15、数据结构与算法 - 实战：图
1. 图概念 - 多对多关系
提出背景
1、 线性表只能局限于一个直接前驱、直接后继的关系**（一对一关系）；
2、 树只能局限于一个父节点的关系（一对多关系）**；
专有名词
1、 边：两个结点之间的连接；
2、 结点（顶点）：可以具有零个或多个相邻元素；
3、 无（有）向图：顶点之间的连接没有（有）方向-即边没有方向；
4、 带权图（网）：边带数值的图；
5、 图的表示；
①：数组形式 - 邻接矩阵
②：数组+链表形式 - 邻链表
无向图 - 数据结构
有向图 - 数据结构
带权图（也称网） - 数据结构
1.1 图的表式
1.1.1 矩阵 - 数组
缺点：浪费太多的空间 - 标记某个结点与图中所有结点的关系
1.1.2 邻接表 - 数组+链表
优势：只记录某个结点与该结点有联系的结点信息
2. 代码
2.1 矩阵
2.1.1 基本类创建#
/**
* @Classname UndirectedWeightGraph
* @Description
* @Date 2022/4/16 13:32
* @Created by lrc
*/
//无向带权图
public class UndirectedWeightGraph {
//存储结点
ArrayList<String> vertexs;
// 存储结点之间的权值 - 结点之间的关系 -- 矩阵
int[][] edges;
// 存储图中边的个数
int numOfEdges;
//存储是否遍历过的节点信息 false未遍历 true已经遍历过
boolean[] isVisable;
public static void main(String[] args) {
//1， 结点信息
String[] vertexs = {
"v1", "v2", "v3", "v4"};
Integer n = vertexs.length;
// 2. 创建带5个结点的无序带权图
UndirectedWeightGraph graph = new UndirectedWeightGraph(n);
// 3. 添加结点
for(String vertex : vertexs) {
graph.insertVertex(vertex);
}
// 4. 添加结点之间的权值 - 这里的权值1仅表示两结点之间有连接关系
graph.insertWeight(0,1, 1);
graph.insertWeight(0,2, 1);
graph.insertWeight(1,2, 1);
graph.insertWeight(1,3, 1);
// 5. 显示图的矩阵
//System.out.println(graph.getGraph());
graph.showGrpah();
}
//初始化 - 结点个数
UndirectedWeightGraph(int vertexsNum) {
this.vertexs = new ArrayList<>(vertexsNum);
this.edges = new int[vertexsNum][vertexsNum];
this.numOfEdges = 0;
}
//获取边的个数
public int getNumOfEdges() {
return numOfEdges;
}
//获取结点个数
public int getVertexsNum() {
return this.vertexs.size();
}
//添加新结点
public void insertVertex(String vertex) {
this.vertexs.add(vertex);
}
//获取两结点之间的边的权值 "A结点表示0" "B节点表示1"
public int getWeight(int firstVertex, int secondVertext) {
return edges[firstVertex][secondVertext];
}
//获取矩阵 - 即把数组Edges权值图打印出来
public String getGraph() {
return Arrays.deepToString(edges);
}
//显示矩阵
public void showGrpah() {
for(int[] edgeWeight : edges) {
System.out.println(Arrays.toString(edgeWeight));
}
}
//添加结点之间的关系 - 即权值 - 因为无向图的关系必须赋值数组中两个元素相同的权值
public void insertWeight(int firstVertex, int secondVertext, int weight) {
edges[firstVertex][secondVertext] = weight;
edges[secondVertext][firstVertex] = weight;
numOfEdges++;
}
}
2.1.2 遍历图的结点#
遍历
深度优先遍历（Depth First Search）
广度优先遍历（Board First Search）
2.1.2.1 深度优先遍历（DFS）#
DFS思想：访问到某个结点，就以某个结点访问该结点的第一个邻接结点 —纵向挖掘访问
找到W
未被访问
访问过
未找到W
1、 访问并输出初始结点V，并标记该V结点已被访问；
2、 查找V结点某个邻接结点W；
3、 是否找到W？；
是否W已经被访问过？
对W进行深度遍历 - 递归进入该结点（即V为W，重复1、2、3步骤）
查找V的下一个邻接结点 - 从步骤3开始
未找到
返回到上一层递归
深度优先遍历代码
写法1
//得到第一个邻接点的小标 - 找到返回W的小标，未找到返回-1 - 下一个小标的结点
public int getFirstNeigbor(int index) {
for(int j = 0; j <vertexs.size(); j++) {
if(edges[index][j] > 0) {
return j;
}
}
return -1;
}
//根据前一个邻结点的小标来获取一个邻接点- 找到返回新的W的小标，未找到返回-1
public int getNextNeigbor(int index, int w) {
for(int j = w+1; j<vertexs.size(); j++ ) {
if(edges[index][j] > 0) {
return j;
}
}
return -1;
}
//深度优先遍历
public void dfs(boolean[] isVisited, int i) {
System.out.println(vertexs.get(i));
isVisited[i] = true;
int w = getFirstNeigbor(i);
while(w != -1) {
if(!isVisited[w]) {
dfs(isVisited, w);
}
w = getNextNeigbor(i, w);
}
}
//重载深度优先算法
public void dfs() {
for(int i = 0; i<getVertexsNum(); i++) {
//如果未访问过，则从该结点开始访问
if(isVisable[i] == false) {
dfs(i);
}
}
//遍历完后修改回原来的状态
for(int i = 0; i < isVisable.length; i++) {
isVisable[i] = false;
}
}
写法2
//得到下一个邻接结点 - 寻找当前结点未被访问的邻接结点
public int getNextNeigbor2(int index) {
for(int j = 0; j<isVisable.length; j++) {
if(edges[index][j] > 0 && isVisable[j] == false) {
return j;
}
}
return -1;
}
//深度优先遍历2
public void dfs2(int i) {
System.out.println(vertexs.get(i));
isVisable[i] = true;
int w = getNextNeigbor2(i);
while(w != -1) {
dfs2(w);
w = getNextNeigbor2(i);
}
}
//重载深度优先算法
public void dfs2() {
//图可能存在没有变得结点 - 故需要遍历所有结点
for(int i = 0; i<getVertexsNum(); i++) {
//如果未访问过，则从该结点开始访问
if(isVisable[i] == false) {
dfs2(i);
}
}
//遍历完后修改回原来的状态
for(int i = 0; i < isVisable.length; i++) {
isVisable[i] = false;
}
}
测试
public static void main(String[] args) {
//1， 结点信息
String[] vertexs = {
"v1", "v2", "v3", "v4"};
Integer n = vertexs.length;
// 2. 创建带5个结点的无序带权图
UndirectedWeightGraph graph = new UndirectedWeightGraph(n);
// 3. 添加结点
for (String vertex : vertexs) {
graph.insertVertex(vertex);
}
// 4. 添加结点之间的权值 - 这里的权值1仅表示两结点之间有连接关系
graph.insertWeight(0, 1, 1);
graph.insertWeight(0, 2, 1);
graph.insertWeight(1, 2, 1);
graph.insertWeight(1, 3, 1);
// 5. 显示图的矩阵
//System.out.println(graph.getGraph());
graph.showGrpah();
graph.dfs2();
}
流程讲解
1. 首先dfs2( 0 ) 打印V1
2. 寻找与V1相邻并且未访问过的邻结点 找到V2即 1
3. 进入递归 dfs(1) 打印V2
4. 寻找与V2相邻并且未访问过的邻结点 找到V3即 2
5. 进入递归 dfs(2) 打印V3
6. 寻找与V3相邻并且未访问过的邻结点 未找到 退出dfs(2)这个递归 返回到dfs(1)这个递归
7. 寻找与V2相邻并且未访问过的邻结点 找到V4即 3
8. 进入递归 dfs(3) 打印V4
9. 寻找与V4相邻并且未访问过的邻结点 未找到 退出dfs(3)这个递归 返回到dfs(1)这个递归
10. 寻找与V2相邻并且未访问过的邻结点 未找到 退出dfs(1)这个递归 返回到dfs(0)这个递归
11. 寻找与V1相邻并且未访问过的邻结点 未找到 退出dfs(0) 结束函数
2.1.2.2 广度优先遍历（BFS）- 分层搜索#
BFS思想：从队列弹出的结点为基准，访问该结点的所有未被访问的邻结节点，并将其放入队列中。如果该弹出的结点所有邻接结点被访问完，则从队列弹出一个结点，重复前者动作
//得到下一个邻接结点
public int getNextNeigbor2(int index) {
for (int j = 0; j < isVisable.length; j++) {
if (edges[index][j] > 0 && isVisable[j] == false) {
return j;
}
}
return -1;
}
public void bfs(int i) {
// 创建队列
LinkedList<Integer> queue = new LinkedList();
//将i入队
queue.addLast(i);
//从队列中获取头结点
int u = queue.removeFirst();
// 打印并输出结点信息
System.out.println(this.getVertexByIndex(i));
isVisable[u] = true;
//以弹出结点读出所有该结点的邻接结点
while(true) {
//获取u的未被访问的邻接结点
int w = getNextNeigbor2(u);
if(w != -1) {
//打印邻接结点并将其放入队列中，并标记已经被访问
System.out.println(getVertexByIndex(w));
isVisable[w] = true;
queue.addLast(w);
//如果当前结点已经遍历过所有其邻接结点，则从队列中弹出一个结点，并访问该结点所有邻接结点
}else {
// 如果队列无元素可弹，结束循环
if(queue.size() == 0) {
break;
}
u = queue.removeFirst();
}
}
}
//重载广度优先遍历
public void bfs() {
//所有结点必须遍历 - 因为存在没有边的结点
for(int i = 0; i < getVertexsNum(); i++) {
if( isVisable[i] == false) {
bfs(i);
}
}
//恢复遍历前的状态
for(int i = 0; i < isVisable.length; i++) {
isVisable[i] = false;
}
}
2.1.2.3 案例讲解#
#深度优先遍历DFS
1 -> 2 -> 4 -> 8 -> 5 -> 3 -> 6 -> 7
#广度优先遍历BFS
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8