01数据结构-图的邻接矩阵和遍历
01数据结构-图的邻接矩阵和遍历
- 1.图的遍历
- 1.1深度优先遍历
- 1.2广度优先搜索
- 2.邻接矩阵的代码实现
1.图的遍历
1.1深度优先遍历
深度优先搜索的过程类似于树的先序遍历，首先从例子中体会深度优先搜索，例如下图1是个无向图，采用深度优先算法遍历这个图的过程是：
图1
- 1.首先任意位置找一个未遍历过的顶点，例如从v1开始，由于v1率先访问过了，所以，需要标记v1的状态为访问过；
- 2.然后遍历v1的邻接点，例如访问v2,并做标记，然后访问v2的邻接点，例如v4（做标记）,然后v8，然后v5；
- 3.当继续遍历v5的邻接点时，根据之前的标记显示，所有邻接点都被访问过了。此时，从v5回到v8，看v8是否有未被访问过的邻接点，如果没有，继续回到v4,v2,v1;
- 4.通过查看v1,找到一个未被访问过的顶点v3,继续遍历,然后访问v3，邻接点v6,然后v7。
- 5.由于v7没有未被访问过的邻接点，所以退回到v6,继续退回到v3,最后到达v1,发现没有未被访问的；
- 6.结束遍历。
这里需要引入已访问的数组Visited，用来标识哪些点被访问了。因为图中的元素比时n:m，遍历的时候如果不引入会出现同一个顶点遍历多次的情况。
1.2广度优先搜索
广度优先搜索的过程类似于树的广度优先搜索，首先从例子中体会广搜，例如图1是个无向图，采用广搜算法遍历这个图的过程是：
- 1.首先任意位置找一个未遍历过的顶点，例如v1,在看到这个v1后，把这个顶点的所有邻接点v2,v3，放进队列中,标记v1的状态为访问过；
- 2.v1访问后访问v2,把v2的所有邻接点且没有被访问过的点(v4,v5)入队，标记v2的状态为访问过；
- 3.v2访问后访问v3,把v3的所有邻接点且没有被访问过的点(v6,v7)入队，标记v3的状态为访问过；
- 4.重复上述过程，直到所有顶点遍历完;
- 5.结束遍历。
值得注意的是这个Visited数组，我们在入队的时候就可以设置为已经访问过的元素，我们的处理是访问出队的顶点，并把出队的顶点的邻接点入队。
2.邻接矩阵的代码实现
邻接矩阵的顶点结构：
//邻接矩阵的顶点结构，表示一个顶点的信息
typedef struct{int no; //顶点编号char *show; //显示行为(我们不希望打印数字no出来，而是空间中存的数据)
}MatrixVertex;
图的邻接矩阵表示法：
typedef int MatrixEdge;
//图的邻接矩阵表示法
typedef struct {MatrixVertex vex[MaxNodeNum]; // 存储顶点信息，使用一维数组存储顶点MatrixEdge edges[MaxNodeNum][MaxNodeNum]; // 存储边的结构，矩阵,数组中存的是权值int nodeNum; // 约束实际的顶点数量//<----------上面三个其实就够了，为了表示任意图，加了下面两个变量------------->int edgeNum; //边的数量int directed; //是否有向
}MatrixGraph;
因为邻接矩阵的边就是个二维矩阵，所以不把它封装成结构体了，直接构建邻接矩阵，参照的是《01数据结构-图的概念和图的存储结构》链接: https://blog.csdn.net/2302_82136376/article/details/150055797?fromshare=blogdetail&sharetype=blogdetail&sharerId=150055797&sharerefer=PC&sharesource=2302_82136376&sharefrom=from_link中的逻辑。
初始化邻接矩阵的接口：
void initMatrixGraph(MatrixGraph *graph,const char *names[],int num,int directed,int edgeValue);void addMGraphEdge(MatrixGraph *graph,int x,int y,int w);
先看void initMatrixGraph(MatrixGraph *graph,const char *names[],int num,int directed,int edgeValue);中的参数，第一个传的是哪一个图，第二个传的是一个字符串数组用于初始化MatrixVertex中的char *show，第三个传的是约束实际的顶点数量，第四个传的是是否有向，第五个传的是每条边的权重，
再看void addMGraphEdge(MatrixGraph *graph,int x,int y,int w);给图中的两个顶点添加边，所以需要MatrixGraph *graph,int x,int y，再给这条边加权重所以传int w。
初始化实现：void initMatrixGraph(MatrixGraph *graph,const char *names[],int num,int directed,int edgeValue);
void initMatrixGraph(MatrixGraph *graph, const char *names[], int num, int directed, int edgeValue) {graph->directed=directed;graph->nodeNum=num;graph->edgeNum=0;memset(graph->vex,0,sizeof(graph->vex));memset(graph->edges,0,sizeof(MatrixEdge) * MaxNodeNum * MaxNodeNum);for (int i = 0; i < num; ++i) {graph->vex[i].no=i;graph->vex[i].show=names[i];for (int j = 0; j < num; ++j) {//存权值graph->edges[i][j]=edgeValue;}}
}
先初始化图中的顶点数量为传入的顶点数量，将传入函数的图中的顶点集和边集权初始化为0。for循环开始为MatrixVertex中的顶点编号和显示行为赋值，进入第二重循环，为边集里的每一条赋权重
添加边：void addMGraphEdge(MatrixGraph *graph,int x,int y,int w);
static int isEdge(int weight) {if (weight > 0 && weight < INF) {return 1;}return 0;
}void addMGraphEdge(MatrixGraph *graph, int x, int y, int w) {if (x<0 || x>graph->nodeNum) {return;}if (y<0 || y>graph->nodeNum) {return;}if (!isEdge(graph->edges[x][y])) {graph->edges[x][y]=w;//对角线另外一条边也添加if (graph->directed == 0) {graph->edges[y][x] = w;}graph->edgeNum++;}
}在static中我们写了一个判断图中两个顶点之间是否有边的内在接口函数，采用的方式是权值判断法，如果传入的边的权值大于0并且小于一个极大值，我们就认为这两个顶点之间有边，反之则无边。在void addMGraphEdge(MatrixGraph *graph, int x, int y, int w)函数中假设没有边，即isEdge(graph->edges[x][y])返回值为0，我们就连接两条边，并赋权重，如果graph->directed == 0我们就认为是个无向图，由于边的矩阵是对称矩阵，我们把对角线另外一条边也添加。
来小小测试一下;
#include <stdio.h>
#include <stdlib.h>
#include "matrixGraph.h"void testMatrixGraph(MatrixGraph *grap) {char *nodeName[] = {"V1", "V2", "V3", "V4", "V5", "V6", "V7", "V8"};initMatrixGraph(grap, nodeName, sizeof(nodeName) / sizeof(nodeName[0]), 0, 0);addMGraphEdge(grap, 0, 1, 1);addMGraphEdge(grap, 0, 2, 1);addMGraphEdge(grap, 1, 3, 1);addMGraphEdge(grap, 1, 4, 1);addMGraphEdge(grap, 2, 5, 1);addMGraphEdge(grap, 2, 6, 1);addMGraphEdge(grap, 3, 7, 1);addMGraphEdge(grap, 4, 7, 1);addMGraphEdge(grap, 5, 6, 1);
}int main() {MatrixGraph g1;testMatrixGraph(&g1);printf("graph have %d edge!\n", g1.edgeNum);return 0;
}
结果:
D:\work\DataStruct\cmake-build-debug\03_GraphStruct\MatrixGraph.exe
graph have 9 edge!进程已结束，退出代码为 0
下面来看深度优先遍历和广度优先遍历的代码
深度优先遍历：void DFS_MGraph(MatrixGraph *graph,int v);
static int MGraphVisited[MaxNodeNum];void visitMGraphNode(MatrixVertex* node) {printf("%s\t", node->show);
}void DFS_MGraph(MatrixGraph *graph,int v) {visitMGraphNode(&graph->vex[v]);MGraphVisited[v]=1;for (int i = 0; i < graph->nodeNum; ++i) {if (isEdge(graph->edges[v][i])&&MGraphVisited[i]==0) {DFS_MGraph(graph,i);}}
}
写了一个数组来存已经访问过的顶点，由于类似于树的先序遍历，所以函数进来就要访问，然后把传入的顶点设为已被访问，进入for循环从0号顶点一直遍历到graph->nodeNum，判断有哪个顶点与他右边并且未被访问，如果找到进入递归，一直递到第一次传入的顶点v找遍graph->nodeNum这么多顶点，退出递归函数。
如图2我们假设传入的时0即a这个顶点，访问a，把a标记为已被访问(红色)，进入函数的for循环，发现了和1即b顶点间有边且b还未被访问，执行DFS_MGraph(graph,i);
第一次递进去，传入的是1即b顶点，把b标记为已被访问(蓝色)，发现和0即a顶点间有边但是a已被访问，继续遍历发现和2即c顶点有边且c顶点未被访问，执行DFS_MGraph(graph,i);
第二次递进去，传入的是2即c顶点，把c标记为已被访问(绿色)，发现和1即b顶点间有边但是b已被访问，继续遍历发现和3即d顶点有边且d顶点未被访问，执行DFS_MGraph(graph,i);
第三次递进去，传入的是3即d顶点，把d标记为已被访问(黄色)，发现和0即a顶点间有边但是b已被访问，继续遍历发现和2即c顶点有边但是c顶点也已访问，一直for循环到把5个顶点全部循环完也没有找到开始归回去
第一次归，由于是从第二次递归的黄颜色进来的，所以归回到第二次递归的黄颜色格子，在第4个顶点即e有边且e顶点未被访问，执行DFS_MGraph(graph,i);
第四次递进去，此时全部顶点都被访问，所以开始归回。
第二次归，直接归回到第四行的紫色格子
第三次归，函数执行完再次归回到第三行的绿色格子，由于全部顶点都被访问所以再归回去。
第四次归，归到第二行的蓝色格子，全部顶点都被访问，直接for循环完后退出函数。最终深搜的顺序：a->b->c->d->e。
图2
广度优先遍历：void BFS_MGraph(MatrixGraph *graph,int v);
void initVisited() {memset(MGraphVisited, 0, sizeof(MGraphVisited));
}void BFS_MGraph(MatrixGraph *graph,int v) {int front=0;int rear=0;MatrixVertex *queue[MaxNodeNum];queue[rear]=&graph->vex[v];// 在入队的同时就标记为已访问MGraphVisited[v] = 1;rear=(rear+1)%MaxNodeNum;while (front!=rear) {//出队MatrixVertex *node=queue[front];int nodeNum=node->no;visitMGraphNode(node);front=(front+1)%MaxNodeNum;//入队for (int i = 0; i < graph->nodeNum; ++i) {if (isEdge(graph->edges[nodeNum][i])&&MGraphVisited[i]==0) {queue[rear]=&graph->vex[i];MGraphVisited[i] = 1; // 在入队的同时就标记为已访问rear=(rear+1)%MaxNodeNum;}}}
}
注意在上面已经给static int MGraphVisited[MaxNodeNum];赋值了所以在开始执行BFS之前，需要初始化MGraphVisited数组。因为MGraphVisited数组中的元素被标记为已访问（即值为1）
我们在void BFS_MGraph(MatrixGraph *graph,int v) 里面创建一个临时队列，初始化这个队列时就把传入的v入队，并在入队的同时就标记为已访问，当队列不为空时，进行出队入队的操作，出队时创建一个临时顶点变量node，让它拿到node的no（因为我们在for循环里需要拿到出队的元素不断判断与其他顶点是否有边，若有边就入队）并访问它，在for循环里用拿到的nodeNum遍历graph->vex[nodeNum]和其他顶点是否有边，其他没有被访问的顶点，如果找到满足条件的顶点，入队，并在入队的同时就标记为已访问。
如图3，我们假设传入的时0即a这个顶点，将a入队，再出队，出队的时候直接把5个顶点全部遍历完，发现1即b顶点和3即d顶点有边且未被访问，直接把b和d顶点入队
把先进来的b出队，出队的时候直接把5个顶点全部遍历完，发现0即a顶点，2即c顶点和4即e顶点有边但是a顶点已被访问剩下两个没有，直接把c和e顶点入队
把d出队，发现1即b顶点和2即c顶点有边但已被访问直接开始出队
重复上述过程直到队列为空，最终广搜的顺序：a->b->d->c->e。
图3
大概先写这些吧，今天的博客就先写到这，谢谢您的观看。