[数据结构]图邻接矩阵C语言简单实现

淡淡的烟草味﹌ 2022-06-05 04:16 209阅读 0赞

Github:([https://github.com/FlameCharmander/DataStructure][https_github.com_FlameCharmander_DataStructure])  
到了图这章确实会比较复杂，因此我想分几个部分，一个是邻接矩阵实现，一个是邻接表实现，然后是基于邻接矩阵的广度优先搜索遍历，基于邻接表的深度优先搜索遍历来讨论。  
首先现在大概有几种图的数据结构，一个是邻接矩阵，邻接表，十字链表（有向图），邻接多重表。  
我们先来看下邻接矩阵是怎么实现的吧。

#include <stdio.h>
    #include <stdlib.h>
    
    #define INFINTE 65535
    #define MAXSIZE 100
    
    typedef char VertexType;                //顶点类型应由用户定义
    typedef int EdgeType;                   //边上的权值类型应由用户定义
    
    typedef struct graph{
        VertexType vexs[MAXSIZE];            //顶点表
        EdgeType   arc[MAXSIZE][MAXSIZE];       //邻接矩阵
        int numNodes, numEdges;
    }Graph;
    
    void CreateGraph(Graph* graph);
    
    int main()
    {
        Graph graph;
        CreateGraph(&graph);
        //打印邻接矩阵
        int i, j;
        for (i = 0; i < graph.numNodes; ++i){
            for (j = 0; j < graph.numNodes; ++j){
                printf("%d ", graph.arc[i][j]);
            }
            printf("\n");
        }
        return 0;
    }
    
    void CreateGraph(Graph* graph){
        int i, j;
        //先把图的邻接矩阵置为0(0表示没边，1表示有边)
        for (i = 0; i < graph->numNodes; ++i){
            for (j = 0; j < graph->numNodes; ++j){
                graph->arc[i][j] = 0;
            }
        }
        //printf("请输入顶点数, 边数：");
        //scanf("%d %d", &graph->numNodes, &graph->numEdges);
        //getchar();    //消除空白符
        graph->numNodes = 6;
        graph->numEdges = 6;
        /*
        for (i = 0; i < graph->numNodes; ++i){
            printf("请输入顶点：");
            scanf("%c", &graph->vexs[i]);
            getchar();  //消除空白符
        }
        */
        graph->vexs[0] = 'A';
        graph->vexs[1] = 'B';
        graph->vexs[2] = 'C';
        graph->vexs[3] = 'D';
        graph->vexs[4] = 'E';
        graph->vexs[5] = 'F';
        VertexType start, end;
        /*
        for (i = 0; i < graph->numEdges; ++i){
            printf("请输入起点， 终点：");
            scanf("%c %c", &start, &end);
            getchar();  //消除空白符
            int startIndex, endIndex;
            for (j = 0; j < graph->numNodes; ++j){  //找到起始点,终点
                if (start == graph->vexs[j]){   //遍历找到起点的下标
                    startIndex = j;
                }
                if (end == graph->vexs[j]){ //遍历找到终点的下标
                    endIndex = j;
                }
            }
            graph->arc[startIndex][endIndex] = 1;
            //如果是无向图，需要双向保存
            graph->arc[endIndex][startIndex] = 1;
        }
        */
        graph->arc[0][2] = 1;
        graph->arc[0][3] = 1;
        graph->arc[3][1] = 1;
        graph->arc[3][4] = 1;
        graph->arc[3][5] = 1;
        graph->arc[4][5] = 1;
        //如果是无向图，需要保存两个边
        graph->arc[2][0] = 1;
        graph->arc[3][0] = 1;
        graph->arc[1][3] = 1;
        graph->arc[4][3] = 1;
        graph->arc[5][3] = 1;
        graph->arc[5][4] = 1;
    }

![图][SouthEast]  
我们以这个图为例，来建一个邻接矩阵。  
还是老规矩，代码和解释对应看  
Line 1~2 头文件  
Line 4 定义无穷大，在图中我们知道有两种图，一种是无权图，也就是在邻接矩阵中0代表没有边，1代表有边；一种是有权图，那么我们就要换种方式表示了，一般来说，有权图的话，是无穷值代表没边，其它的话代表权值。  
Line 5 图的那个数组最多的大小  
Line 7~8 一个是顶点类型，一个是权值类型，权值类型一般是int  
Line 10~14 图的数据结构，由一个顶点表，一个邻接矩阵，还有两个存放顶点个数和边的个数。  
Line 16 创建图的声明  
Line 18~31 创建图，并且打印邻接矩阵  
Line 36~40 把邻接矩阵的每个元素都赋值为0，上面那个图的例子是个无权图（边没权值），所以0代表没变，1代表有边。如果是有权图的话，应该赋值为无穷大（刚才说的，有权图用无穷大来表示没边）  
Line 41~42 我们需要用户定义一下图的顶点数和边的数目  
Line 43 这里是c语言里面scanf函数的一个机制，为什么要getchar()，因为上面输入完我们按下回车键，回车键\\n会影响给下一次scanf()，不信的话你们可以去掉试试  
Line 47~50 根据用户输入顶点  
Line 53~58 这里为了方便展示，我也写了一些数据在里面的，6个顶点ABCDEF，是根据上面的那个图写的  
Line 61~64 这里主要是输入边，输入边的两个顶点，来建立起边  
Line 66~73 主要是根据用户输入的两个顶点来找到顶点的下标  
Line 74 然后把找到邻接矩阵对应的位置赋值1（代表有边），如果是有权图，则赋值权值  
![这里写图片描述][SouthEast 1]  
Line 76 如果是无向图，这样的，则要反向存储  
Line 79~91 这是我根据上面的图，写的一个边

[https_github.com_FlameCharmander_DataStructure]: https://github.com/FlameCharmander/DataStructure
[SouthEast]: /images/20220605/bfae490a4d544464b269ba95212a2d4c.png
[SouthEast 1]: /images/20220605/d6d60cddfe914cfa97e1f60ab6fdfa24.png