To find an augmenting path, start from an unmatched vertex and run a DFS or BFS. Follow these rules: from vertices in , take non-matching edges to . From vertices in , take matching edges back to .
If you reach an unmatched vertex in , you have found an augmenting path. If all unmatched vertices in fail to find paths, the current matching is maximum. This search takes time.
Space complexity is for the data structures used.