Graph Search

Neighborhood

The set of vertices in $G$ adjacent to a vertex $v$ is called the neighborhood of $v$ and denoted as $N(v)$.

If it is a directed graph, you can make a distinction between incoming and outgoing neighbors. $N_{outgoing}(A) = \{B,C\}$ $N_{incoming}(C) = \{A,D\}$

Path

A path is a sequence of consecutive edges in a graph.

• Alternatively, we can define "path" as a sequence of vertices where each vertex in the sequence is adjacent to the vertex next to it. (The end point of those edges)

A simple path is one where a path does not repeat any of its edges/vertex.

•  In some references, what I defined as "path" is described as "walk," and instead "simple path" is called, simply, "path."
•  No circley movement!

Graph Search

The general graph search problem is figuring out if a path contains a path from one vertex to another. Input: Graph $G = (V,E)$, and a starting vertex $s \in V$. Output: Identify the vertices in $V$ reachable from $s$ in $G$.

• Bt definition, every vertex can reach itself, $s$.

There are many variation of this problem. For example, you can also request the path to each of those vertices. Or, you can ask for the shortest path.

General Solution

Systematic, deterministic, efficient, and general solution.

// Post: a vertex is reachable from s iff it is marked as explored.

mark s as explored;
	mark all other vertices as unexplored;

	while (there is an edge (v,w) in E with v explored and w unexplored) {
		choose some edge (v,w); // underspecified
		mark w as explored;
	} 

• Choosing the edge: depending on what you pick, you can create a breadth-first search or a depth-first search

Pseudocode:

mark s as explored; all other vertices as unexplored
Q := a queue data structure, initialize with s
while Q is not empty
	remove the vertex from the front of Q, call it v
	for edge (v,w) in v's neighborhood do
	if w is unexplored then
		mark w as explored
		add w to the end of Q

Breadth-First Search

Breadth-First Search, or BFS, is any search algorithm that considers neighbors of a vertex, that is, outgoing edges of the vertex's predecessor in the search, before any outgoing edges of the vertex. Extremes are searched last. Dictionary of Algorithms and Data Structures

Given a "source" vertex to initiate the search, BFS starts by visiting its adjacent nodes. All nodes can be reached by a path from the start node containing two edges, three edges, etc. 

The BFS algorithm visits all vertices in a graph $G$ that are $k$ edges away from the source vertex $s$ before visiting any vertex $k+1$ edges away.

• You have seen this behavior in level-order tree traversal.

Depth-First Search

Depth-First Search, or DFS, is any search algorithm that considers outgoing edges (children) of a vertex before its siblings, that is, outgoing edges of the vertex's predecessor in the search. Extremes are searched first.

Explore deeper into the graph whenever possible. Starting at a vertex, DFS will take a path and explore it as far as it goes. It then backtracks until it reaches an unexplored neighbor (a branch on the path it has not explored yet). This process continues until every vertex that is reachable from the original source vertex has been discovered.

• You have seen this behavior in pre-order and post-order tree traversal (and in-order binary tree traversal).

Psudocode:

mark s as explored; all other vertices as unexplored
S := a stack data structure, initialize with s
while S is not empty
	remove the vertex from the top of S, call it v
	for edge (v,w) in v's neighborhood do
	if w is unexplored then
		mark w as explored
		add w to the top of S

Discovered vs Visited

"discovered" happens when you run across the node, basically when you add it to the stack or queue. "visited" means that you explored it.

Analysis

Here is a (more elaborate) pseudocode for solving the General Graph Search problem:

mark s as explored, all other vertices as unexplored		O(n)
D := a queue or stack data structure, initialized with s 	O(1)
while D is not empty do										O(n)
	remove the vertex from the front/top of D, call it v	O(1)
	for edge (v, w) in v's neighborhood do					O(d(v))
		if w is unexplored then								O(1)
			mark w as explored								O(1)
			add w to the end/top of D						O(1)

• you will only put it into the stack/queue if it hasnt been explored, so every node can only be put in it at max one.
  • worst case: n

-d(v) is the degree of v. It means the number of neighbors a node v has.

If it is an adjacency matrix: it is O(n^2) If it is an adjacency list: it is O(n*d(v))

• where the sum of d(v) = 2M which is O(m)
  • O(m) is the most expensive part of this algorithm
  • The whole thing is O(n+m)