Algorithm 25 Generic depth-first search
1: // Driver function that calls DFS until everything has been visited
2: function TRAVERSE(G = (V,E ))
3: visited[1..n] = false
4: for each vertex u = 1 to n do
5: if not visited[u] then
6: DFS(u)
7:
8: function DFS(u)
9: visited[u] = true
10: for each vertex v adjacent to u do
11: if not visited[v ] then
12: DFS(v ) and :Algorithm 26 Finding connected components using depth-first search
1: // Driver function that finds each connected component
2: function CONNECTED_COMPONENTS(G = (V,E ))
3: component[1..n] = null
4: num_components = 0
5: for each vertex u = 1 to n do
6: if component[u] = null then
7: num_components += 1
8: DFS(u, num_components)
9: return num_components, component[1..n]
10:
11: // One DFS will visit a single connected component
12: function DFS(u, comp_num)
13: component[u] = comp_num
14: for each vertex v adjacent to u do
15: if component[v ] = null then
16: DFS(v , comp_num) and :Algorithm 27 Cycle detection in an undirected graph using depth-first search
1: // Driver function that calls DFS to look for a cycle
2: function HAS_CYCLE(G = (V,E ))
3: visited[1..n] = false
4: for each vertex u = 1 to n do
5: if not visited[u] and DFS(u, null) = true then
6: return true
7: return false
8:
9: // Returns True if a cycle was detected
10: function DFS(u, p)
11: visited[u] = true
12: for each vertex v adjacent to u do
13: if visited[v ] and v 6= p then //We found a cycle!
14: return true
15: else if v 6= p and DFS(v , u) = true then
16: return true
17: return false and: Algorithm 28 Generic breadth-first search
1: function BFS(G = (V,E ), s )
2: visited[1..n] = false
3: visited[s ] = true
4: queue = Queue()
5: queue.push(s )
6: while queue is not empty do
7: u = queue.pop()
8: for each vertex v adjacent to u do
9: if not visited[v ] then
10: visited[v ] = true
11: queue.push(v ) and : Algorithm 29 Single-source shortest paths in an unweighted graph
1: function BFS(G = (V,E ), s )
2: dist[1..n] =1
3: pred[1..n] = null
4: queue = Queue()
5: queue.push(s )
6: dist[s ] = 0
7: while queue is not empty do
8: u = queue.pop()
9: for each vertex v adjacent to u do
10: if dist[v ] =1then
11: dist[v ] = dist[u] + 1
12: pred[v ] = u
13: queue.push(v ) and Algorithm 30 Reconstruct shortest path
1: function GET_PATH(s , u, pred[1..n])
2: path = [u]
3: while u 6= s do
4: path.append(pred[u])
5: u = pred[u]
6: return reverse(path) and : Algorithm 31 Topological sorting using Kahn’s algorithm
1: function TOPOLOGICAL_SORT(G = (V,E ))
2: order = empty array
3: ready = queue of all vertices with no incoming edges
4: while ready is not empty do
5: u = ready.pop()
6: order.append(u)
7: for each edge (u, v ) adjacent to u do
8: Remove (u, v ) from G
9: if v has no remaining incoming edges then
10: ready.push(v )
11: return order and : Algorithm 32 Topological sorting using DFS
1: function TOPOLOGICAL_SORT(G = (V,E ))
2: order = empty array
3: visited[1..n] = false
4: for each vertex v = 1 to n do
5: if not visited[v ] then
6: DFS(v )
7: return reverse(order)
8:
9: function DFS(u)
10: visited[u] = true
11: for each vertex v adjacent to u do
12: if not visited[v ] then
13: DFS(v )
14: order.append(u) and : Algorithm 33 Connectivity check
1: function CONNECTED(u, v )
2: return (component[u] = component[v ])