vlambda博客
学习文章列表

一起玩转图论算法之二:图的深度优先遍历

1. 什么是图论





图论(英语:Graph theory),是组合数学的一个分支,和其他数学分支,如群论、矩阵论、拓扑学有着密切关系。是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物,连接两顶点的边则用于表示两个事物间具有这种关系。


图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决,因此普遍认为欧拉是图论的创始人。


图论的研究对象相当于一维的单纯复形。


---维基百科的定义


一起玩转图论算法之二:图的深度优先遍历



2. 图的两种形式遍历

所谓图的遍历(graph traversal),也称为搜索(search),就是从图中某个顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次。遍历可以采取两种方法进行:深度优先搜索(DFS,depth first search)

广度优先搜索(BFS,breadth first search)


3. 图的深度优先遍历顺序

深度优先搜索是一个递归过程,有回退过程。DFS 算法的思想是:对一个无向连通图,在访问图中某一起始顶点 v 后,由 v 出发,访问它的某一邻接顶点w1再从w1出发,访问与w1邻接但还没有访问过的顶点w2;然后再从w2出发,进行类似的访问;…;如此进行下去,直至到达所有邻接顶点都被访问过的顶点u为止;接着,回退一步,回退到前一次刚访问过的顶点,看

是否还有其它没有被访问过的邻接顶点,如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再回退一步进行类似的访问。重复上述过程,直到该连通图中所有顶点都被访问过为止。

一起玩转图论算法之二:图的深度优先遍历


深度优先遍历的递归的遍历形式:

一起玩转图论算法之二:图的深度优先遍历

一起玩转图论算法之二:图的深度优先遍历

一起玩转图论算法之二:图的深度优先遍历


4. 图的深度优先遍历伪代码

树的前序遍历,与图的深度优先遍历的比较:

一起玩转图论算法之二:图的深度优先遍历


5. 实现图的深度优先遍历

连通图的深度优先遍历

-结合上述的伪代码

package graphDFS;
import java.util.ArrayList;

public class GraphDFS { // 创建一个数组, private ArrayList<Integer> res = new ArrayList<>(); // 输出最后深度优先遍历的结果 private boolean[] visited; private Graph graph; public GraphDFS(Graph graph) { this.graph = graph; visited = new boolean[graph.V()]; // 结点的数量 dfs(0); } private void dfs(int v) { visited[v] = true; res.add(v); for (int w: graph.adj(v)) { // 遍历该节点的相邻结点 if (! visited[w]) dfs(w); } } public Iterable<Integer> res(){ return res; }
public static void main(String[] args) { Graph graph = new Graph("g2.txt"); GraphDFS graphDFS = new GraphDFS(graph); System.out.println(graphDFS.res());// [0, 1, 3, 2, 6, 5, 4] }
}

6. 遍历图的深度优先遍历的改进

如果不是联通图的话,孤立的结点将不会遍历。

-结合上述的伪代码

一起玩转图论算法之二:图的深度优先遍历

package graphDFS;
import java.util.ArrayList;

public class GraphDFS { // 创建一个数组, private ArrayList<Integer> res = new ArrayList<>(); // 输出最后深度优先遍历的结果 private boolean[] visited; private Graph graph; public GraphDFS(Graph graph) { this.graph = graph; visited = new boolean[graph.V()]; // 结点的数量 //dfs(0); // 改进的地方:对每一个结点进行遍历 for (int v = 0; v < graph.V(); v++) { if (!visited[v]) { dfs(v); } } } private void dfs(int v) { visited[v] = true; res.add(v); for (int w: graph.adj(v)) { // 遍历该节点的相邻结点 if (! visited[w]) dfs(w); } } public Iterable<Integer> res(){ return res; }
public static void main(String[] args) { Graph graph = new Graph("g2.txt"); GraphDFS graphDFS = new GraphDFS(graph); System.out.println(graphDFS.res());// [0, 1, 3, 2, 6, 5, 4] }
}





点击查看往期内容回顾

1. 



END



一起玩转图论算法之二:图的深度优先遍历

免费分享程序员面经、机器学习、编程语言等,

1300G互联网视频、书籍资源,各种干货。

生活不止于编程,爱编程更爱生活。