Graph Search

Breadth First Search

Idea

Go one level at a time - level by level within a graph.

Pseudocode

function BREADTH_FIRST_SEARCH(G, start_vertex):
    Q = INIT_QUEUE()
    Q.append(start_vertex)
    while Q is not empty
        current_vertex = Q.remove(0)
        if current_vertex is not visited
            Mark current_vertex as visited
            Print current_vertex
            for all neighboring nodes for current_vertex
                if neighboring nodes are not visited
                    Q.append(neighboring_node)

Completeness and optimality

In the analysis of algorithms, the input to breadth-first search is assumed to be a finite graph, represented explicitly as anadjacency listor similar representation. However, in the application of graph traversal methods inartificial intelligencethe input may be animplicit representationof an infinite graph. In this context, a search method is described as being complete if it is guaranteed to find a goal state if one exists. Breadth-first search is complete, but depth-first search is not. When applied to infinite graphs represented implicitly, breadth-first search will eventually find the goal state, but depth-first search may get lost in parts of the graph that have no goal state and never return

Applications

• Cheney's algorithm for GC
• Testing bipartiteness of a graph (Two coloring graph)
• Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
• Finding the shortest path between two nodes u and v, with path length measured by number of edges

Depth First Search

Idea

Go multiple levels and meet the leaf nodes first. Meet all the leaf nodes.

Pseudocode

function DEPTH_FIRST_SEARCH(G, start_vertex):  
    S = INIT_STACK()  
    S.add(start_vertex)  
    while S is not empty  
        current_vertex = S.pop()  
        if current_vertex is not visited  
            Mark current_vertex as visited  
            Print current_vertex  
            for all neighboring nodes for current_vertex  
                if neighboring nodes are not visited  
                    S.add(neighboring_node)

Applications

Finding connected components.

Finding strongly connected components.

Finding 2-(edge or vertex)-connected components.

Finding 3-(edge or vertex)-connected components.

Finding the bridges of a graph.

Topological sorting.

Generating words in order to plot the Limit Set of a Group.

Planarity testing

Solving puzzles with only one solution, such as mazes. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)

Maze generation may use a randomized depth-first search.

Finding biconnectivity in graphs.

Complexity

E - number of edges 
V - number of vertices
O(E+V)