Page 201 - Algorithms Notes for Professionals

end if
end for
end while
Return level

As we have discussed earlier, BFS only works for unweighted graphs. For weighted graphs, we'll need Dijkstra's
algorithm. For negative edge cycles, we need Bellman-Ford's algorithm. Again this algorithm is single source
shortest path algorithm. If we need to find out distance from each nodes to all other nodes, we'll need Floyd-
Warshall's algorithm.

Section 41.3: Connected Components Of Undirected Graph
Using BFS

BFS can be used to find the connected components of an undirected graph. We can also find if the given graph is
connected or not. Our subsequent discussion assumes we are dealing with undirected graphs.The definition of a
connected graph is:

A graph is connected if there is a path between every pair of vertices.

Following is a connected graph.

Following graph is not connected and has 2 connected components:

1. Connected Component 1: {a,b,c,d,e}
2. Connected Component 2: {f}

colegiohispanomexicano.net – Algorithms Notes 197