Undirected Graph

1.  Graph -- Set of vertices connected pairwise by edges.

 

2.  Graph Applications :

 

3.  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.

 

4.  Graph API

public class Graph {
    Graph(int V) {...} //create an empty graph with V vertices
    Graph(In in) {...} //create a graph from input stream
    void addEdge(int v, int w) {...} //add an edge v-w
    Iterable<Integer> adj(int v) {...} //vertices adjacent to v
    int V() {...} //number of vertices
    int E() {...} //number of edges
    String toString() {...} //string representation
}

 

5.  Typical graph-processing code

//compute the degree of v
public static int degree(Graph G, int v)
{
    int degree = 0;
    for (int w : G.adj(v)) degree++;
    return degree;
}

//compute maximum degree
public static int maxDegree(Graph G)
{
    int max = 0;
    for (int v = 0; v < G.V(); v++)
        if (degree(G, v) > max)
            max = degree(G, v);
    return max;
}

//compute average degree
public static double averageDegree(Graph G)
{ return 2.0 * G.E() / G.V(); }

//count self-loops
public static int numberOfSelfLoops(Graph G)
{
    int count = 0;
    for (int v = 0; v < G.V(); v++)
    for (int w : G.adj(v))
        if (v == w) count++;
    return count/2; // each edge counted twice
}

 

6.  Graph Representation

    --  Set-of-edges : Maintain a list of the edges (linked list or array).

    --  Adjacency-matrix : Maintain a two-dimensional V-by-V boolean array; for each edge v–w in graph: adj[v][w] = adj[w][v] = true.

    --  Adjacency-list : Maintain vertex-indexed array of lists. Each list contains all the vertices adjacent to the vertex represented by that array entry.

    --  In practice. Use adjacency-lists representation.

        --  Algorithms based on iterating over vertices adjacent to v.

        --  Real-world graphs tend to be sparse.

 

7.  Adjacency-list graph representation Java implementation :

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]; }
    }
}

 

8.  Design pattern for graph processing:

    --  Decouple graph data type from graph processing.

    --  Create a Graph object.

    --  Pass the Graph to a graph-processing routine.

    --  Query the graph-processing routine for information.

public class Paths {
    Paths(Graph G, int s) {...}  //find paths in G from source s
    boolean hasPathTo(int v)  {...}  //is there a path from s to v?
    Iterable<Integer> pathTo(int v)  {...}  //path from s to v; null if no such path
}

 

9.  Depth First Search

    --  Goal: Systematically search through a graph.

    --  Typical applications:

        --  Find all vertices connected to a given source vertex.

        --  Find a path between two vertices.

    --  To visit a vertex v :

        --  Mark vertex v as visited.

        --  Recursively visit all unmarked vertices adjacent to v.

    --  Implementation :

public class DepthFirstPaths
{
    private boolean[] marked;
    //edgeTo[v] = previous vertex on path from s to v
    private int[] edgeTo;
    private int s;

    public DepthFirstSearch(Graph G, int s)
    {
        int V = G.V();
        this.marked = new boolean[V];
        this.edgeTo = new int[V];
        this.s = s;
        dfs(G, s);
    }

    private void dfs(Graph G, int v)
    {
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w])
            {
                dfs(G, w);
                edgeTo[w] = v;
            }
    }

    public boolean hasPathTo(int v)
    { return marked[v]; }

    public Iterable<Integer> pathTo(int v)
    {
      if (!hasPathTo(v)) return null;
      Stack<Integer> path = new Stack<Integer>();
      for (int x = v; x != s; x = edgeTo[x])
        path.push(x);
path.push(s);
return path;
}
}

 

10.  DFS marks all vertices connected to s in time proportional to the sum of their degrees. After DFS, can find vertices connected to s in linear time and can find a path to s (if one exists) in time proportional to its length.

 

11.  Breadth First Search

    --  Intuition: examines vertices in increasing distance from s

    --  Typical application : find path from s to t that uses fewest number of edges.

    --  BFS from source vertex s :

        --  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.

    --  Implementation : 

 

public class BreadthFirstPaths
{
    private boolean[] marked;
    private int[] edgeTo;
    
    private void bfs(Graph G, int s)
    {
        Queue<Integer> q = new Queue<Integer>();
        q.enqueue(s);
        marked[s] = true;
        while (!q.isEmpty())
        {
            int v = q.dequeue();
            for (int w : G.adj(v))
            {
                if (!marked[w])
                {
                    q.enqueue(w);
                    marked[w] = true;
                    edgeTo[w] = v;
                }
            }
        }
    }
}

 

 

12.  BFS computes shortest paths (fewest number of edges) from s to all other vertices in a graph in time proportional to E + V.

 

13.  Connected Components:

    --  Vertices v and w are connected if there is a path between them.

    --  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.

    --  Goal: preprocess graph to answer queries of whether v is connected to w in constant time.

    --  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.

    --  Implementation:

 

public class CC
{
    private boolean[] marked;
    private int[] id; //id[v] = id of component containing v
    private int count; //number of components

    public CC(Graph G)
    {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for (int v = 0; v < G.V(); v++)
        {
            if (!marked[v])
            {
                dfs(G, v);
                count++;
            }
        }
    }

    public int count()
    { return count; }

    public int id(int v)
    { return id[v]; }

    private void dfs(Graph G, int v)
    {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v))
            if (!marked[w])
                dfs(G, w);
    }
}

 

 

14.  Graph-processing Problem :

    --  Is a graph bipartite (A bipartite graph is a graph whose vertices we can divide into two sets

such that all edges connect a vertex in one set with a vertex in the other set.) We can use DFS/BFS to color vertices with two different color if they are directly connected. If we found some edge that's connects two already visited vertices that have been colored the same color , then it's not a bipartite.

    --  Find a cycle : use DFS/BFS to visit the vertices , when we visit v , if an edge (v, w) with pathTo[v] != w, then there is a cycle.

    --  Find a (general) cycle that uses every edge exactly once. It's Eulerian tour , yes iff connected and all vertices have even degree.

    --  Find a cycle that visits every vertex exactly once. It's Hamiltonian cycle (NP-Complete problem)

    --  Are two graphs identical except for vertex names? Graph isomorphism is longstanding open problem

    --  Lay out a graph in the plane without crossing edges. Linear-time DFS-based planarity algorithm

discovered by Tarjan in 1970s (too complicated for most practitioners)