C语言 图的建立（邻接矩阵与邻接表）

一、邻接矩阵 

1.邻接矩阵表示法

邻接矩阵是用于表示图的数据结构之一，可以用二维数组来表示。在邻接矩阵中，每个顶点都对应矩阵的一行和一列，矩阵中的值表示相应两个顶点之间的连通性。如果两个顶点之间存在一条边，则矩阵中对应位置为1；否则为0。如果是网 ，则矩阵中对应位置为权值；否则为（计算机允许、大于所以边上的数）。对于无向图而言，邻接矩阵是对称的；而对于有向图而言，则不一定对称。邻接矩阵可以方便地进行图的遍历、查找和修改等操作，但是对于稀疏图（边数较少）来说，邻接矩阵会浪费大量的空间。

用邻接矩阵表示法表示图除了一个用于储存邻接矩阵的二维数组外，还需要一个一维数组储存顶点信息。

储存结构如下：

#define MVNum 100//最大顶点数#define MaxInt 66666//表示极大值typedef struct {char vexs[MVNum];//顶点表（顶点为字符型）int arcs[MVNum][MVNum];//邻接矩阵（权值为整型）int vexnum, arcnum;//图的当前点数和边数}AMGraph;

 2.采用邻接矩阵表示法创建无向网

//定位int LocateVex(AMGraph* G, char v) {int i;for (i = 0; i vexnum; i++) {if (G->vexs[i] == v) {return i;}}return -1;}//创建无向网GAMGraph* CreateUDN() {int i, j, k, w;char v1, v2;AMGraph* G = malloc(sizeof(AMGraph));printf("输入总顶点数，边数\n");scanf("%d%d", &G->vexnum, &G->arcnum);getchar();//吸收换行符printf("依次输入点的信息\n");for (i = 0; i vexnum; i++) {scanf("%c", &G->vexs[i]);}getchar();//吸收换行符for (i = 0; i vexnum; i++)    for (j = 0; j vexnum; j++) {    if (i == j) {    G->arcs[i][j] = 0;    }    else {    G->arcs[i][j] = MaxInt;    }}for (k = 0; k arcnum; k++) {printf("输入一条边依附的顶点及权值\n");scanf("%c%c", &v1, &v2);scanf("%d", &w);getchar();//吸收换行符i = LocateVex(G, v1), j = LocateVex(G, v2);//确定v1、v2在顶点数组的下标G->arcs[i][j] = w;//边权值置为wG->arcs[j][i] = w;//无向网对称边权值也置为w}return G;}

再写个输出函数

void print(AMGraph* G) {int i, j;printf("  ");for (i = 0; i vexnum; i++) {printf("%c ", G->vexs[i]);}printf("\n");for (i = 0; i vexnum; i++) {printf("%c ", G->vexs[i]);for (j = 0; j vexnum; j++) {if (G->arcs[i][j] == MaxInt)printf("∞ ");elseprintf("%d ", G->arcs[i][j]);}printf("\n");}}

如果要创建无向图，只需改动两处：一是初始化时将边的权值都初始化为0；二是构造邻接矩阵时将权值w改为1。同样，稍做修改即可建立有向图或有线网（如果你前面知识学懂了，这里肯定没问题）。

二、邻接表

1.邻接表表示法

邻接表（Adjacency List）是一种表示无向图或有向图的数据结构。它使用一个数组来存储所有顶点，每个顶点对应一个链表。链表中存储了与该顶点直接相邻的所有顶点。对于有向图，邻接表中的链表只存储指向的顶点（个数为出度）。有时，为了便于确定顶点的入度，可以建立有向图的逆邻接表。

邻接表储存结构如下： 

#define MVNum 100  //最大顶点数typedef struct ArcNode {  //边表结点int adjvex;//邻接点在顶点数组中的下标struct ArcNode* next;//指向下一条边的指针}ArcNode;typedef struct VNode {   //表头顶点信息结构体char data;ArcNode* first;//指向第一条依附于该顶点的边的指针}VNode, AdjList[MVNum];typedef struct {   //图结构体AdjList vertices;//邻接表int vexnum, arcnum;//顶点数和边数}ALGraph;

2.采用邻接表表示法创建无向图 

• 首先输入顶点数和边数
• 对于每条边，都会关联两个顶点，所以接下里输入被关联的两个顶点
• 通过输入的顶点调用LocateVex函数来找到这两个顶点在顶点数组中的下标
• 创建新结点，采用头插法插入到关联顶点的表头结点指向的单链表中

  //查找int LocateVex(ALGraph* G, char v) {int i;for (i = 0; i vexnum; i++) {if (G->vertices[i].data == v) {return i;}}return -1;}//无向图的创建ALGraph* CreateALGraph() {int i, j, k;char v1, v2;ALGraph* G = malloc(sizeof(ALGraph));printf("输入顶点数和边数:\n");scanf("%d%d", &G->vexnum, &G->arcnum);getchar();//吸收换行符printf("依次输入顶点信息：\n");for (i = 0; i vexnum; i++) {scanf("%c", &G->vertices[i].data);G->vertices[i].first = NULL;}getchar();//吸收换行符//构造边表for (k = 0; k arcnum; k++) {printf("输入一条边依附的两个顶点:\n");scanf("%c%c", &v1, &v2);getchar();//吸收换行符i = LocateVex(G, v1), j = LocateVex(G, v2);//确定v1、v2在邻接表数组中的下标ArcNode* p1 = malloc(sizeof(ArcNode));//生成新的边结点*p1p1->adjvex = i;//邻接点序号为ip1->next = G->vertices[j].first;//头插法插到顶点vj的边表头部G->vertices[j].first = p1;//因为是无向图，所以生成对称的边结点*p2ArcNode* p2 = malloc(sizeof(ArcNode));p2->adjvex = j;p2->next = G->vertices[i].first;G->vertices[i].first = p2;}return G;}

  还可以写个输出邻接表的函数

  void print(ALGraph* G) {int i;for (i = 0; i vexnum; i++) {printf("顶点%c的邻结点有：", G->vertices[i].data);ArcNode* p = G->vertices[i].first;while (p != NULL) {printf(" %c", G->vertices[p->adjvex].data);p = p->next;}printf("\n");}}

  运行 并构建如下图所示的邻接表：

   运行结果如下：

   总结