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

本文主要是介绍[数据结构]图邻接矩阵C语言简单实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

#include <stdio.h>
#include <stdlib.h>#define INFINTE 65535
#define MAXSIZE 100typedef 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;
}

我们以这个图为例，来建一个邻接矩阵。
还是老规矩，代码和解释对应看
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（代表有边），如果是有权图，则赋值权值
这里写图片描述
Line 76 如果是无向图，这样的，则要反向存储
Line 79~91 这是我根据上面的图，写的一个边