首页 > 代码库 > 数据结构(C实现)------- 图的邻接矩阵表示
数据结构(C实现)------- 图的邻接矩阵表示
[本文是自己学习所做笔记,欢迎转载,但请注明出处:http://blog.csdn.net/jesson20121020]
图的邻接表表示法类似于树的孩子链表表示法,就是对图中的每个顶点vi,将所有邻接于vi的顶点链接成一个单链表,这个单链表就称为顶点vi的邻接表。在邻接表中有两种结点结构:头结点(vexdata,firstarc)、表结点(adjvex,nextarc)。
其中,表头结点由顶点域(vexdata)和指向第一条邻接边的指针域(firstarc)构成;表结点由邻接点域(adjvex)和指向下一条邻接边的指针域(nextarc)构成。
对于一个具有n个顶点、e条边的图G,若G是无向图,则它的邻接表需要n个表头节点组成的顺序表和2e个结点组成的n个链表;若G是有向图,则它的邻接表需要n个表头结点组成的顺序表和e个结点组成的n个链表。因此图的邻接表表示法的空间复杂度为S(n,e) = O(n+e)。若图中边的数目远远小于n^2,即图为稀疏图,则这时用邻接表表示要比用邻接矩阵表示节省空间。
算法实现:
图的邻接表存储结构描述如下:
#define MAX_VERTEX_NUM 50 typedef enum { DG, UDG } GraphType; typedef char VertexType; //表节点 typedef struct ArcNode { int adjvex; //邻接节点 int weight; //边权重 struct ArcNode *nextarc; //下一个节点指针 } ArcNode, *ArcPtr; //头节点 typedef struct { VertexType vexdata; int id; ArcPtr firstarc; } VNode; //头节点数组 typedef struct { VNode vertices[MAX_VERTEX_NUM]; int vexnum, arcnum; GraphType type; } ALGraph;
建立图的邻接表的算法描述如下:
(1) 输入图的类型(无向图或有向图)
(2) 输入图的顶点数,边数
(3) 输入所有顶点的字符信息,并初始化所有链表的头指针为空指针NULL。
(4) 输入边的信息,生成边表结点,建立图的邻接表,注意区分是图的类型,另外,如果是有权图,邻接矩阵保存其边的权重,这里是无权图
算法源代码如下:
void create_AG(ALGraph *AG) { ArcPtr p; int i, j, k, type; VertexType v1, v2; printf("Please input graph type UG(0) or UDG(1) :"); scanf("%d", &type); if (type == 0) AG->type = DG; else if (type == 1) AG->type = UDG; else { printf("Please input correct graph type UG(0) or UDG(1)!"); return; } printf("please input vexnum:"); scanf("%d", &AG->vexnum); printf("please input arcnum:"); scanf("%d", &AG->arcnum); getchar(); for (i = 1; i <= AG->vexnum; i++) { printf("please input the %dth vex(char) : ", i); scanf("%c", &AG->vertices[i].vexdata); getchar(); AG->vertices[i].firstarc = NULL; } for (k = 1; k <= AG->arcnum; k++) { printf("please input the %dth arc v1(char) v2(char) :", k); scanf("%c %c", &v1, &v2); i = getIndexOfVexs(v1, AG); j = getIndexOfVexs(v2, AG); //根据图的类型创建邻接表 if (AG->type == DG) { //有向图 p = (ArcPtr) malloc(sizeof(ArcNode)); p->adjvex = j; p->nextarc = AG->vertices[i].firstarc; AG->vertices[i].firstarc = p; } else { //无向图 p = (ArcPtr) malloc(sizeof(ArcNode)); p->adjvex = j; p->nextarc = AG->vertices[i].firstarc; AG->vertices[i].firstarc = p; p = (ArcPtr) malloc(sizeof(ArcNode)); p->adjvex = i; p->nextarc = AG->vertices[j].firstarc; AG->vertices[j].firstarc = p; } getchar(); } }算法说明:
该算法的时间复杂度为O(n+e)。若输入边的两个顶点字符,需要通过查找才能得到顶点在图中的位置,则算法的时间复杂度为O(n*e)。值得注意的是,一个图的邻接矩阵表示是唯一的,但其邻接表表示不唯一,这是因为在邻接表表示法中,各边表结点的链接次序取决于建立邻接表的算法以及边的输入次序。例如,在该算法中,每生成一个边表结点,均插在对应链表的表头位置。
完整代码如下:
/* ============================================================================ Name : ALGraph.c Author : Version : Copyright : Your copyright notice Description : Hello World in C, Ansi-style ============================================================================ */ #include <stdio.h> #include <stdlib.h> #include <stdio.h> #define MAX_VERTEX_NUM 50 typedef enum { DG, UDG } GraphType; typedef char VertexType; //表节点 typedef struct ArcNode { int adjvex; //邻接节点 int weight; //边权重 struct ArcNode *nextarc; //下一个节点指针 } ArcNode, *ArcPtr; //头节点 typedef struct { VertexType vexdata; int id; ArcPtr firstarc; } VNode; //头节点数组 typedef struct { VNode vertices[MAX_VERTEX_NUM]; int vexnum, arcnum; GraphType type; } ALGraph; /** * 根据顶点字符得到在顶点数组中的下标 */ int getIndexOfVexs(char vex, ALGraph *AG) { int i; for (i = 1; i <= AG->vexnum; i++) { if (AG->vertices[i].vexdata =http://www.mamicode.com/= vex) {>
执行结果:Please input graph type UG(0) or UDG(1) :1 please input vexnum:4 please input arcnum:4 please input the 1th vex(char) : a please input the 2th vex(char) : b please input the 3th vex(char) : c please input the 4th vex(char) : d please input the 1th arc v1(char) v2(char) :a b please input the 2th arc v1(char) v2(char) :a c please input the 3th arc v1(char) v2(char) :a d please input the 4th arc v1(char) v2(char) :b d Graph type: Undirect graph Graph vertex number: 4 Graph arc number: 4 Vertex set : a b c d Adjacency List: 1-->4-->3-->2 2-->4-->1 3-->1 4-->2-->1
以上实现了图的邻接表表示法,用邻接表表示图,可以实现的基本有(1)求图中任一顶点的度(2)判定图中任意两个顶点之间是否有边相连等操作。数据结构(C实现)------- 图的邻接矩阵表示