01数据结构-图的邻接矩阵和遍历

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

大概先写这些吧，今天的博客就先写到这，谢谢您的观看。