内容概要：
- DFS类的实现
- DFS求解连通分量
- DFS求解点对之间的一个路径
- DFS判定无环图和二分图
相关概念
深度优先遍历(DFS)，广度优先遍历(BFS)，(深度优先)前序遍历，中序遍历，(深度优先)后序遍历，层次遍历，无环图，二分图。
遍历的意义
每种数据结构都有遍历方式，这是取得其中数据的方式，图是一种数据结构。另外很多算法(图论)在本质上都是都是遍历的不同应用。
深度优先遍历
对比树的前序遍历与图的深度优先遍历：
preorder(root);
void preorder(TreeNode node){
if(node){
visit(node.val);
preorder(node.left);
preorder(node.right);
}
}
visited[0...V-1] = false;
dfs(0);
dfs(int v){
visited[v] = true;
visit(v);
for(int w: adj(v)){
if(!visited[w])
dfs(w);
}
}
本质上二者的逻辑是一样的，二叉树的遍历前序遍历其实就是一种深度优先遍历，相比于树，图因为每个顶点的相邻顶点个数不定，所以要对顶点的相邻顶点做循环并维护一个是否访问过某节点的记录数组。
树的前中后序这三种遍历都是深度优先遍历，相应的有图的深度优先前序遍历，和深度优先后序遍历，而图没有中序遍历，就像n叉树(n>2)也没有中序遍历一样。
深度优先遍历类(无向图)
import java.util.ArrayList;
// 无向无权图
public class GraphDFS {
private Graph G;
private boolean[] visited;
private ArrayList<Integer> pre = new ArrayList<>(); // 深度优先前序遍历
private ArrayList<Integer> post = new ArrayList<>(); // 深度优先后序遍历
public GraphDFS(Graph G){
this.G = G;
visited = new boolean[G.V()];
for(int v = 0; v < G.V(); v ++)
if(!visited[v])
dfs(v);
}
public Iterable<Integer> pre() { // ArrayList
// 返回深度优先前序遍历的结果
return pre;
}
public Iterable<Integer> post() { // ArrayList
// 返回深度优先后序遍历的结果
return post;
}
private void dfs(int v){
visited[v] = true;
pre.add(v);
for(int w: G.adj(v))
if(!visited[w])
dfs(w);
post.add(v);
}
public static void main(String args[]){
Graph g = new Graph("g.txt");
GraphDFS graphDFS = new GraphDFS(g);
System.out.println(graphDFS.post());
}
}
深度优先遍历是很多后续图论算法的基石。
DFS的应用
- 求图的连通分量
两点是否可达
两点间的一条路径
检测图中是否有环
二分图检测
寻找图中的桥和割点
寻找哈密尔顿路径
拓扑排序(有向图)
图的连通分量(无向图)
求解连通分量个数
- 连通分量个数，每个连通分量包含的顶点集合，两个顶点是否相连。
具体返回每个连通分量中包含的顶点：
方案1：dfs(v,list[i]);将不同连通分量的顶点添加到不同列表。
方案2：visited数组改为整型，初值置-1表示没有访问过，非负值标记属于哪个连通分量。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
// 无向无权图
public class CC {
private Graph G;
private int[] visited; // 标记顶点是否被访问以及属于哪个连通分量
private int cccount = 0; // 求连通分量个数
public CC(Graph G){
this.G = G;
visited = new int[G.V()];
for(int i = 0; i < visited.length; i ++)
visited[i] = -1;
for(int v = 0; v < G.V(); v ++)
if(visited[v] == -1) {
dfs(v, cccount);
cccount ++; // dfs(v, cccount ++);
}
}
private void dfs(int v, int ccid){// ConnectedComponent ID
visited[v] = ccid;
for(int w: G.adj(v))
if(visited[w] == -1)
dfs(w, ccid);
}
public int count(){
return cccount;
}
public ArrayList<Integer> getCC(){// 查看连通分量标记
// ArrayList<Integer> cc = new ArrayList<>(Arrays.asList(visited));
// ArrayList<Integer> cc = new ArrayList<>(visited.length);
// Collections.addAll(cc,visited); // 有错误
ArrayList<Integer> cc = new ArrayList<>();
for(int i = 0; i < visited.length; i ++)
cc.add(visited[i]);
return cc;
}
public ArrayList<Integer>[] components(){
// 返回各个连通分量
ArrayList<Integer>[] res = new ArrayList[cccount];
for(int i = 0; i < cccount; i ++)
res[i] = new ArrayList<>();
for(int v = 0; v < G.V(); v ++)
res[visited[v]].add(v);
return res;
}
public boolean isConnected(int v, int w){
// 判断两个顶点是否连接
G.validateVertex(v);
G.validateVertex(w);
return visited[v] == visited[w];
}
public static void main(String args[]){
Graph g = new Graph("g.txt");
CC cc = new CC(g);
System.out.println(cc.count());
System.out.println(cc.getCC());
ArrayList<Integer>[] comp = cc.components();
for(int ccid = 0; ccid < comp.length; ccid ++){
System.out.print(ccid + ": ");
for(int w: comp[ccid])
System.out.print(w + " ");
System.out.println();
}
}
}
求解单源路径(无向图)
求解路径
DFS时，两个顶点在同一连通分量表示有路径，从一点出发，记录经过的顶点，直到到达另一顶点这就是一条路径。具体做法就是记录每个顶点是从哪里来的，由于会有访问标记，所以这个值是唯一的，最后从终点到源点反推即得到路径。
import java.util.ArrayList;
import java.util.Collections;
// 无向无权图
public class SingleSourcePath{
private Graph G;
private int s;
private boolean[] visited;
private int pre[]; // 其实只用 pre 一个数组即可标记访问与否及路径信息
public SingleSourcePath(Graph G, int s){
// s是源顶点
G.validateVertex(s);
this.G = G;
this.s = s;
visited = new boolean[G.V()];
pre = new int[G.V()];
for(int i = 0; i < pre.length; i ++)
pre[i] = -1;
dfs(s, s);
}
private void dfs(int v, int parent){
// parent是v的上一个顶点
visited[v] = true;
pre[v] = parent;
for(int w: G.adj(v))
if(!visited[w])
dfs(w, v);
}
public boolean isConnectedTo(int t){
// 源点是否与 t 连通
G.validateVertex(t);
return visited[t];
}
public Iterable<Integer> path(int t){
// 返回记录的路径 s -> t
ArrayList<Integer> res = new ArrayList<>();
if(!isConnectedTo(t)) return res; // 没有路径
int cur = t;
while(cur != s){
res.add(cur);
cur = pre[cur];
}
res.add(cur); // 最后的源顶点
Collections.reverse(res);
return res;
}
public static void main(String args[]){
Graph g = new Graph("g.txt");
SingleSourcePath spath = new SingleSourcePath(g, 0);
System.out.println("0 -> 6: " + spath.path(6));
System.out.println("0 -> 5: " + spath.path(5));
}
}
由上述的单源路径不难得到任意两个点对之间的一条路径。
无向图环检测
深度优先遍历中如果一个被访问的顶点再次被访问到，且这个顶点不是它前一个节点，则说明图中存在环。
public class CycleDetection {
private Graph G;
private boolean hasCycle;
private boolean[] visited;
public CycleDetection(Graph G){
this.G = G;
visited = new boolean[G.V()];
for(int v = 0; v < G.V(); v ++)
if(!visited[v])
if(dfs(v, v)) {
hasCycle = true;
break;
}
}
private boolean dfs(int v, int parent){
visited[v] = true;
for(int w: G.adj(v))
if(!visited[w]) {
if (dfs(w, v))
return true;
}
else if(w != parent) // w 的邻点访问过且不是 w 的上一个顶点，则找到环
return true;
return false;
}
public boolean hasCycle(){
return hasCycle;
}
public static void main(String args[]){
Graph g = new Graph("g.txt");
CycleDetection cd = new CycleDetection(g);
System.out.println(cd.hasCycle());
}
}
二分图检测
二分图：顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，且两个子集内的顶点不相邻的图。
二分图例子
如上面两个图都是二分图，第一个比较容易看出，第二个与第一个拓扑同构也是二分图。
二分图检测可以通过染色操作完成，很容易证明如果用两种颜色对图中顶点进行染色，二分图最终每两个相邻顶点必不同色，同样，用两种颜色对图进行染色，如果可以每两个相邻顶点都不同色，则这个图是二分图。
// 无向无权图
public class BipartitionDetection {
private Graph G;
private boolean isBipartite = true;
private boolean[] visited;
private int[] colors; // 取值 0, 1 表示两种颜色
public BipartitionDetection(Graph G){
this.G = G;
visited = new boolean[G.V()];
colors = new int[G.V()];
for(int i = 0; i < G.V(); i ++)
colors[i] = -1; // 表示还没有被染色
for(int v = 0; v < G.V(); v ++)
if(!visited[v])
if(!dfs(v, 0))
isBipartite = false;
}
private boolean dfs(int v, int color){
// v 会被染色为 color
// 通过 v 检测是否是二分图
visited[v] = true;
colors[v] = color;
for(int w: G.adj(v)) {
if (!visited[w]) {
if (!dfs(w, 1 - color))// 邻点颜色相反
return false;
}
else if (colors[w] == colors[v])
return false;
}
return true;
}
public boolean isBipartite(){
return isBipartite;
}
public static void main(String args[]){
Graph g = new Graph("g.txt");
BipartitionDetection bd = new BipartitionDetection(g);
System.out.println(bd.isBipartite());
}
}
网友评论