首页 > 代码库 > 数据结构(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实现)------- 图的邻接矩阵表示