图的邻接表存储结构-白红宇

图的邻接表存储结构

阅读量：5104 次

发布时间：2019-06-13

本文共 10508 字，大约阅读时间需要 35 分钟。

// c7-2.h 图的邻接表存储结构(见图7.16)#define MAX_VERTEX_NUM 20enum GraphKind{DG,DN,UDG,UDN}; // {有向图,有向网,无向图,无向网}struct ArcNode{	int adjvex; // 该弧所指向的顶点的位置	ArcNode *nextarc; // 指向下一条弧的指针	InfoType *info; // 网的权值指针}; // 表结点typedef struct{	VertexType data; // 顶点信息	ArcNode *firstarc; // 第一个表结点的地址，指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM]; // 头结点struct ALGraph{	AdjList vertices;	int vexnum,arcnum; // 图的当前顶点数和弧数	int kind; // 图的种类标志};

图717 和图718 分别是有向图和无向网的的邻接表存储结构。要注意的是，为了

提高效率，bo7-2.cpp 中的基本操作函数CreateGraph()产生链表时总是在表头插入结点。

所以，对于给定的图，即使它的顶点输入顺序相同，邻接表的存储结构也不惟一。邻接表

的存储结构还与弧或边的输入顺序有关。

对于无向的图或网，每一条边产生2 个表结点，分别在该边的2 个顶点的链表上。由

图718 可见，2 条边的无向网有4 个表结点。为简化，无向网的每条边只动态生成1 个

存放权值的存储空间，由两个结点共同指向。由于邻接表存储结构中的链表的长度与该顶

点的邻接出弧或边数相等，显然，图的邻接表存储结构适合存储弧或边相对较少的稀

疏图。

由邻接表的存储结构可见，每个顶点的信息由表示顶点名称的字符串和不带头结点的

单链表组合而成。这样，对于单链表的处理，我们就可以利用不带头结点的单链表的基本

操作(在bo2-8.cpp 中)和扩展操作(在func2-1.cpp 中)来简化编程。为了能够利用这些操

作，需要将在bo2-8.cpp 和func2-1.cpp 中用到的类型ElemType、LNode、LinkList 和邻

接表的类型ArcNode 联系起来。c7-21.h 就是根据c7-2.h 建立了这种联系。

// c7-21.h 图的邻接表存储结构(与单链表的变量类型建立联系)#define MAX_VERTEX_NUM 20enum GraphKind{DG,DN,UDG,UDN}; // {有向图,有向网,无向图,无向网}struct ElemType // 加(见图7.19){	int adjvex; // 该弧所指向的顶点的位置	InfoType *info; // 网的权值指针};struct ArcNode // 改(见图7.20){	ElemType data; // 除指针以外的部分都属于ElemType	ArcNode *nextarc; // 指向下一条弧的指针}; // 表结点typedef struct{	VertexType data; // 顶点信息	ArcNode *firstarc; // 第一个表结点的地址,指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM]; // 头结点struct ALGraph{	AdjList vertices;	int vexnum,arcnum; // 图的当前顶点数和弧数	int kind; // 图的种类标志};#define LNode ArcNode // 加，定义单链表的结点类型是图的表结点的类型#define next nextarc // 加，定义单链表结点的指针域是表结点指向下一条弧的指针域typedef ArcNode *LinkList; // 加，定义指向单链表结点的指针是指向图的表结点的指针

// bo7-2.cpp 图的邻接表存储(存储结构由c7-21.h定义)的基本操作(15个)，包括算法7.4～7.6#include"bo2-8.cpp" // 不带头结点的单链表基本操作#include"func2-1.cpp" // 不带头结点的单链表扩展操作int LocateVex(ALGraph G,VertexType u){ // 初始条件：图G存在，u和G中顶点有相同特征	// 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1	int i;	for(i=0;i
    
     =2) // 无向图或网，产生第2个表结点，并插在第j个元素(入弧)的表头		{			e.adjvex=i; // e.info不变，不必再赋值			ListInsert(G.vertices[j].firstarc,1,e); // 插在第j个元素的表头，在bo2-8.cpp中		}	}}void CreateGraphF(ALGraph &G){ // 采用邻接表存储结构，由文件构造没有相关信息图或网G(用一个函数构造4种图)	int i,j,k,w; // w是权值	VertexType va,vb; // 连接边或弧的2顶点	ElemType e;	char filename[13];	FILE *graphlist;	printf("请输入数据文件名(f7-1.txt或f7-2.txt)：");	scanf("%s",filename);	printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");	scanf("%d",&G.kind);	graphlist=fopen(filename,"r"); // 以读的方式打开数据文件，并以graphlist表示	fscanf(graphlist,"%d",&G.vexnum);	fscanf(graphlist,"%d",&G.arcnum);	for(i=0;i
     
      =2) // 无向图或网，产生第2个表结点，并插在第j个元素(入弧)的表头		{			e.adjvex=i; // e.info不变，不必再赋值			ListInsert(G.vertices[j].firstarc,1,e); // 插在第j个元素的表头，在bo2-8.cpp中		}	}	fclose(graphlist); // 关闭数据文件}void DestroyGraph(ALGraph &G){ // 初始条件：图G存在。操作结果：销毁图G	int i;	ElemType e;	for(i=0;i
      
       i) // 顶点序号>i(保证动态生成的权值空间只释放1次)					free(e.info);			}			else // 图				DestroyList(G.vertices[i].firstarc); // 销毁弧或边链表，在bo2-8.cpp中			G.vexnum=0; // 顶点数为0			G.arcnum=0; // 边或弧数为0}VertexType& GetVex(ALGraph G,int v){ // 初始条件：图G存在，v是G中某个顶点的序号。操作结果：返回v的值	if(v>=G.vexnum||v<0)		exit(ERROR);	return G.vertices[v].data;}Status PutVex(ALGraph &G,VertexType v,VertexType value){ // 初始条件：图G存在，v是G中某个顶点。操作结果：对v赋新值value	int i;	i=LocateVex(G,v);	if(i>-1) // v是G的顶点	{		strcpy(G.vertices[i].data,value);		return OK;	}	return ERROR;}int FirstAdjVex(ALGraph G,VertexType v){ // 初始条件：图G存在，v是G中某个顶点	// 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1	ArcNode *p;	int v1;	v1=LocateVex(G,v); // v1为顶点v在图G中的序号	p=G.vertices[v1].firstarc;	if(p)		return p->data.adjvex;	else		return -1;}Status equalvex(ElemType a,ElemType b){ // DeleteArc()、DeleteVex()和NextAdjVex()要调用的函数	if(a.adjvex==b.adjvex)		return OK;	else		return ERROR;}int NextAdjVex(ALGraph G,VertexType v,VertexType w){ // 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点	// 操作结果：返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点，则返回-1	LinkList p,p1; // p1在Point()中用作辅助指针，Point()在func2-1.cpp中	ElemType e;	int v1;	v1=LocateVex(G,v); // v1为顶点v在图G中的序号	e.adjvex=LocateVex(G,w); // e.adjvex为顶点w在图G中的序号	p=Point(G.vertices[v1].firstarc,e,equalvex,p1); // p指向顶点v的链表中邻接顶点为w的结点	if(!p||!p->next) // 没找到w或w是最后一个邻接点		return -1;	else // p->data.adjvex==w		return p->next->data.adjvex; // 返回v的(相对于w的)下一个邻接顶点的序号}void InsertVex(ALGraph &G,VertexType v){ // 初始条件：图G存在，v和图中顶点有相同特征	// 操作结果：在图G中增添新顶点v(不增添与顶点相关的弧，留待InsertArc()去做)	strcpy(G.vertices[G.vexnum].data,v); // 构造新顶点向量	G.vertices[G.vexnum].firstarc=NULL;	G.vexnum++; // 图G的顶点数加1}Status DeleteVex(ALGraph &G,VertexType v){ // 初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧	int i,j,k;	ElemType e;	LinkList p,p1;	j=LocateVex(G,v); // j是顶点v的序号	if(j<0) // v不是图G的顶点		return ERROR;	i=ListLength(G.vertices[j].firstarc); // 以v为出度的弧或边数，在bo2-8.cpp中	G.arcnum-=i; // 边或弧数-i	if(G.kind%2) // 网		while(G.vertices[j].firstarc) // 对应的弧或边链表不空		{			ListDelete(G.vertices[j].firstarc,1,e); // 删除链表的第1个结点，并将值赋给e			free(e.info); // 释放动态生成的权值空间		}		else // 图			DestroyList(G.vertices[j].firstarc); // 销毁弧或边链表，在bo2-8.cpp中		G.vexnum--; // 顶点数减1		for(i=j;i
       
        next=p->next; // 从链表中删除p所指结点				else // p指向首元结点					G.vertices[i].firstarc=p->next; // 头指针指向下一结点				if(G.kind<2) // 有向				{					G.arcnum--; // 边或弧数-1					if(G.kind==1) // 有向网						free(p->data.info); // 释放动态生成的权值空间				}				free(p); // 释放v为入度的结点			}			for(k=j+1;k<=G.vexnum;k++) // 对于adjvex域>j的结点，其序号-1			{				e.adjvex=k;				p=Point(G.vertices[i].firstarc,e,equalvex,p1); // Point()在func2-1.cpp中				if(p)					p->data.adjvex--; // 序号-1(因为前移)			}		}		return OK;}Status InsertArc(ALGraph &G,VertexType v,VertexType w){ // 初始条件：图G存在，v和w是G中两个顶点	// 操作结果：在G中增添弧
        
         ，若G是无向的，则还增添对称弧
         
           ElemType e; int i,j; i=LocateVex(G,v); // 弧尾或边的序号 j=LocateVex(G,w); // 弧头或边的序号 if(i<0||j<0) return ERROR; G.arcnum++; // 图G的弧或边的数目加1 e.adjvex=j; e.info=NULL; // 初值 if(G.kind%2) // 网 { e.info=(int *)malloc(sizeof(int)); // 动态生成存放权值的空间 printf("请输入弧(边)%s→%s的权值: ",v,w); scanf("%d",e.info); } ListInsert(G.vertices[i].firstarc,1,e); // 将e插在弧尾的表头，在bo2-8.cpp中 if(G.kind>=2) // 无向，生成另一个表结点 { e.adjvex=i; // e.info不变 ListInsert(G.vertices[j].firstarc,1,e); // 将e插在弧头的表头 } return OK;}Status DeleteArc(ALGraph &G,VertexType v,VertexType w){ // 初始条件：图G存在，v和w是G中两个顶点 // 操作结果：在G中删除弧
          
           ，若G是无向的，则还删除对称弧
           
             int i,j; Status k; ElemType e; i=LocateVex(G,v); // i是顶点v(弧尾)的序号 j=LocateVex(G,w); // j是顶点w(弧头)的序号 if(i<0||j<0||i==j) return ERROR; e.adjvex=j; k=DeleteElem(G.vertices[i].firstarc,e,equalvex); // 在func2-1.cpp中 if(k) // 删除成功 { G.arcnum--; // 弧或边数减1 if(G.kind%2) // 网 free(e.info); if(G.kind>=2) // 无向，删除对称弧
            
              { e.adjvex=i; DeleteElem(G.vertices[j].firstarc,e,equalvex); } return OK; } else // 没找到待删除的弧 return ERROR;}Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)void(*VisitFunc)(char* v); // 函数变量(全局量)void DFS(ALGraph G,int v){ // 从第v个顶点出发递归地深度优先遍历图G。算法7.5 int w; visited[v]=TRUE; // 设置访问标志为TRUE(已访问) VisitFunc(G.vertices[v].data); // 访问第v个顶点 for(w=FirstAdjVex(G,G.vertices[v].data);w>=0;w=NextAdjVex(G,G.vertices[v].data, G.vertices[w].data)) if(!visited[w]) DFS(G,w); // 对v的尚未访问的邻接点w递归调用DFS}void DFSTraverse(ALGraph G,void(*Visit)(char*)){ // 对图G作深度优先遍历。算法7.4 int v; VisitFunc=Visit; // 使用全局变量VisitFunc，使DFS不必设函数指针参数 for(v=0;v
             
              =0;w=NextAdjVex(G,G.vertices[u].data, G.vertices[w].data)) if(!visited[w]) // w为u的尚未访问的邻接顶点 { visited[w]=TRUE; Visit(G.vertices[w].data); EnQueue(Q,w); // w入队 } } } printf("\n");}void DFS1(ALGraph G,int v,void(*Visit)(char*)){ // 从第v个顶点出发递归地深度优先遍历图G。仅适用于邻接表存储结构 ArcNode *p; // p指向表结点 visited[v]=TRUE; // 设置访问标志为TRUE(已访问) Visit(G.vertices[v].data); // 访问该顶点 for(p=G.vertices[v].firstarc;p;p=p->next) // p依次指向v的邻接顶点 if(!visited[p->data.adjvex]) DFS1(G,p->data.adjvex,Visit); // 对v的尚未访问的邻接点递归调用DFS1}void DFSTraverse1(ALGraph G,void(*Visit)(char*)){ // 对图G作深度优先遍历。DFS1设函数指针参数 int v; for(v=0;v
              
               next) // p依次指向u的邻接顶点 if(!visited[p->data.adjvex]) // u的邻接顶点尚未被访问 { visited[p->data.adjvex]=TRUE; // 该邻接顶点设为已被访问 Visit(G.vertices[p->data.adjvex].data); // 访问该邻接顶点 EnQueue(Q,p->data.adjvex); // 入队该邻接顶点序号 } } } printf("\n");}void Display(ALGraph G){ // 输出图的邻接矩阵G int i; ArcNode *p; switch(G.kind) { case DG: printf("有向图\n"); break; case DN: printf("有向网\n"); break; case UDG:printf("无向图\n"); break; case UDN:printf("无向网\n"); } printf("%d个顶点：\n",G.vexnum); for(i=0;i
               
                data.adjvex) // 有向或无向两次中的一次 { printf("%s→%s ",G.vertices[i].data,G.vertices[p->data.adjvex].data); if(G.kind%2) // 网 printf(":%d ",*(p->data.info)); } p=p->nextarc; } printf("\n"); }}

// main7-2.cpp 检验bo7-2.cpp的主程序#include"c1.h"#define MAX_NAME 3 // 顶点字符串的最大长度+1typedef int InfoType; // 网的权值类型typedef char VertexType[MAX_NAME]; // 顶点类型为字符串#include"c7-21.h"#include"bo7-2.cpp"void print(char *i){	printf("%s ",i);}void main(){	int i,j,k,n;	ALGraph g;	VertexType v1,v2;	printf("请顺序选择有向图,有向网,无向图,无向网\n");	for(i=0;i<4;i++) // 验证4种情况	{		CreateGraph(g);		Display(g);		printf("插入新顶点，请输入顶点的值: ");		scanf("%s",v1);		InsertVex(g,v1);		printf("插入与新顶点有关的弧或边，请输入弧或边数: ");		scanf("%d",&n);		for(k=0;k

代码的运行结果：

请顺序选择有向图,有向网,无向图,无向网

请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): 0

请输入图的顶点数,边数: 2,1

请输入2个顶点的值(<3个字符):

a1 a2

请输入每条弧(边)的弧尾和弧头(以空格作为间隔):

a2 a1

有向图(见图721)

2个顶点：

a1 a2

1条弧(边):