Graph Algorithms

Graph Algorithms

1. A set of objects, called vertices, together with a collection of pairwise connections between them, called edges.

2. Graph ADT

   • numVertices() vertices() numEdges() edges() getEdge(u,v)
   • endVertices(e) opposite(v,e) outDegree(v) inDegree(v) outdoingEdge(v)
   • incomingEdges(v) insertVertex(x) insertEdge(u,v,x) removeVertex(v) removeEdge(e)

3. Data Structures for Graphs

   • Edge list
     • unordered list of all edges.
   • Adjacency list
     • for each vertex, a separate list containing those edges that are incident to the vertex.
   • Adjacency map
     • the secondary container of all edges incident to a vertex is organized as a map.
   • Adjacency matrix
     • maintaining an n × n matrix, for a graph with n vertices.

4. Graph Traversals

   • systematic procedure for exploring a graph by examining all of its vertices and edges.
     • Depth-First Search
     • Breadth-First Search

5. Shortest Paths

   • Dijkstra's Algorithm
     • Applying the greedy method to the single-source, shortest-path problem

6. Minimum Spanning Trees

   • Spanning tree: A tree that contains every vertex of a connected graph G
   • MST: the problem of computing a spanning tree T with smallest total weight
   • Prim-Jarník Algorithm
     • we grow a minimum spanning tree from a single cluster starting from some “root” vertex s.
   • Kruskal’s Algorithm
     • maintains many smaller trees in a forest, repeatedly merging pairs of trees until a single tree spans the graph.