II.1.1 Undirected Graphs

Algorithm II Week 1: Undirected Graphs

Graph

Graph. Set of vertices connected pairwise by edges.

Some Problems

• Path. Is there a path between s and t ?

  • Shortest path. What is the shortest path between s and t ?

• Cycle. Is there a cycle in the graph?

  • Euler tour. Is there a cycle that uses each edge exactly once?

  • Hamilton tour. Is there a cycle that uses each vertex exactly once.

• Connectivity. Is there a way to connect all of the vertices?

  • MST. What is the best way to connect all of the vertices?

  • Biconnectivity. Is there a vertex whose removal disconnects the graph?

• Planarity. Can you draw the graph in the plane with no crossing edges?

• Graph isomorphism. Do two adjacency lists represent the same graph?

Graph API

Class Graph:
    void add_edge(int v, int w)
    list adj(inv)
    int num_of_V()
    int num_of_E()
    str to_string()

Representation

1. Set-of-edges representation (linked list or array)
2. Adjancency-matrix representation (vertex-indexed array of lists)

   

 public class Graph {
   private final int V;
   private Bag<Integer>[] adj;
   public Graph(int V)
   {
      this.V = V;
      adj = (Bag<Integer>[]) new Bag[V];
      for (int v = 0; v < V; v++)
         adj[v] = new Bag<Integer>();
   }
   public void addEdge(int v, int w)
   {
      adj[v].add(w);
      adj[w].add(v);
   }
   public Iterable<Integer> adj(int v)
   {  return adj[v];  }
}

Depth First Search & Breadth First Search

Getting out of a maze.