图的深度优先遍历、联通分量与寻路
深度优先遍历对有向图和无向图都可以使用
一、图的深度优先遍历
深度优先遍历.png
如上图案例所示，深度优先遍历遍历过的节点将不会再次遍历，上述案例优先遍历的过程为0、1、2、5、3、4、6
二、联通分量
联通分量就是在一个图中相互不连接的独立的部分，联通分量与联通分量没有一条边相连
联通分量.png
如上就有三个联通分量
三、深度优先与计算联通分量代码实现
- 实现代码
import java.util.Iterator;
/**
* @author Liucheng
* @since 2019-10-13
*/
public class Components {
private Graph graph; // 图的引用
private boolean[] visited; // 保存被访问过的节点
private int count; // 记录联通分量个数
private int[] id; // 每个节点所对应的联通分量标记
/**
* 构造函数，求出无权图的联通分量
*/
public Components(Graph graph) {
// 初始化
this.graph = graph;
this.visited = new boolean[graph.V()];
this.id = new int[graph.V()];
this.count = 0;
for (int i = 0; i < graph.V(); i++) {
id[i] = -1;
}
// 求图的联通分量
for (int i = 0; i < graph.V(); i++) {
if (!this.visited[i]) {
this.dfs(i);
count ++;
}
}
}
/**
* 图的深度优先遍历,遍历一个节点的所有邻边
*/
void dfs(int v) {
System.out.print(v + " ");
// 记录对应的联通分量
id[v] = count;
Iterator<Integer> iterator = graph.adj(v).iterator();
visited[v] = true;
while (iterator.hasNext()) {
Integer next = iterator.next();
if (!visited[next]) {
this.dfs(next);
}
}
}
/**
* 返回联通分量的值
*/
public int count() {
return count;
}
/**
* 查询点v和点w是否联通
*/
public boolean isConnect(int v, int w) {
assert v >= 0 && v < graph.V();
assert w >= 0 && w < graph.V();
return id[v] == id[w];
}
/**
* 案例测试
* @param args
*/
public static void main(String[] args) {
int[][] data = {
{0, 1}, {0, 2}, {0, 5}, {0, 6},
{3, 4}, {3, 5},
{4, 5}, {4, 6},
};
// 测试稠密图
Graph dense = new DenseGraph(7, false);
for (int[] pare : data) {
dense.addEdge(pare[0], pare[1]);
}
dense.show();
Components componentsD = new Components(dense);
System.out.println("\n\\~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
// 测试稀疏图
Graph sparse = new SparseGraph(7, false);
for (int[] pare : data) {
sparse.addEdge(pare[0], pare[1]);
}
sparse.show();
Components componentsS = new Components(sparse);
System.out.println(componentsS.isConnect(3, 6));
}
}
- 运行结果
0 1 1 0 0 1 1
1 0 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 1 1 0
0 0 0 1 0 1 1
1 0 0 1 1 0 0
1 0 0 0 1 0 0
0 1 2 5 3 4 6
\~~~~~~~~~~~~~~~~~~~~~~~~~~~~
vertex 0: 1 2 5 6
vertex 1: 0
vertex 2: 0
vertex 3: 4 5
vertex 4: 3 5 6
vertex 5: 0 3 4
vertex 6: 0 4
0 1 2 5 3 4 6 true
三、寻路
此方法只能找到最先找到的路径！
- 寻路实现
import java.util.Stack;
import java.util.Vector;
/**
* @author Liucheng
* @since 2019-10-13
*/
public class Path {
private Graph G; // 图的引用
private int s; // 起始点
private boolean[] visited; //记录dfs过程中节点是否被访问
private int[] from; // 记录路径, from[i]表示查找的路径上i的【上一个节点】
/**
* 构造函数,寻路算法，寻找图graph从s点到其他点的路径
*/
public Path(Graph graph, int s) {
assert s >= 0 && s < G.V();
// 初始化
this.G = graph;
this.visited = new boolean[G.V()];
this.from = new int[G.V()];
this.s = s;
// 记录寻路的节点初始化为-1
for (int i = 0; i < G.V(); i++) {
this.from[i] = -1;
}
// 寻路算法
dfs(s);
}
/**
* 深度优先遍历
*/
private void dfs(int v) {
visited[v] = true;
for (Integer i : G.adj(v)) {
if (!visited[i]) {
from[i] = v;
dfs(i);
}
}
}
/**
* 查询从s点到w点是否有路径
*/
public boolean hasPath(int w) {
assert w >= 0 && w < G.V();
return visited[w];
}
/**
* 查询从s点到w点的路径，存放在vec中
*/
public Vector<Integer> path(int w) {
// 判断w是否被遍历过(在同一个联通分量上)
assert hasPath(w);
Stack<Integer> s = new Stack<>();
// 通过from数组逆向查找从s到w的路径，存放到栈中
int p = w;
// 记录寻路节点的默认值为-1
while (p != -1) {
s.push(p);
p = from[p];
}
// 从栈中依次取出元素，获得顺序的从s到w的路径
Vector<Integer> res = new Vector<>();
while (!s.empty()) {
res.add(s.pop());
}
return res;
}
/**
* 打印出从s点到w点的路径
*/
public void showPath(int w) {
Vector<Integer> vec = path(w);
for( int i = 0 ; i < vec.size() ; i ++ ){
System.out.print(vec.elementAt(i));
if( i == vec.size() - 1 ) {
System.out.println();
} else {
System.out.print(" -> ");
}
}
}
/**
* 测试寻路算法
*/
public static void main(String[] args) {
String filename = Thread.currentThread().getContextClassLoader()
.getResource("testG.txt").getPath();
SparseGraph g = new SparseGraph(7, false);
ReadGraph readGraph = new ReadGraph(g, filename);
g.show();
System.out.println();
Path path = new Path(g,0);
System.out.println("Path from 0 to 6 : ");
path.showPath(6);
}
}
- 测试结果
vertex 0: 1 2 5 6
vertex 1: 0
vertex 2: 0
vertex 3: 4 5
vertex 4: 3 5 6
vertex 5: 0 3 4
vertex 6: 0 4
Path from 0 to 6 :
0 -> 5 -> 3 -> 4 -> 6
四、图的深度优先遍历的复杂度分析
- 稀疏图（邻接表）：
- O(V + E) 表示点的个数加上边的个数
- 稠密图（邻接矩阵 ：
- O(V^2) 表示边的次方，因为稠密图计算每一个节点相邻不为空的所有情况
深度优先遍历可以检测图中是否有环 无向图中查找环无意义，在有向图中查找环才有意义
