Graph Searching: DFS and BFS Algorithms Explained

When we characterize the running time of a graph algorithm on a given graph G = (V, E), we usually measure the size of the input in terms of the number of vertices |V| and the number of edges |E| of the graph.

That is, we describe the size of the input with two parameters, not just one.

GRAPH SEARCHING

Searching a graph:

Systematically follow the edges of a graph to visit the vertices of the graph. Used to discover the structure of a graph.
Standard graph-searching algorithms:

• Breadth-first Search (BFS)
• Depth-first Search (DFS)

Depth-first Search (DFS)

Main Idea: DFS is a systematic method of visiting the vertices of a graph. Its general step requires that if we are currently visiting vertex ‘u’, then we next visit a vertex adjacent to ‘u’ which has not yet been visited. If no such vertex exists then we return to the vertex visited just before u, and the search is repeated until every vertex in that component of the graph has been visited.

DFS uses a strategy that searches “deeper” in the graph whenever possible, unlike BFS which discovers all vertices at distance ‘k’ from the source before discovering any vertices at distance k+1.

The predecessor subgraph produced by DFS may be composed of several trees, because the search may be repeated from several sources. This predecessor subgraph forms a depth-first forest depth-first forest ‘E’ composed of several depth-first trees and the edges in ‘E’ are called tree edges. On the other hand the predecessor subgraph of BFS forms a tree.

Besides creating a depth first forest, depth first search also timestamps each vertex.

Each vertex has two timestamps:

1. The first timestamp d[v] records when v is discovered (and grayed).
2. The second timestamp f[v] records when the search finishes examining v’s adjacency list (and blackens v).

The procedure DFS below records when it discovers vertex u in the variable d[u]and when it finishes vertex u in the variable f [u]. These timestamps are integers between 1 and 2|v|, since, there is one discovery event and one finishing event for each of the |v| vertices. For every vertex v,

d[v]<f[v]

Application of Depth First Search

1. We can determine the articulation point through depth first search.
2. We can determine bridges through depth-first search.
3. We can determine number of connected components through depth first search.
4. We can also determine cycle.

Breadth-First Search

• Input: Graph G = (V, E), either directed or undirected, and source vertex s ∈ V.
• Output:(a) d[v] = distance (smallest number of edges, or shortest path) from s to v, for all v ∈ V. d[v] = ∞ if v is not reachable from s.
  (b) p[v] = u such that (u, v) is last edge on shortest path s to v. u is v’s predecessor.
  (c) Builds breadth-first tree with root s that contains all reachable vertices

Definitions:

• Path between vertices u and v: Sequence of vertices (v1, v2,. . . , vk) such that u = v1 and v = vk, and (vi , vi +1) ∈ E, for all 1 ≤ i ≤ k – 1.
• Length of the path: Number of edges in the path.
• Path is simple if no vertex is repeated.
• Expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier.
  (a) A vertex is “discovered” the first time it is encountered during the search.
  (b) A vertex is “finished” if all vertices adjacent to it have been discovered.

• Colors the vertices to keep track of progress.
  (a) White – Undiscovered.
  (b) Gray – Discovered but not finished.
  (c) Black – Finished.

• Colors are required only to reason about the algorithm. Can be implemented without colors.

Applications of Breadth First Search

1. To test if a graph is bipartite.
2. Cycle detection in undirected graph.
3. To find if there is a path between two vertices.
4. Finding all nodes within one connected components
5. Number of connected components.

MADE EASY

MADE EASY is a well-organized institute, complete in all aspects, and provides quality guidance for both written and personality tests. MADE EASY has produced top-ranked students in ESE, GATE, and various public sector exams. The publishing team regularly writes exam-related blogs based on conversations with the faculty, helping students prepare effectively for their exams.