Graph Algorithms - I

TBD: Cover the implementation in Cpp part here. Ajacency list, Adjancy matrix and application of the Graph.

Subtopics

Depth first search

DFS solve the reachablity problem, can help detect cycles, find directed path, topological sorting, connected components, solve bipartitedness or periodic cycle problem. In below, previsit and postvisit functions can help in performing some actions at first discovery or at finish time of DFS.

Algorithm


Explore(G, s)
	G = (V, E) is a Graph 
	visited(s) = true 
	previsit(s) 
	for all nodes t reachable from s 
		if not visited[t]:
			Explore(G, t) 
	postvisit(s)


DFS(G)
	G = (V, E) is a Graph, 
	for each u in V visited(u) is set to true 
	for all nodes in G.V :
		if not visited[u] :
			Explore(G, u)

Each explore call discovers a new connected component. We can mark the cc number during previst call. We can also mark three colors White, Grey and Black, where white indicates undiscovered vertex, grey is in frontier and We can also mark the previsit and postvisit numbers. There are 2 type of edges in the undirected graph case, tree edge and back edge. For tree edge the [pre(u), post(u)] contains [pre(v), post[v]] else they are disjoint.

For the directed case, there are 4 types of edges.

Tree edges (u, v): pre(u) < pre(v) < post(v) < post(u)

Back edges (u, v): pre(v) < pre(u) < post(u) < post(v)

Forward edges(u, v) : pre(u) < pre(v) < post(v) < post(u)

Cross edges (u, v): pre(v) < post(v) < pre(u) < pre(u)

A directed graph is a DAG iff DFS discovers a back edge. If there is no back edge i.e its a DAG then every edge leads to a vertex with lower post order number. Hence the nodes of the graph can be ordered in this sense. The node with the hightest post order number is the source vertex and one with the lowest post order number is the Every DAG will have atleast one source and one sink.

Running time O(n+m), where n is number of vertices and m is number of edges.

Topological sorting, CC and Cycles

Topological sorting is representing nodes of Graph in sorted order such that the edges goes from left to right only.Every DAG (and only DAGs) can be sorted in Topological order. In a DAG there is always a source and sink vertex, we can step by step remove either source or sink and recursively find this order. Also the post order numbers calculated in DFS also indicates the topological ordering. Highest post order number indicates that the vertex is source vertex and so on.

Back edge in directed or undirected graph indicates cycle.

Each explore cycle finds a new Connected component in DFS for undirected graph.

Strongly connected components and 2SAT

SCC is the sub graph such that all pair of nodes are connected. Pair of nodes are called connected if there is path from Every directed graph is a DAG of its strongly connected components. The node that recieves the highest post order number is in the source SCC. So the highest post order number of

BFS and Shortest path

Distance between two nodes is length of the shortest path between 2 nodes. DFS donot find the shortest path. We can use BFS to get the shortest path tree in unweighted graph. Again we can augments BFS, to include the parent, dist, color code (W, G, B) to idenify forntier.


BFS(G, s)
	for all u in G.V: 
		dist(u) = INF
	pick a initial node s,
	set dist(s) = 0
	Q = queue(s)
	u = eject(Q)
	inject(Q, v)
	dist[v] = dist[u] + 1

Prim's Algorithm

Krushkal's Algorithm

Dijkstra's Algorithm

BFS won't find shortest distance on weighted graph. We can use a slight variation to it. Dijktras algorithm is like BFS but instead of using queue it uses priority queue with keys which keeps in account the edge weights.

Dijkstra(G, s)
	for all u in G.V: 
		dist(u) = INF, 
		prev(u) = NIL 
	set dist(s) = 0 
	H = makequeue(V) with distance value as keys 
	u = deletemin(Q) 
	dist[v] = dist[u] + l(u, v) 
	prev[v] = u decreaseKey(H, v)

The above algorithm uses Binary heap (or can be arrays, d-ary heap or fibonacci heap) for priotity queue implementation. Binary heap is a complete binary tree with heap property (root is either greater or smaller than the childs). Following operations of priority queue is used in the algorithm:

Insert (): Add a new element to the set.

Decrease-Key (H, ): accomodate decrease in key value for particular element.

Delete-Min: Return the element with the smallest key and remove it from the set.

Make-queue: Build priority queue using the given elements and key values.

For binary heap being a array can be implemented as an array of size 2n - 1 for n elements. with parent of j being j/2 and childs being 2i + 1 and 2i + 2. Each heap operation can be implemented as below

Insert: Place the new element at the bottom of the tree and let it bubble. Then if it is smaller than its parent, swap and keep doing it repeatedly.

Decrease key: decrease the key and heapify.

Deletemin: swap root with lowest element, remove last element and let root sift down. if it is bigger than any child, swap it with min of those and repeat.

Bellman Ford's Algorithm

Bellman ford can take care of the negative cycles. To detect negative cycles we can run the algorithm one more time and see if the weight changes.


Bellman(G)
	dist(u) = INF 
	prev(u) = NIL 
	dist(s) = 0 
	dist(v) = min(dist(u), l(u, v))

Floyd Warshall's Algorithm

Common Problem statement

Complexity Cheat sheet

Problem	Algorithm	Time	Space
Path Existence	DFS	E + V	V
Shortest path (fewest edges)	BFS	E + V	V
Detect Cycle	DFS	E + V	V
Directed Path	DFS	E + V	V
Shortest Directed Path (fewest edges)	BFS	E + V	V
Directed cycle	DFS	E + V	V
Topological sort	DFS	E + V	V
bipartitedness / odd cycle	DFS	E + V	V
connected components	DFS	E + V	V
strong components	Kosaraju	E + V	V
eulerian cycle (un)directed	DFS	E + V	E + V
transitive closure	DFS	V(V+E)	V^2
minimum spanning tree	Krushkal	ElogV	E + V
minimum spanning tree	Prims	ElogV	E + V
single source shortest path	Dijktras	ElogV	V
single source shortest path	Bellman ford	V(V+E)	V
all pair shortest paths	Floyd Warshall	V^3	V^2
maxflow-mincut	Ford Fulkerson	EV(E+V)	V