Graph View

Backlinks

The Library

Search

SearchSearch

Graph Algorithms

Sep 25, 2024, 4 min read

Breadth First Search

Recursive

BFS(G, v):
	if v not discovered:
		label v as discovered
	
	N := all u adjacent to v
	for each u in N:
		if u not discovered: 
			label u as discovered 

	for each u in N:
		BFS(G, u)

Iterative

Q := queue()
label root as explored
Q.enqueue(root)

while Q is not empty:
	v := Q.dequeue()
	for all u adjacent to v:
		if u not discovered:
			label u as discovered
			Q.enqueue(u)

Depth First Search

Recursive

DFS(G, v):
	label v as discovered
	for each u adjacent to v:
		if u not discovered: 
			DFS(G, u)

Iterative

S := stack()
S.push(root)
while len(S) != 0: 
	v := S.pop()
	if v not discovered:
		label v as discovered 

		for all u adjacent to v: 
			S.push(v)

Dijkstra’s Shortest Path

  • Let be a weighted graph. We take in a source vertex be the distance of from source be the weight of edge be the previous vertex to in a hypothetical shortest path.
for each v in V:
	mark v "unvisited"
	d(v) <- 0
	prev(v) <- NULL

d(s) = 0
Q := priority queue

Q.add(s)

while Q not empty:
	u <- Q.extract_min()
	for each neighbor v of u:
		d'< <- d(u) + w(u,v)
		if d' < d(v):
			d(v) <- d'
			prev(v) <- u
			Q.update_priority(v)

Proof of Correctness

  • Let be the set of visited vertices thus far. be the last visited vertex .

    The base case is easy to see. For the inductive hypothesis, every vertex in that isn’t has the correct label (i.e., ).

    Suppose that the shortest path from to is and has length

    i.e., we have a better path than what Dijkstra’s algorithm outputs.

    Now starts in and leaves to get to which is not in as we have defined.

    Let be the first edge on that leaves . be the -subpath of .

    We have that

    Equivalently

    But by our hypothesis, we know that so

    And since is adjacent to , it must have been updated so that

    Finally, since was selected by the algorithm, must have had the smallest distance label. We get the following inequality

    Which gives us a contradiction when we apply all inequalities in reverse order.

Fleury’s Algorithm

Algorithm

  • Let be an Eulerian Graph. Then, the following construction is always possible and produces an Eulerian trail of .

    Start at any vertex and traverse the edges in an arbitrary manner subject to only the following rules:

  1. Delete the edges as they are traversed and if any isolated vertices arise, erase them too.
  2. At each stage, use a bridge only when there is no alternative (i.e., choose only edges that would not cause the graph to be disconnected).

Proof

  • The algorithm works because we choose edges that do not cause the graph to be disconnected. By choosing to traverse bridges as last resorts, we maintain connectivity
  • It also always yields the complete Eulerian trail since there can be no edge of left untraversed when the last edge incident to is used. Otherwise, the removal of some earlier edge disconnected the graph, contradicting what we have established.

Kruskal’s Algorithm

Algorithm

F := []

for each v in E:
	MAKE-SET(v)

S := sort(E)

for each e in S
	if FIND(u) != FIND-SET(v):
		F.add(e)
		UNION(FIND(u), FIND(v))

return F
  • The algorithm exploits the Minimum Spanning Tree Cut and Cycle property.

Links