Algorithm(四)：Graph Part I：有向无向图

1
2
3
4
5
6
7
8
9
public class Graph{
                   Graph(int V)            // create a V-vertex graph with no edges
                   Graph(In in)            // read a graph from input stream in
               int V()                     // number of vertices
               int E()                     // number of edges
              void addEdge(int v, int w)   // add edge v-w to this graph
   Iterable<Integer> adj(int v)            // vertices adjacent to v
            String toString()              // string representation
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class UndirectedGraph {
  private final int V;                    // number of vertices
  private int E;                          // number of edges
  private Bag<Integer>[] adj;             // adjacency lists
  
  public UndirectedGraph(int V){
      this.V = V;                         
      this.E = 0;                         
      adj = (Bag<Integer>[]) new Bag[V];  // Create array of lists.
      for (int v = 0; v < V; v++)         // Initialize all lists
          adj[v] = new Bag<Integer>();    //   to empty.
   }
  
   public UndirectedGraph(In in){
       this(in.readInt());                // Read V and construct this graph.
       int E = in.readInt();              // Read E.
       for (int i = 0; i < E; i++){       
             int v = in.readInt();        // Read a vertex,
             int w = in.readInt();        // read another vertex,
             addEdge(v, w);               // and add edge connecting them.
       }
    }
  
   public int V()  {  return V;  }
   public int E()  {  return E;  }
  
   public void addEdge(int v, int w){
       adj[v].add(w);                     // Add w to v’s list.
       adj[w].add(v);                     // Add v to w’s list.
       E++;
   }
  
   public Iterable<Integer> adj(int v){ 
       return adj[v];
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class DepthFirstPaths{                   // using depthFirstSearch to find path to s in graph G
   private boolean[] marked;                    // has dfs() been called for this vertex?
   private int[] edgeTo;                        // last vertex on know path to this vertex
   private final int s;                         // source
   public DepthFirstSearchPaths(Graph G, int s){
      marked = new boolean[G.V()];
      edgeTo = new int[G.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]) {
             edgetTo[w] = v;
             dfs(G, w);
         }
   }
   
   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;
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class BreadthFirstPaths{
   private boolean[] marked;                        // Is a shortest path to this vertex known?
   private int[] edgeTo;                            // last vertex on known path to this vertex
   private final int s;                             // source
   private int[] distTo;                            // distTo[v] = length of shortest s->v path

   public BreadthFirstPaths(Graph G, int s){
      marked = new boolean[G.V()];
      distTo = new int[G.V()];
      edgeTo = new int[G.V()];
      for (int v = 0; v < G.V(); v++)
        distTo[v] = INFINITY;
      this.s = s;
      bfs(G, s);
   }
   
   private void bfs(Graph G, int s){
      Queue<Integer> queue = new Queue<Integer>();
      marked[s] = true;                               // Mark the source
      distTo[s] = 0;
      queue.enqueue(s);                               // and put it on the queue.
      while (!queue.isEmpty()){
         int v = queue.dequeue();                     // Remove next vertex from the queue.
         for (int w : G.adj(v)){
            if (!marked[w]){                          // For every unmarked adjacent vertex,
                edgeTo[w] = v;                        // save last edge on a shortest path,
                distTo[w] = distTo[v] + 1;
                marked[w] = true;                     // mark it because path is known,
                queue.enqueue(w);                     // and add it to the queue.
            }
         }
      }
   }
   
   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;
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class CC{

   private boolean[] marked;
   private int[] id;
   private int count;
   
   public CC(Graph G){
      marked = new boolean[G.V()];
      id = new int[G.V()];
      for (int s = 0; s < G.V(); s++)
         if (!marked[s]){
             dfs(G, s);
             count++; 
        }
   }
   
   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);
   }
   
   public boolean connected(int v, int w){  
       return id[v] == id[w];  
   }
   
   public int id(int v) {  return id[v];  }
   public int count()   {  return count;  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Digraph{
     private final int V;
     private int E;
     private Bag<Integer>[] adj;
     
     public Digraph(int V){           //create a V-vertex digraph with no edges
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++)
           adj[v] = new Bag<Integer>();
     }
     
     public int V()  {  return V;  }      //number of vertices
     public int E()  {  return E;  }      //number of edges
     
     public void addEdge(int v, int w){     //add edge v->w to this digraph

        adj[v].add(w);
        // adj[w].add[v] 无向图需要加两次，有向图只能按方向加一次。
        E++;
     }
     
     public Iterable<Integer> adj(int v){  
      return adj[v];  }
     
     public Digraph reverse(){          //reverse of this Digraph
        Digraph R = new Digraph(V);
        for (int v = 0; v < V; v++)
           for (int w : adj(v))
              R.addEdge(w, v);
        return R; }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class DepthFirstOrder{
  
   private boolean[] marked;
   private Stack<Integer> reversePost;  // vertices in reverse postorder
   
   public DepthFirstOrder(Digraph G){
      reversePost   = new Stack<Integer>();
      marked  = new boolean[G.V()];
      for (int v = 0; v < G.V(); v++)
         if (!marked[v]) dfs(G, v);
   }
   
   private void dfs(Digraph G, int v){
      marked[v] = true;
      for (int w : G.adj(v))
         if (!marked[w])
            dfs(G, w);
      reversePost.push(v);
   }
   
   public Iterable<Integer> reversePost(){return reversePost;}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void dfs(Digraph G, int v){  
    onStack[v] = true;
    marked[v] = true;
    for(int w:G.adj(v)){
        //已经有环了，洗洗睡吧
        if(cycle != null) return;
        //未访问过则继续往下探索
        else if(!marked[w]){
            edgeTo[w] = v;
            dfs(G,w);
        //访问过并且处于当前DFS路径，有环！
        }else if onStack[w]{
            cycle = new Stack<Integer>();
            //记录环的情况
            for(int x=v;x!=w;x=edgeTo[x])
                cycle.push(x);
            cycle.push(x);
            cycle.push(v);
        }
    }
    //当前节点搜索完毕，换一条路径
    onStack[v] =false;
}

1
2
3
4
5
6
7
8
9
// components in undirected graph
public int connected(int v, int w){  
    return cc[v] == cc[w];
}

// strong components in directed graph
public int stronglyConnected(int v, int w){  
    return scc[v] == scc[w];
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class KosarajuSharirSCC{
  
  private boolean[] marked;     //reached vertices
  private int[] id;             //component identifiers
  private int count;            //number of strong components

  public KosarajuSharirSCC(Digraph G){
    marked = new boolean[G.V()];
    id = new int[G.V()];
    DepthFirstOrder order = new DepthFirstOrder(G.reverse());
    for (int s : order.reversePost())
      if (!marked[s]){  
        dfs(G, s); count++;
      }
  }
  
    private void dfs(Digraph G, int v){
       marked[v] = true;
       id[v] = count;
       for (int w : G.adj(v))
          if (!marked[w])
              dfs(G, w);
    }
    
    public boolean stronglyConnected(int v, int w){return id[v] == id[w];}
    public int id(int v){return id[v];}
    public int count(){return count;}
}