Graphs

Applications

Google knowledge graph | six degrees of separation

google map (select the shortest, cheapest or most scenic way to a particular place)

Terminology

Graph representations: adjacency matrix, adjacency list, edge list

Adjacency matrix 
(A)                               (B)
  | 1  2  3  4  5                  | 1  2  3  4  5
--|--------------                --|--------------
1 |    1        1                1 |    1        1 
2 |       1                      2 | 1     1     1
3 |          1                   3 |    1     1
4 |             1                4 |       1     1
5 |    1                         5 | 1  1     1
Adjacency list 
(A)                               (B)
Vertex Adjacency-list             Vertex  Adjacency-list
1      [2 5]                      1       [2 5]
2      [3]                        2       [1 3 5]
3      [4]                        3       [2 4]
4      [5]                        4       [3 5]
5      [2]                        5       [1 2 4]
Edge list 
1 2
1 5
2 3
3 4
5 2

Other representations:

Object Oriented Representations
v.neighbors = Adj[v]

Implicit Representations
Adj(u) is a function
v.neighbors() is a method
(the above is useful when there are enormous numbers of vertices, e.g. possible distinct states of a complex system, etc.)

Graph visualization

Graph applications

Graph implementations

An ADT for graphs | An implementation of the ADT using adjacency list

Graph traversal (walk through a graph)

Graph traversal: visit the vertices of a graph in some specific order based on the graph's topology.
(Recall that tree traversals visit every node exactly once, in some specified order such as preorder, inorder, or postorder)

Graph traversal algorithm typically begins with a start vertex and then visits the remaining vertices from the start vertex.
Be aware of the following cases:
1) It may not be possible to reach all vertices from the start vertex (when the graph is not connected).
2) The graph may contain cycles, and cycles may cause the algorithm to go into an infinite loop if not carefully considered.
Solutions: to maintain a mark bit for each vertex on the graph and set the bit when the vertex is visited.
Walk in a graph
Figure source

Depth-First Search (DFS)

Whenever a vertex V is visited during the search, DFS will recursively visit all of V's unvisited neighbors. Equivalently, DFS will add all edges leading out of v (to an unvisited vertex) to a stack. The next vertex to be visited is determined by popping the stack and following that edge. The DFS process can be used to define a depth-first search tree, which is composed of the edges that were followed to any unvisited vertex during the traversal, and leaves out the edges that lead to already visited vertices. 
	
	public void DFS(int v) {
		preVisit(v); 
  		//e.g., preNum.add(v) for preVisit enumeration of the nodes
		//when v is first "discovered" (aizu)
		setVisited(v);
		List<Integer> neighbors = getNeighbors(v);
		for(int i = 0; i < neighbors.size(); i ++) {
			int v1 = neighbors.get(i);
			if(ifVisited(v1) == false) DFS(v1); //use recursion!
		}
		postVisit(v); 
		//e.g., postNum.add(v) for postVisit enumeration of the nodes
		//when search finishes examining v's neighbors 
	}
Cost of the DFS? DFS processes each edge once in a directed graph. In an undirected graph, DFS processes each edge from both directions. Each vertex must be visited, but only once, so the total cost is $\Theta(|V| + |E|)$.

preVisit() vs postVisit() functions; E.g., postVisit enumeration of the nodes for topological sort.

How does DFS work?

Breath-First Search (BFS)

BFS examines all vertices connected to the start vertex before visiting vertices further away. Similarly, the BFS process results in a breadth-first search tree
BFS is implemented similarly to DFS, except that a queue replaces the recursion stack.

How does it work?
  1. Start from a node s in the graph. (1 node visited in 0 steps)
  2. Visit all nodes that can be reached by only one edge. ( Adj[s] nodes visited in 1 step)
  3. From each node visited in (1.), visit all nodes that can be reached by only one edge.
  4. Continue until you visit all nodes that are reachable from the node s.
Avoid duplicates--don't visit a node that has been visited before!
This will work in $O(|V|+|E|)$ time.
	public void BFS(int s) {
		ArrayList<Integer> toVisit = new ArrayList<Integer>();
		toVisit.add(s);
		while(toVisit.size() > 0) {
			//first-in, first-visit; if queue is used, use its dequeue() function
			int v = toVisit.remove(0); 
			setVisited(v);
			List<Integer> neighbors = getNeighbors(v);
			for(int i = 0; i < neighbors.size(); i ++) {
				int v1 = neighbors.get(i);
				if((ifVisited(v1) == false) && (toVisit.contains(v1) == false)) {
					toVisit.add(v1);
				}
			}
		}
	}

Topological Sort

Shortest-Paths Problems

Minimum-Cost Spanning Trees