温习Algs4 (三):无向图, 搜索和连通分量

我会带着你远行 2022-04-12 04:08 220阅读 0赞

### 无向图, 搜索和连通分量 ###

*  无向图
 *   *  Graph.java
 *  搜索
 *   *  Visitor.java
     *  Search.java
 *  深度优先搜索
 *   *  DepthFirstSearch.java
 *  广度优先遍历
 *   *  BreadthFirstSearch.java
 *  连通分量
 *   *  CC.java
 *  总结

# 无向图 #

对于一般算法题来说图的实现方式是邻接矩阵, 但是对于稀疏图来说用邻接表来实现比较实惠一点.  
图的API多种多样, 我这里实现的API有:

1.  添加边
2.  获得该图的顶点数和边数
3.  遍历一个点的所有邻接点
4.  获得一个点的degree

## Graph.java ##

/****************************************************************************** * Compilation: javac Graph.java * Execution: java Graph * Author: Chenghao Wang ******************************************************************************/
    
    import java.util.Scanner;
    
    public class Graph { 
        private int vertexCount;
        private int edgeCount;
        private Bag<Integer>[] adj;
        private int[] degree;
    
        Graph() {  }
    
        Graph(int v) { 
            vertexCount = v;
            edgeCount = 0;
            adj = (Bag<Integer>[]) new Bag[v];
            degree = new int[v];
            for (int i = 0; i < v; i++) { 
                adj[i] = new Bag<Integer>();
            }
        }
    
        Graph(Scanner scan) { 
            this(scan.nextInt());
            int e = scan.nextInt();
            for (int i = 0; i < e; i++) { 
                int j = scan.nextInt();
                int k = scan.nextInt();
                addEdge(j, k);
            }
        }
    
        public int V() { 
            return vertexCount;
        }
    
        public int E() { 
            return edgeCount;
        }
    
        public void addEdge(int v, int w) { 
            adj[w].add(v);
            adj[v].add(w);
            edgeCount++;
            degree[w]++;
            degree[v]++;
        }
    
        public Iterable<Integer> adj(int v) { 
            return adj[v];
        }
    
        public String toString() { 
            StringBuilder sb = new StringBuilder();
            sb.append("<graph>\n");
            for (int i = 0; i < vertexCount; i++) { 
                for (int v : adj[i]) { 
                    if (v < i) { 
                        continue;
                    }
                    sb.append(" " + i + " - " + v + "\n");
                }
            }
            sb.append("</graph>");
            return sb.toString();
        }
    
        public int degree(int v) { 
            return degree[v];
        }
    }

# 搜索 #

搜索即遍历图的所有顶点, 分为深度优先搜索和广度优先搜索, 因为二者具有共性, 所以我这里实现一个抽象类作为他们的父类, 以及一个用来定制遍历代码的辅助类 (java中没有函数指针, 所以用类来代替).  
Search支持的操作只有检查某一点是否被访问过.

## Visitor.java ##

/****************************************************************************** * Compilation: javac Visitor.java * Execution: java Visitor * Author: Chenghao Wang ******************************************************************************/
    
    public abstract class Visitor { 
        public abstract void visit(Graph g, int v);
    }

## Search.java ##

/****************************************************************************** * Compilation: javac Search.java * Execution: java Search * Author: Chenghao Wang ******************************************************************************/
    
    public class Search { 
        protected boolean[] mark;
        protected Graph g;
        protected Visitor visitor;
    
        Search() {  }
    
        Search(Graph g, int start) { 
            this(g, start, null);
        } 
    
        Search(Graph g, int start, Visitor visitor) { 
            mark = new boolean[g.V()];
            this.g = g;
            this.visitor = visitor;
        } 
    
        public boolean mark(int v) { 
            return mark[v];
        }
    
        public String toString() { 
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < mark.length; i++) { 
                if (!mark[i]) continue;
                sb.append(i + " ");
            }
            return sb.toString();
        }
    }

# 深度优先搜索 #

英文名 DepthFirstSearch 即 *DFS*. 出于简便性我这里采用递归调用的方式实现.

## DepthFirstSearch.java ##

/****************************************************************************** * Compilation: javac DepthFirstSearch.java * Execution: java DepthFirstSearch * Author: Chenghao Wang ******************************************************************************/
    
    public class DepthFirstSearch extends Search { 
    
        DepthFirstSearch() {  }
    
        DepthFirstSearch(Graph g, int start) { 
            this(g, start, null);
        } 
    
        DepthFirstSearch(Graph g, int start, Visitor visitor) { 
            super(g, start, visitor);
            dfs(start);
        } 
    
        private void dfs(int v) { 
            mark[v] = true;
            if (visitor != null) { 
                visitor.visit(g, v);
            }
            for (int next : g.adj(v)) { 
                if (mark[next]) continue;
                dfs(next);
            }
        }
    }

# 广度优先遍历 #

英文名是 BreadthFirstSearch 即 *BFS*, 其代码实现需要之前写到的Queue数据结构.

## BreadthFirstSearch.java ##

/****************************************************************************** * Compilation: javac BreadthFirstSearch.java * Execution: java BreadthFirstSearch * Author: Chenghao Wang ******************************************************************************/
    
    public class BreadthFirstSearch extends Search { 
    
        BreadthFirstSearch() {  };
    
        BreadthFirstSearch(Graph g, int start) { 
            this(g, start, null);
        }
    
        BreadthFirstSearch(Graph g, int start, Visitor visitor) { 
            super(g, start, visitor);
    
            Queue<Integer> queue = new Queue<Integer>();
            mark[start] = true;
            queue.enqueue(start);
    
            while (!queue.isEmpty()) { 
                int v = queue.dequeue();
                if (visitor != null) { 
                    visitor.visit(g, v);
                }
                for (int w : g.adj(v)) { 
                    if (mark[w]) continue;
                    mark[w] = true;
                    queue.enqueue(w);
                }
            }
        }
    }

# 连通分量 #

英文名是 ConnectedComponent 即 *CC*, 实现方法很简单, 即用DFS或BFS对所有点进行搜索, 每次搜索都会生成一个新的连通分量. 我这里支持的操作有:

1.  判断两点是否相连
2.  连通分量的数量
3.  查询某一点对应的ID值 (0 ~ N-1)
4.  返回某一ID对应的所有点

## CC.java ##

/****************************************************************************** * Compilation: javac CC.java * Execution: java CC * Author: Chenghao Wang ******************************************************************************/
    
    public class CC { 
        private boolean[] mark;
        private Vector<Bag<Integer>> components;
        private int[] id;
        private int currentId;
    
        CC(Graph g) { 
            mark = new boolean[g.V()];
            id = new int[g.V()];
            components = new Vector<Bag<Integer>>();
            currentId = 0;
    
            Visitor visitor = new Visitor() { 
                public void visit(Graph g, int v) { 
                    mark[v] = true;
                    id[v] = currentId;
                    components.get(currentId).add(v);
                }
            };
    
            for (int i = 0; i < g.V(); i++) { 
                if (mark[i]) continue;
                components.add(new Bag<Integer>());
                new DepthFirstSearch(g, i, visitor);
                currentId++;
            }
        }
    
        public boolean connected(int v, int w) { 
            return id[v] == id[w];
        }
    
        public int count() { 
            return components.size();
        }
    
        public int id(int v) { 
            return id[v];
        }
    
        public Iterable<Integer> component(int i) { 
            return components.get(i);
        }
    }

# 总结 #

无向图的相关算法相比于有向图更为简单, 但是一个难点是**找出图中所有的环**, 该算法我会另起一篇博客介绍.