Graph Algorithms

Hamiltonian vs Euler:

• hamiltonian path → path connecting two vertices (v,w) in graph G such that the path includes each vertex exactly once
• hamiltonian circuit → hamiltonian path where starting vertex = ending vertex (e.g. bus route – want to go to each stop exactly once + end up back at bus depo)
• approach (similar to recursive DFS path-finding, but tracking lengths):
  • generate all possible simple paths (e.g. using DFS)
  • keep counter of vertices visited in current path
  • stop when path found containing V vertices
• pseudocode:

(12)

• how many connected subgraphs are there?
• (is the graph entirely connected, or are there disconnected subgraphs?)
• easiest solution: create a componentOf array, where each index refers to a vertex + the value at that index refers to which graph it’s in
  • start at a node + do a DFS traversal
  • any nodes that have been visited must be in in the same subgraph, so set each of their values in componentOf array to the same number
  • repeat for one of the unvisited nodes, with different subgraph number
  • repeat until all nodes have been visited

• pseudocode:

(12)

• is there a cycle in a particular graph, or is it just a tree?
• true if at any point in the graph…
  • path of length > 2
  • start vertex = end vertex
  • no edge used more than once
• can do DFS in tree – if you ever reach a node you’ve already visited (incl. start node), then there is a cycle
• pseudocode:

(12)

A simple graph with n vertices (n ≥ 3) is Hamiltonian if every vertex has degree n / 2 or greater

A graph has an Euler circuit if and only if the <g-bubble> degree </g-bubble> of every vertex is even and it is connected.

// The following is the pseudocode for Kruskal's Algorithm, which find the minimum spanning tree of a graph.

KruskalMST(G):
  MST=empty graph
  sort edges(G) by weight
  for each e ∈ sortedEdgeList:
    MST = MST ∪ {e}  // add edge
    if MST has a cyle:
      MST = MST \ {e}  // drop edge 
    if MST has n-1 edges:
      return MST

// The following is the pseudocode for Prim's algorithm, which finds the minimum spanning tree of a graph.

PrimMST(G):
  MST = empty graph
  usedV = {0}
  unusedE = edges(g)
  while |usedV| < n:
    find e = (s,t,w) ∈ unusedE such that {
       s ∈ usedV ∧ t ∉ usedV 
         (∧ w is min weight of all such edges)
    }
    MST = MST ∪ {e}
    usedV = usedV ∪ {t}
    unusedE = unusedE \ {e}
  return MST

// This is the pseudocode for Dijkstra's Algorithm, which finds the shortest path from a source vertex
to all other vertices

dijkstraSSSP(G,source):
  dist[]  // array of cost of shortest path from s
  pred[]  // array of predecessor in shortest path from s
  vSet    // vertices whose shortest path from s is unknown
  initialise all dist[] to ∞
  dist[source]=0
  initialise all pred[] to -1
  vSet = all vertices of G
  while vSet is not empty:
    find v in vSet with minimum dist[v]
    for each (v,w,weight) in edges(G):
      relax along (v,w,weight)
    vSet = vSet \ {v}