有向图的邻接表表示法

ゝ一纸荒年。 2022-03-28 05:38 240阅读 0赞

图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表(Adjacency List)。  
  
**1． 邻接表的结点结构**

（1）表结点结构  
┌────┬───┐   
│adjvex │next │  
└────┴───┘  
　邻接表中每个表结点均有两个域:  
　① 邻接点域adjvex  
　　存放与vi相邻接的顶点vj的序号j。  
　② 链域next  
　　将邻接表的所有表结点链在一起。  
注意：  
　 若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域。  
  
（2）头结点结构  
┌────┬─────┐   
│vertex │firstedge │  
└────┴─────┘  
　顶点vi邻接表的头结点包含两个域：  
　① 顶点域vertex  
　　存放顶点vi的信息  
　② 指针域firstedge  
　　vi的邻接表的头指针。  
注意：  
　 ① 为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。  
　② 有时希望增加对图的顶点数及边数等属性的描述，可将邻接表和这些属性放在一起来描述图的存储结构。

## 2.代码实例 ##

\#include<iostream> using namespace std; \#define MAX\_VERTEX\_NUM 50//定义图的最大顶点数 typedef char VertexData; typedef struct EdgeNode//表结点 \{ int adjvex;//邻接点域 VertexData data; EdgeNode \*next;//边结点所对应的下一个边结点 \} EdgeNode; typedef struct VertexNode//头结点 \{ VertexData data; EdgeNode \*firstedge;//头结点所对应的第一个边结点 \}VertexNode; typedef struct AdjList \{ int VexNum,ArcNum;//定义图的顶点数和边数 VertexNode vertex\[MAX\_VERTEX\_NUM\];//定义头结点数组。 \}AdjList; void CreateGraph(AdjList \*adj,int \*n) \{ int e,s,d; cout<<"输入顶点数和边数"<<endl; cin>>\*n>>e;//输入顶点数和边数。 adj->VexNum=\*n; adj->ArcNum=e; EdgeNode \*q=NULL; //初始化表头结点 int i; for(i=1;i<=\*n;i++) \{ cout<<"输入第"<<i<<"个结点的顶点名称"<<endl; cin>>adj->vertex\[i\].data;//顶点名称，是一个字符 adj->vertex\[i\].firstedge=NULL; \} for(i=1;i<=e;i++) \{ cout<<"输入第"<<i<<"条边的起点和终点"<<endl; cin>>s>>d;//输入边的起始和终止 // cout<<"输入表结点信息"<<endl; q=(EdgeNode \*)malloc(sizeof(EdgeNode));//创建一个表结点 if(q==NULL) return; q->adjvex=d; // cin>>q->data; q->next=adj->vertex\[s\].firstedge;//新加入的节点都是在头结点之后，原来在头结点之后的节点要后移。 adj->vertex\[s\].firstedge=q; \} \} void DisplayGraph(AdjList \*adj) \{ int n=adj->VexNum;//顶点个数，后面要遍历每一个点点 EdgeNode \*q=NULL; int i; for( i=1;i<=n;i++) \{ // cout<<n<<endl; q=adj->vertex\[i\].firstedge; if(q==NULL)//表示头结点后面没有跟其他结点 \{ cout<<"没用从"<<adj->vertex\[i\].data<<"出发的节点"<<endl; \} else \{ cout<<"从结点"<<adj->vertex\[i\].data<<"出发的边有"<<endl; while(q!=NULL) \{ // cout<<adj->vertex\[i\].data<<"->"<<q->data<<endl; cout<<adj->vertex\[i\].data<<"->"<<adj->vertex\[q->adjvex\].data<<endl; q=q->next; \} \} \} \} void main() \{ int n; AdjList \*adj=(AdjList \*)malloc(sizeof(AdjList)); CreateGraph(adj,&n); DisplayGraph(adj); // cout<<"hello world!"<<endl; \}

输出结果为：

输入顶点数和边数 6 6 输入第1个结点的顶点名称 a 输入第2个结点的顶点名称 b 输入第3个结点的顶点名称 c 输入第4个结点的顶点名称 d 输入第5个结点的顶点名称 e 输入第6个结点的顶点名称 f 输入第1条边的起点和终点 1 3 输入第2条边的起点和终点 2 4 输入第3条边的起点和终点 2 1 输入第4条边的起点和终点 4 3 输入第5条边的起点和终点 3 6 输入第6条边的起点和终点 3 5 从结点a出发的边有 a->c 从结点b出发的边有 b->a b->d 从结点c出发的边有 c->e c->f 从结点d出发的边有 d->c 没用从e出发的节点 没用从f出发的节点

## 3.代码实例2(ps:补充于2011-6-14) ##

总体而言，邻接表表示法中主要含有两种结点，分别是头结点和表结点(也叫做边结点)，在头结点(s)到表结点(d)之间存在着一条边。如果头结点后面有多个表结点，即s->d1->d2，则表示存在着两条边，分别是e(s,d1)和e(s,d2)。邻接表表示法中，头结点的数量是固定的，就是图中的顶点数量V，表结点的数量由边的数量来决定。如果是有向图，表结点的数量=边的数量；如果是无向图，则表结点的数量=边的数量\*2。

在构造图的时候，如果一个头结点后面有多个表结点，那么表结点按次序添加在头结点后面。比如原先有结构s->d1->d2，现在需要添加表结点d3，那么需要打断s->d1的指针，让d3指向d1，s指向d3。即s->d3->d1->d2。

\#include<iostream> \#include<stdlib.h> using namespace std; \#define MAX\_VERTEX\_NUM 50//定义图的最大顶点数 typedef char VertexData;//顶点名称是字符型。 typedef struct EdgeNode//表结点 \{ int adjvex;//邻接点域 VertexData data; EdgeNode \*next;//表结点所对应的下一个表结点 \} EdgeNode; typedef struct VertexNode//头结点 \{ VertexData data; EdgeNode \*firstedge;//头结点所对应的第一个表结点 \}VertexNode; typedef struct AdjList//图的数据结构 \{ int VexNum,ArcNum;//定义图的顶点数和边数 VertexNode vertex\[MAX\_VERTEX\_NUM\];//定义头结点数组。 \}AdjList; void CreateGraph(AdjList \*adj) \{ int s,d; int i; cout<<"输入顶点数和边数"<<endl; cin>>adj->VexNum>>adj->ArcNum;//输入图的顶点数和边数。 EdgeNode \*q=NULL;//定义表结点 //初始化表头结点 cout<<"输入"<<adj->VexNum<<"个头结点的名称"<<endl; for(i=1;i<=adj->VexNum;i++) \{ //adj->vertex\[i\]是头结点数组 cin>>adj->vertex\[i\].data;//顶点名称，是一个字符 adj->vertex\[i\].firstedge=NULL;//初始状态下头结点后面不跟表结点，因此firstedge=null \} //在初始化头结点以后，就需要开始将表结点添加到头结点后面去。 cout<<"输入"<<adj->ArcNum<<"条边的起点和终点"<<endl; for(i=1;i<=adj->ArcNum;i++) \{ cin>>s>>d;//输入边的起始和终止，起始s就是头结点位置，终止d就是表结点位置 q=(EdgeNode \*)malloc(sizeof(EdgeNode));//创建一个表结点，为其分配空间 if(q==NULL) return; /\* 如果原来的链表是s->a->b-c>，现在要加入一个表结点q，那么加入以后就变成了s->q->a->b->c 因此： 1.q所指向的应该是当前s所指向的元素。 2.q的邻接点域是d 3.s的指针指向q 操作如以下三行代码 \*/ q->adjvex=d;//表结点的邻接点域是d q->next=adj->vertex\[s\].firstedge;//新加入的节点都是在头结点之后，原来在头结点之后的节点要后移。 adj->vertex\[s\].firstedge=q; \} \} void DisplayGraph(AdjList \*adj) \{ int n=adj->VexNum;//顶点个数，后面要遍历每一个点点 EdgeNode \*q=NULL; int i; for( i=1;i<=adj->VexNum;i++) \{ // cout<<n<<endl; q=adj->vertex\[i\].firstedge;//q为头结点i所指向的表结点，i->q之间存在边 if(q==NULL)//表示头结点后面没有跟其他结点 \{ cout<<"没用从"<<adj->vertex\[i\].data<<"出发的节点"<<endl; \} else \{ cout<<"从结点"<<adj->vertex\[i\].data<<"出发的边有"<<endl; while(q!=NULL) \{ // cout<<adj->vertex\[i\].data<<"->"<<q->data<<endl; cout<<adj->vertex\[i\].data<<"->"<<adj->vertex\[q->adjvex\].data<<endl; q=q->next;//链表往后跳 \} \} \} \} void main() \{ int n; AdjList \*adj=(AdjList \*)malloc(sizeof(AdjList)); CreateGraph(adj); DisplayGraph(adj); system("pause"); \} /\* 输入顶点数和边数 6 6 输入6个头结点的名称 a b c d e f 输入6条边的起点和终点 1 3 2 4 2 1 4 3 3 6 3 5 从结点a出发的边有 a->c 从结点b出发的边有 b->a b->d 从结点c出发的边有 c->e c->f 从结点d出发的边有 d->c 没用从e出发的节点 没用从f出发的节点 请按任意键继续. . . \*/