数据结构：手把手带你了解 ”图“ 所有知识！(含DFS、BFS）
数据结构：手把手带你了解 ”图“ 所有知识！(含DFS、BFS）
Carson.Ho
发布于 2020-09-15 10:02:07
发布于 2020-09-15 10:02:07
前言
本文主要讲解 数据结构中的图 结构，包括 深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树算法等，希望你们会喜欢。
目录
1. 简介
- 数据结构的中属于 圆形结构 的逻辑结构
- 具体介绍如下
2. 基础概念
- 在图的数据结构中，有许多基础概念，如 边类型、图顶点 & 边间的关系等等
- 具体请看下图
3. 类型
图的类型分为很多种，具体如下：
3.1 有向图 & 无向图
3.2 连通图
- 定义 图中任意顶点都是连通的图
- 具体相关概念 对于有向图 & 无向图，连通图的的具体概念又不同，具体如下
对于无向图：
对于有向图：
3.3 其余类型图
4. 存储结构
图的存储结构共有5种，具体请看下图
5. 图的遍历
5.1 定义
从图中某1顶点出发，遍历图中其余所有顶点 & 使每1个顶点仅被访问1次
5.2 遍历方式
深度优先遍历（DFS）、广度优先遍历（BFS）
5.3 具体介绍
5.3.1 深度优先遍历（ DFS ）
- 简介
- 算法示意图
- 具体实现：递归 & 非递归
此处图的存储结构 = 邻接矩阵
import java.util.Stack;
public class MyGraph {
/**
* 准备工作1：设置变量
*/
private int vexnum; // 存放图中顶点数量
private char[] vertices; // 存放结点数据
private int [][] arcs; // 存放图的所有边
private boolean[] visited;// 记录节点是否已被遍历
/**
* 准备工作2：初始化图的顶点数量、数据 & 边
*/
public MyGraph(int n){
vexnum = n;
vertices = new char[n];
visited = new boolean[n];
arcs = new int[n][n];
}
/**
* 图的深度优先遍历算法实现：递归
* 类似 前序遍历
*/
public void DFSTraverse(){
// 1. 初始化所有顶点的访问标记
// 即，都是未访问状态
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
// 2. 深度优先遍历顶点（从未被访问的顶点开始）
for(int i=0;i < vexnum;i++){
if(visited[i]==false){
// 若是连通图，只会执行一次
traverse(i); // ->>看关注1
}
}
}
/**
* 关注1：邻接矩阵的深度优先搜索递归算法
* 即，从第i个顶点开始深度优先遍历
*/
private void traverse(int i){
// 1. 标记第i个顶点已遍历
visited[i] = true;
// 2. （输出）访问当前遍历的顶点
visit(i);
// 3. 遍历邻接矩阵中第i个顶点的所有邻接顶点
for(int j=0;j<vexnum;j++){
// a. 若当前顶点的邻接顶点存在 & 未被访问，则递归 深度优先搜索 算法
if(arcs[i][j]==1 && visited[j]==false){
// b. 将当前顶点的邻接顶点作为当前顶点，递归 深度优先搜索 算法
traverse(j);
}
}
}
/**
* 辅助算法1：访问顶点值
*/
public void visit(int i){
System.out.print(vertices[i] + " ");
}
/**
* 图的深度优先遍历算法实现：非递归
* 原理：采用 栈实现
*/
public void DFSTraverse2(){
// 1. 初始化顶点访问标记
// 全部标记为：未访问
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
// 2. 创建栈
Stack<Integer> s = new Stack<Integer>();
for(int i=0 ; i<vexnum; i++){
// 3. 若该顶点未被访问
if(!visited[i]){
// 4. 入栈该顶点
s.add(i);
do{
// 出栈
int curr = s.pop();
// 如果该节点还没有被遍历，则遍历该节点并将子节点入栈
if(visited[curr]==false){
// 遍历并打印
visit(curr);
visited[curr] = true;
// 没遍历的子节点入栈
for(int j=vexnum-1; j>=0 ; j-- ){
if(arcs[curr][j]==1 && visited[j]==false){
s.add(j);
}
}
}
}while(!s.isEmpty());
}
}
}
/**
* 测试（递归 & 非递归）
*/
public static void main(String[] args) {
// 1. 初始化图的结构（顶点数量 = 9）
MyGraph g = new MyGraph(9);
// 2. 设置顶点数据
char[] vertices = {'A','B','C','D','E','F','G','H','I'};
g.setVertices(vertices);
// 3. 设置边
g.addEdge(0, 1);
g.addEdge(0, 5);
g.addEdge(1, 0);
g.addEdge(1, 2);
g.addEdge(1, 6);
g.addEdge(1, 8);
g.addEdge(2, 1);
g.addEdge(2, 3);
g.addEdge(2, 8);
g.addEdge(3, 2);
g.addEdge(3, 4);
g.addEdge(3, 6);
g.addEdge(3, 7);
g.addEdge(3, 8);
g.addEdge(4, 3);
g.addEdge(4, 5);
g.addEdge(4, 7);
g.addEdge(5, 0);
g.addEdge(5, 4);
g.addEdge(5, 6);
g.addEdge(6, 1);
g.addEdge(6, 3);
g.addEdge(6, 5);
g.addEdge(6, 7);
g.addEdge(7, 3);
g.addEdge(7, 4);
g.addEdge(7, 6);
g.addEdge(8, 1);
g.addEdge(8, 2);
g.addEdge(8, 3);
// 4. 执行 图的深度优先遍历：（递归 & 非递归）
System.out.println("深度优先遍历（递归）");
g.DFSTraverse();
System.out.println("深度优先遍历（非递归）");
g.DFSTraverse2();
}
/**
* 辅助算法1：添加边(无向图)
*/
public void addEdge(int i, int j) {
// 边的头尾不能为同一节点
if (i == j) return;
// 将邻接矩阵的第i行第j列的元素值置为1；
arcs[i][j] = 1;
// 将邻接矩阵的第j行第i列的元素值置为1；
arcs[j][i] = 1;
// 设置为1代表2顶点之间存在 边 （设置相等原因 = 邻接矩阵 是对称的）
}
/**
* 辅助算法2：设置顶点数据
*/
public void setVertices(char[] vertices) {
this.vertices = vertices;
}
}- 测试结果
深度优先遍历（递归）
A B C D E F G H I
深度优先遍历（非递归）
A B C D E F G H I- 特别注意 对于图的存储结构 = 邻接表实现，只需要将 存储边 的2维数组 改成链表即可。
- 图的存储结构 = 邻接矩阵 / 邻接表 的性能对比
5.3.2 广度优先遍历（BFS）
- 简介
- 算法示意图
- 具体流程
注：
G比I先访问的原因 = 用数组存储顶点时，G的下标 比I的下标小（按ABCDEFGHI顺序存储）
- 具体实现
非递归：采用队列
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class MyGraph {
/**
* 准备工作1：设置变量
*/
private int vexnum; // 存放图中顶点数量
private char[] vertices; // 存放结点数据
private int [][] arcs; // 存放图的所有边
private boolean[] visited;// 记录节点是否已被遍历
/**
* 准备工作2：初始化图的顶点数量、数据 & 边
*/
public MyGraph(int n){
vexnum = n;
vertices = new char[n];
visited = new boolean[n];
arcs = new int[n][n];
}
/**
* 广度优先搜索 算法实现
* 原理：非递归（采用队列）
*/
public void BFS(){
// 1. 初始化所有顶点的访问标记
// 即，设置为未访问状态
for (int i = 0; i < vexnum; i++) {
visited[i] = false;
}
// 2. 创建队列
Queue<Integer> q=new LinkedList<Integer>();
// 3. 对所有顶点做遍历循环（从第1个顶点开始）
// 若遍历完毕，则结束整个层序遍历
for(int i=0;i < vexnum;i++){
// 4. 若当前顶点未被访问，就进行处理
// 若当前顶点已被访问，则回到3进行判断
if( visited[i]==false ) {
// 5. （输出）访问当前顶点
visit(i);
// 6. 标记当前顶点已被访问
visited[i] = true;
// 7. 入队当前顶点
q.add(i);
// 8.判断当前队列是否为空
// 若为空则跳出循环，回到3进行判断
while(!q.isEmpty()) {
// 9. 出队队首元素 & 将出队的元素 赋值为 当前顶点
i = q.poll();
// 10. 遍历当前顶点的所有邻接点
// 若遍历完毕，则回到8判断
for(int j=0; j< vexnum ; j++){
// 11. 若当前顶点的邻接顶点存在 & 未被访问，则执行处理
// 否则回到10判断
if(arcs[i][j]==1 && visited[j]==false){
// 12. （输出）访问当前顶点的邻接顶点
visit(j);
// 13. 标记当前顶点的邻接顶点已被访问
visited[j] = true;
// 14. 入队当前顶点的邻接顶点
q.add(j);
}
}
}
}
}
}
/**
* 辅助算法1：访问该顶点
*/
public void visit(int i){
System.out.print(vertices[i] + " ");
}
/**
* 测试算法
*/
public static void main(String[] args) {
// 1. 初始化图的结构（顶点数量 = 9
MyGraph g = new MyGraph(9);
// 2. 设置顶点数据
char[] vertices = {'A','B','C','D','E','F','G','H','I'};
g.setVertices(vertices);
// 3. 设置边
g.addEdge(0, 1);
g.addEdge(0, 5);
g.addEdge(1, 0);
g.addEdge(1, 2);
g.addEdge(1, 6);
g.addEdge(1, 8);
g.addEdge(2, 1);
g.addEdge(2, 3);
g.addEdge(2, 8);
g.addEdge(3, 2);
g.addEdge(3, 4);
g.addEdge(3, 6);
g.addEdge(3, 7);
g.addEdge(3, 8);
g.addEdge(4, 3);
g.addEdge(4, 5);
g.addEdge(4, 7);
g.addEdge(5, 0);
g.addEdge(5, 4);
g.addEdge(5, 6);
g.addEdge(6, 1);
g.addEdge(6, 3);
g.addEdge(6, 5);
g.addEdge(6, 7);
g.addEdge(7, 3);
g.addEdge(7, 4);
g.addEdge(7, 6);
g.addEdge(8, 1);
g.addEdge(8, 2);
g.addEdge(8, 3);
// 4. 执行 图的广度优先遍历（非递归）
System.out.print("广度优先遍历（非递归）：");
g.BFS();
}
/**
* 辅助算法1：添加边(无向图)
*/
public void addEdge(int i, int j) {
// 边的头尾不能为同一节点
if (i == j) return;
// 将邻接矩阵的第i行第j列的元素值置为1；
arcs[i][j] = 1;
// 将邻接矩阵的第j行第i列的元素值置为1；
arcs[j][i] = 1;
// 设置为1代表2顶点之间存在 边 （设置相等原因 = 邻接矩阵 是对称的）
}
/**
* 辅助算法2：设置顶点数据
*/
public void setVertices(char[] vertices) {
this.vertices = vertices;
}
}- 执行结果
广度优先遍历（非递归）：A B F C G I E D H5.4 遍历方式对比
6. 最小生成树
本节主要讲解 图中的 最小生成树
6.1 定义
构造 连通网图 的最小成本生成树
- 网图：带有权值的图
- 最小成本：用（n-1）条边将 含n个顶点的连通图 连接起来 & 使得权值和最小
6.2 寻找最小生成树的算法
- 主要包括：（
Prim）普利姆算法 & （Kruskal）克鲁斯卡尔算法 - 具体介绍如下
6.2.1 （Prim）普利姆算法
- 算法概述
- 算法原理流程示意图
- 举例说明
6.2.2（Kruskal）克鲁斯卡尔算法
- 算法概述
6.3 算法对比
7. 最短路径
7.1 定义
- 对于非网图（无权值），最短路径 = 两顶点间经过的边数最少的路径
- 对于网图（有权值）：最短路径 = 两顶点间经过的边上权值和最少的路径
第1个顶点 = 源点、第2个顶点 = 终点
7.2 需解决的问题
从源点 -> 其余各顶点的最短路径
7.3 寻找最短路径 算法
- 主要包括：迪杰斯特拉算法
（Dijkstra）、弗洛伊德算法（Floyd） - 具体介绍如下
8. 总结
- 本文主要讲解了数据结构中的图
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-09-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。