Overview

Searching a graph usually involves following the edges of a graph to discover all the vertices. Graph searching can be used to discover the structure of a graph. There are two different basic types of searches #BFS and #DFS.

BFS

Running Time: $\mathrm{\Theta }(V+E)$ (V = # vertices, E = # edges)

Breath-First Search systematically explores the edges of a graph to discover every vertex, starting from a source vertex. BFS also assigns a distance to each vertex which. Distance is defined as the smallest number of edges it takes to get from the source to the particular vertex.

BFS works on both directed and undirected graphs.

Implementation

We discover vertices in "waves" to expand the "frontier" between discovered and undiscovered vertices.

e.g. Discovering vertices

• 1st wave will discover all vertices with distance 1.
• 2nd wave will then discover all vertices with distance 2.

BFS uses a FIFO queue to keep track of every frontier wave.

There are 3 "types" of vertices in a BFS, undiscovered, frontier, and discovered vertices. They are marked as such throughout the search.

Undiscovered vertices are what all vertices start out as, they are not yet visited.

Frontier vertices are ones that have just been discovered. They are enqueued into the FIFO when discovered.

Discovered vertices are ones that have been visited. The vertex becomes "discovered" when it is dequeued from the FIFO queue and all undiscovered adjacent vertices are put on the frontier.

Additionally the following properties are kept track of for each vertex.

• Distance (from source)
• Predecessor (parent vertex)
• Type (discovered, undiscovered, frontier)

Pseudo Code

function bfs(graph, source) {
  // Initalize all the vertices (clear the graph)
  for (let vertex of graph.vertices) {
    vertex.type = "undiscovered";
    vertex.distance = Infinity;
    vertex.predecessor = null;
  }
  // Initalize the source vertex
  source.type = "frontier";
  source.distance = 0;

  // Start a FIFO queue
  const queue = [source];

  // Continue expanding frontier
  while (queue.length !== 0) {
    // Grab the vertex at the front of the frontier
    u = queue.shift();
	// Visit and unvisited neighbors and update the distance
    for (let v of graph.adj[u]) {
      if (v.type === "undiscovered") {
        v.type = "frontier";
        v.distance = u.distance + 1;
        v.parent = u
        queue.push(v)
      }
    }
	// We've finished discovering this vertex
	u.type = "discovered"
  }
}

DFS

Running Time: $\mathrm{\Theta }(V+E)$ (V = # vertices, E = # edges)

Depth-First Search works as the anthesis to BFS. DFS does not have a source vertex and searches "deeper" into the graph when possible, only backtracking traveling deeper is not possible. Searching "deeper" usually consists of continuing visiting adjacent vertices when possible.

DFS works on both directed and undirected graphs.

Implementation

There are 3 "types" of vertices in a DFS, undiscovered, frontier, and discovered vertices. They are marked as such throughout the search.

Undiscovered vertices are what all vertices start out as, they are not yet visited.

Frontier vertices are ones that have just been discovered. They are enqueued into the FIFO when discovered.

Discovered vertices are ones that have been visited. The vertex becomes "discovered" when it is dequeued from the FIFO queue and all undiscovered adjacent vertices are put on the frontier.

DFS maintains 2 timestamps for each vertex in addition to keeping track of the predecessor and type.

• Time of arrival records when the vertex was first discovered (added as a frontier)
• Time of departure records when the vertex was marked as discovered.

Time of arrival should always be less than the time of departure.

Maintaining timestamps is useful for topological sorting

Pseudo Code

// Set a global time for both functions to use
var time = 0;

function dfs(graph) {
  // Intitalize each vertex
  for (const vertex of graph.vertices) {
    vertex.type = "undiscovered";
    vertex.predecessor = null;
  }
  time = 0;
  // Search any undiscovered vertices
  for (const u of graph.vertices) {
	if (u.type === "undiscovered") {
	  dfs_visit(G, u);
	}
  }
}

function dfs_visit(graph, u) {
  // We have discovered this vertex
  u.arrive = ++time;
  u.type = "frontier";
  // Keep looking into adjacent vertices
  for (const v of graph.adj[u]) {
    if (v.type === "undiscovered") {
	  v.predecessor = u;
	  dfs_visit(graph, v)
    }
  }
  // We have finished discovering this vertex
  u.depart = ++time;
  u.type = "discovered"
}

Reference

1. Sun, Hongyang Graphs The University of Kansas 2024

Related

• Graphs
• Algorithms