【数据结构——图与邻接矩阵】 - 实践

引入

树的遍历方式可分为深搜和广搜，这同样适用于图，不过有些地方会有出入。

树的节点结构从根到叶子节点都是1：n,到叶子节点后就没有了。而对于图来说，如果到了最底下的节点，它可能除了连接已经记录过的上层节点，还连接着上一层的其他未被记录的节点（比如下图的V8)，那对于第三层的节点（V4、V5）来说,再往下顺延就成了2:1(n:m)了。

图的深搜

与树的深搜类似，一直沿着一个方向走到底就是深搜。从V1遍历到V8之后，因为V8连接着两个节点，遍历节点时如何准确遍历到还未被访问的节点，这时候可以通过数组来做标记（标记已遍历的），防止重复遍历。
之后就精准的遍历到了V5，那下一步应该怎么办？对于V5来说它连接了V8和V2，而此时两者都已经访问过了。与树的遍历相似，访问到底了就回退到根节点继续遍历另外一边，直到所有节点都被标记。

图的广搜

深搜和广搜都需要用数组存储标记信息防止重复便利，除此之外：
在之前的二叉树的广搜和深搜这篇文章里利用队列来实现记忆功能从而完成广搜的方法同样适用于图的广搜,这里不再附图了,想更直观的了解过程可以点进去看一下。

遍历过V1之后就将V1连接的的下一层节点都入队（先左后右，先进先出）,之后将入队的节点逐个出队,每出队一个节点就将此节点连接的下一层节点都入队,直到所有节点出队。
需要注意的是广搜中标记的是已进入队列的节点,不是访问过的节点,防止重复入队。

在写代码之前先到上一篇回顾一下图的邻接矩阵的存储特点：
示意图， 邻接矩阵！本篇没有邻接表的代码。

头文件

在代码中,1E4 是科学计数法的表示形式,它表示的是 10^4 ,也就是十进制的 10000 。
在图的邻接矩阵表示中，常常会用一个很大的值（比如这里的 1E4 ）来表示两个顶点之间没有边相连（即不可达），这类似于无穷大的概念，在后续涉及到图的路径、权重等相关算法（如最短路径算法）时，方便进行计算和判断。

#pragma once
#define INF 1E4
#define MaxNodeNum 20
typedef struct {
int no; //顶点编号
char* show; //显示指向的数组的对应内容（如A、B）
}MatrixVertex; //矩阵顶点
typedef int MatrixEdge;
//图的邻接矩阵表示法
typedef struct {
MatrixVertex vex[MaxNodeNum]; //顶点集
int nodeNum; //约束实际的顶点个数
MatrixEdge edge[MaxNodeNum][MaxNodeNum]; //边集
int edgeNum; //边的数量
int directed; //是否有向
}MGraph; //表示邻接矩阵（邻接图的缩写）
void initMGraph(MGraph* graph, char* names[], int num, int directed, int edgeValue);
void addMGraphEdge(MGraph* graph, int x, int y, int w);
void visitMGraphNode(MatrixVertex* node);
void initVisited();
void DFS_MGraph(MGraph* graph, int v);
void BFS_MGraph(MGraph* graph, int v);

功能实现

判断是否有边

static int isEdge(int weight) {
if (weight >
0 && weight < INF) {
return 1;
}
return 0;
}

初始化

void initMGraph(MGraph* graph, const char* names[], int num, int ditected, int edgeValue) {
graph->directed = ditected;
graph->nodeNum = num;
graph->edgeNum = 0;
//初始边的权值为0，代表没有边
memset(graph->vex, 0, sizeof(graph->vex));
memset(graph->edge, 0, sizeof(MatrixEdge)*MaxNodeNum*MaxNodeNum);
for (int i = 0; i < num;
++i) {
//顶点（一维数组）填充
graph->vex[i].no = i;
graph->vex[i].show =(char*) names[i];
for (int j = 0; j < num;
++j) {
//边（矩阵）的填充
graph->edge[i][j] = edgeValue;
}
}
}

添加边

void addMGraphEdge(MGraph* graph, int x, int y, int w) {
if (x<
0 || x>graph->nodeNum) {
return;
}
if (y<
0 || y>graph->nodeNum) {
return;
}
if (!isEdge(graph->edge[x][y])) {
//如果没有边再执行
graph->edge[x][y] = w;
if (graph->directed == 0) {
//如果是无向则同时标记对向路径的权值
graph->edge[y][x] = w;
//矩阵的转置
}
graph->edgeNum++;
//同时更新路径数目
}
}

访问当前顶点

void visitMGraphNode(MatrixVertex* node) {
printf("\t%s", node->show);
//访问当前顶点的展示内容（如A、B）
}

标记与初始化标记

static int MGraphVisited[MaxNodeNum];
//用来标记已遍历的顶点
void initVisited() {
//初始化已标记的顶点，防止多次遍历时受干扰
memset(MGraphVisited, 0, sizeof(MGraphVisited));
}

深搜

void DFS_MGraph(MGraph* graph, int v) {
//v是起始顶点的索引
visitMGraphNode(&graph->vex[v]);
//先访问
MGraphVisited[v]=1;
//访问后做标记
for (int i = 0; i < graph->nodeNum;++i){//访问v的所有邻接顶点if( isEdge(graph->edge[v][i]) && MGraphVisited[i] == 0){//若邻接且未访问DFS_MGraph(graph, i);//再重复操作}}}

广搜

void BFS_MGraph(MGraph* graph, int v) {
//起始顶点下标v
int que[MaxNodeNum];
//队列存储待访问的顶点下标
int rear = 0, front = 0, cur;
rear = (rear + 1) % MaxNodeNum;
//形成循环数组防止溢出（后移一格）
que[rear] = v;
//下标v入队
MGraphVisited[v] = 1;
//标记下标为v的顶点(广度遍历标记的是入队的顶点)
while (front != rear) {
//队列不为空时
front = (front + 1) % MaxNodeNum;
//访问队头（front后移一格，这里此时front与rear相同）
cur = que[front];
//cur现为队头，同时也为刚入队在队尾的顶点标号v
visitMGraphNode(&graph->vex[cur]);
//访问v标号存储的顶点
for (int i = 0; i < graph->nodeNum;++i) {//访问v的所有邻接且未被标记的顶点if (isEdge(graph->edge[cur][i]) &&!MGraphVisited[i]) {rear = (rear + 1) % MaxNodeNum;//找到后将尾指针后移que[rear] = i;//将该顶点入队并放在队尾MGraphVisited[i] = 1;//入队后做标记}}}}

功能调用

void testMatrixGraph(MGraph* grap) {
const char* nodeName[] = {
"V1", "V2", "V3", "V4", "V5", "V6", "V7", "V8"
};
initMGraph(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() {
MGraph g1;
testMatrixGraph(&g1);
printf("graph have %d edge!\n", g1.edgeNum);
DFS_MGraph(&g1, 0);
initVisited();
printf("\n");
BFS_MGraph(&g1, 0);
return 0;
}