Week 1 - Graphs

1. Undirected Graphs

1.1. Graph terminology

  • Path. Sequence of vertices connected by edges.
  • Cycle. Path whose first and last vertices are the same.
  • Two vertices are connected if there is a path between them.
  • Some graph-processing 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?
  • Challenge. Which of these problems are easy? difficult? intractable?

1.2. Graph API

  • Typical graph-processing code

Adjacency-list graph representation

  • Goal. Find all vertices connected to s (and a corresponding path).
  • Algorithm.
    • Use recursion (ball of string).
    • Mark each visited vertex (and keep track of edge taken to visit it). Return (retrace steps) when no unvisited options.
  • Data structures.
    • boolean[] marked to mark visited vertices.
    • int[] edgeTo to keep tree of paths.
    • (edgeTo[w] == v) means that edge v-w taken to visit w for first time
  • Depth-first search. Put unvisited vertices on a stack.
  • Breadth-first search. Put unvisited vertices on a queue.
  • Shortest path. Find path from s to t that uses fewest number of edges.

  • Algorithm.

    • Put s onto a FIFO queue, and mark s as visited.
    • Repeat until the queue is empty:
      • remove the least recently added vertex v
      • add each of v's unvisited neighbors to the queue, and mark them as visited.

1.5. Connected Components

  • Goal:
    • Vertices v and w are connected if there is a path between them.
    • Preprocess graph to answer queries of the form is v connected to w? in constant time.
  • The relation "is connected to" is an equivalence relation:
    • Reflexive: v is connected to v.
    • Symmetric: if v is connected to w, then w is connected to v.
    • Transitive: if v connected to w and w connected to x, then v connected to x.
  • A connected component is a maximal set of connected vertices.
  • Algorithm:
    • Initialize all vertices v as unmarked.
    • For each unmarked vertex v, run DFS to identify all vertices discovered as part of the same component.

1.6. Some Quizzes

  • Some definitions:
    • An edge having the same vertex as both its end vertices is called a self-loop.
    • Two edges with the same end vertices are referred to as parallel edges.
    • A graph that has neither self-loops nor parallel edges is called a simple graph.
    • The eccentricity of a vertex v in a connected graph G is the maximum graph distance between v and any other vertex in the graph G.
    • The maximum eccentricity is the graph diameter. The minimum graph eccentricity is called the graph radius.
    • The center of a graph G is the set of vertices of graph eccentricity equal to the graph radius. (i.e., the set of central points).
    • From Wolfram Mathworld
  • Diameter of a tree. Given a graph that is a tree (connected and acyclic), find the longest path, i.e., a pair of vertices v and w that are as far apart as possible. Your algorithm should run in linear time.

    1. Assume x and y are the vertices with the longest diameter.
    2. Randomly pick any vertex v, and its furthest vertex w should be either x or y. Because the distance between any two vertices is definitely less than or equal to x-y.
      1. Remember there are always paths from v to x and y, so [v-w] > [v-x] and [v-w] > [v-y] can't be true in the same time. otherwise, y or x should be equal to w.
    3. Then just use x or y to find y or x which correspond to its furthest vertex.
  • Center of a tree. Given a graph that is a tree (connected and acyclic), find a vertex such that its maximum distance from any other vertex is minimized.

    • Find the diameter of the tree (the longest path between two vertices) and return a vertex in the middle.
  • Parallel edge detection. Devise a linear-time algorithm to count the parallel edges in a graph.
    • Hint: maintain a boolean array of the neighbors of a vertex, and reuse this array by only reinitializing the entries as needed.
    • // TODO Don't understand.

2. Directed Graphs (Digraphs)

  • Set of vertices connected pairwise by directed edges.

2.1. Digraph API

  • toString()

      In in = new In(args[0]);
      Digraph G = new Digraph(in);
      for (int v = 0; v < G.V(); v++) 
          for (int w: G.adj(v))
              StdOut.pringln(v + "->" + w);
  • Adjacency-lists digraph representation

    • same as graph APIs. only difference is:

        public void addEdge(int v, int w) { 
  • same as Undirected Graph.

2.3. Topological(拓扑) Sort

  • Goal. Given a set of tasks to be completed with precedence constraints, in which order should we schedule the tasks?
    • Digraph model.
      • vertex = task;
      • edge = precedence constraint.
  • DAG. Directed acyclic graph.
  • Topological sort. Redraw DAG so all edges point upwards.

    • Run depth-first search.
    • Return vertices in reverse postorder.
  • A digraph has a topological order iff no directed cycle.

2.4. Strong Components

  • Def. Vertices v and w are strongly connected if there is both a directed path from v to w and a directed path from w to v.
  • Def. A strong component is a maximal subset of strongly-connected vertices.

Connected components vs. strongly-connected components

Kosaraju-Sharir algorithm

  • Reverse graph. Strong components in G are same as in G^R.
    • G^R denotes reversed G.
  • Kernel DAG. Contract each strong component into a single vertex.

    • Compute topological order in kernel DAG.
    • Run DFS, considering vertices in reverse topological order.
  • Phases:

    1. Compute topological order in G^R.
    2. run DFS on G, considering vertices in order given by first DFS
  • Java Implement(Strong components in a digraph (with two DFSs))

3. Digraph-processing summary

results matching ""

    No results matching ""