备案控制台
探索云世界
开发者社区 云计算 文章 正文

有向图的邻接表表示法

2017-12-04 1239
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

图的邻接表表示法类似于树的孩子链表表示法。对于图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.代码实例

[c-sharp]  view plain copy print ?
  1. #include<iostream>  
  2. using namespace std;  
  3. #define MAX_VERTEX_NUM 50//定义图的最大顶点数  
  4. typedef char VertexData;  
  5. typedef struct EdgeNode//表结点  
  6. {  
  7.     int adjvex;//邻接点域  
  8.     VertexData data;  
  9.     EdgeNode *next;//边结点所对应的下一个边结点  
  10. } EdgeNode;  
  11. typedef struct VertexNode//头结点  
  12. {  
  13.     VertexData data;  
  14.     EdgeNode *firstedge;//头结点所对应的第一个边结点  
  15. }VertexNode;  
  16. typedef struct AdjList  
  17. {  
  18.     int VexNum,ArcNum;//定义图的顶点数和边数  
  19.     VertexNode vertex[MAX_VERTEX_NUM];//定义头结点数组。  
  20. }AdjList;  
  21. void CreateGraph(AdjList *adj,int *n)  
  22. {  
  23.     int e,s,d;  
  24.     cout<<"输入顶点数和边数"<<endl;  
  25.     cin>>*n>>e;//输入顶点数和边数。  
  26.     adj->VexNum=*n;  
  27.     adj->ArcNum=e;  
  28.     EdgeNode *q=NULL;  
  29.     //初始化表头结点  
  30.     int i;  
  31.     for(i=1;i<=*n;i++)  
  32.     {  
  33.         cout<<"输入第"<<i<<"个结点的顶点名称"<<endl;  
  34.         cin>>adj->vertex[i].data;//顶点名称，是一个字符  
  35.         adj->vertex[i].firstedge=NULL;  
  36.     }  
  37.     for(i=1;i<=e;i++)  
  38.     {  
  39.         cout<<"输入第"<<i<<"条边的起点和终点"<<endl;  
  40.         cin>>s>>d;//输入边的起始和终止  
  41.        // cout<<"输入表结点信息"<<endl;  
  42.         q=(EdgeNode *)malloc(sizeof(EdgeNode));//创建一个表结点  
  43.         if(q==NULL)  
  44.             return;  
  45.         q->adjvex=d;  
  46.     //  cin>>q->data;  
  47.         q->next=adj->vertex[s].firstedge;//新加入的节点都是在头结点之后，原来在头结点之后的节点要后移。  
  48.         adj->vertex[s].firstedge=q;  
  49.     }  
  50. }  
  51. void DisplayGraph(AdjList *adj)  
  52. {  
  53.     int n=adj->VexNum;//顶点个数，后面要遍历每一个点点  
  54.     EdgeNode *q=NULL;  
  55.     int i;  
  56.     for( i=1;i<=n;i++)  
  57.     {  
  58.     //  cout<<n<<endl;  
  59.         q=adj->vertex[i].firstedge;  
  60.         if(q==NULL)//表示头结点后面没有跟其他结点  
  61.         {  
  62.             cout<<"没用从"<<adj->vertex[i].data<<"出发的节点"<<endl;  
  63.         }  
  64.         else  
  65.         {  
  66.             cout<<"从结点"<<adj->vertex[i].data<<"出发的边有"<<endl;  
  67.             while(q!=NULL)  
  68.             {  
  69.             //  cout<<adj->vertex[i].data<<"->"<<q->data<<endl;  
  70.                 cout<<adj->vertex[i].data<<"->"<<adj->vertex[q->adjvex].data<<endl;  
  71.                 q=q->next;  
  72.             }  
  73.         }  
  74.     }  
  75. }  
  76. void main()  
  77. {  
  78.     int n;  
  79.     AdjList *adj=(AdjList *)malloc(sizeof(AdjList));  
  80.     CreateGraph(adj,&n);  
  81.     DisplayGraph(adj);  
  82. //  cout<<"hello world!"<<endl;  
  83. }  
 

输出结果为：

[c-sharp]  view plain copy print ?
  1. 输入顶点数和边数  
  2. 6 6  
  3. 输入第1个结点的顶点名称  
  4. a  
  5. 输入第2个结点的顶点名称  
  6. b  
  7. 输入第3个结点的顶点名称  
  8. c  
  9. 输入第4个结点的顶点名称  
  10. d  
  11. 输入第5个结点的顶点名称  
  12. e  
  13. 输入第6个结点的顶点名称  
  14. f  
  15. 输入第1条边的起点和终点  
  16. 1 3  
  17. 输入第2条边的起点和终点  
  18. 2 4  
  19. 输入第3条边的起点和终点  
  20. 2 1  
  21. 输入第4条边的起点和终点  
  22. 4 3  
  23. 输入第5条边的起点和终点  
  24. 3 6  
  25. 输入第6条边的起点和终点  
  26. 3 5  
  27. 从结点a出发的边有  
  28. a->c  
  29. 从结点b出发的边有  
  30. b->a  
  31. b->d  
  32. 从结点c出发的边有  
  33. c->e  
  34. c->f  
  35. 从结点d出发的边有  
  36. d->c  
  37. 没用从e出发的节点  
  38. 没用从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。

[c-sharp]  view plain copy print ?
  1. #include<iostream>  
  2. #include<stdlib.h>  
  3. using namespace std;  
  4. #define MAX_VERTEX_NUM 50//定义图的最大顶点数  
  5. typedef char VertexData;//顶点名称是字符型。  
  6. typedef struct EdgeNode//表结点  
  7. {  
  8.     int adjvex;//邻接点域  
  9.     VertexData data;  
  10.     EdgeNode *next;//表结点所对应的下一个表结点  
  11. } EdgeNode;  
  12. typedef struct VertexNode//头结点  
  13. {  
  14.     VertexData data;  
  15.     EdgeNode *firstedge;//头结点所对应的第一个表结点  
  16. }VertexNode;  
  17. typedef struct AdjList//图的数据结构  
  18. {  
  19.     int VexNum,ArcNum;//定义图的顶点数和边数  
  20.     VertexNode vertex[MAX_VERTEX_NUM];//定义头结点数组。  
  21. }AdjList;  
  22. void CreateGraph(AdjList *adj)  
  23. {  
  24.     int s,d;  
  25.     int i;  
  26.     cout<<"输入顶点数和边数"<<endl;  
  27.     cin>>adj->VexNum>>adj->ArcNum;//输入图的顶点数和边数。  
  28.     EdgeNode *q=NULL;//定义表结点  
  29.     //初始化表头结点  
  30.     cout<<"输入"<<adj->VexNum<<"个头结点的名称"<<endl;  
  31.     for(i=1;i<=adj->VexNum;i++)  
  32.     {  
  33.         //adj->vertex[i]是头结点数组  
  34.         cin>>adj->vertex[i].data;//顶点名称，是一个字符  
  35.         adj->vertex[i].firstedge=NULL;//初始状态下头结点后面不跟表结点，因此firstedge=null  
  36.     }  
  37.     //在初始化头结点以后，就需要开始将表结点添加到头结点后面去。  
  38.     cout<<"输入"<<adj->ArcNum<<"条边的起点和终点"<<endl;  
  39.     for(i=1;i<=adj->ArcNum;i++)  
  40.     {  
  41.         cin>>s>>d;//输入边的起始和终止，起始s就是头结点位置，终止d就是表结点位置  
  42.         q=(EdgeNode *)malloc(sizeof(EdgeNode));//创建一个表结点，为其分配空间  
  43.         if(q==NULL)  
  44.             return;  
  45.         /* 
  46.         如果原来的链表是s->a->b-c>，现在要加入一个表结点q，那么加入以后就变成了s->q->a->b->c 
  47.         因此： 
  48.         1.q所指向的应该是当前s所指向的元素。 
  49.         2.q的邻接点域是d 
  50.         3.s的指针指向q 
  51.         操作如以下三行代码 
  52.         */  
  53.         q->adjvex=d;//表结点的邻接点域是d  
  54.         q->next=adj->vertex[s].firstedge;//新加入的节点都是在头结点之后，原来在头结点之后的节点要后移。  
  55.         adj->vertex[s].firstedge=q;  
  56.     }  
  57. }  
  58. void DisplayGraph(AdjList *adj)  
  59. {  
  60.     int n=adj->VexNum;//顶点个数，后面要遍历每一个点点  
  61.     EdgeNode *q=NULL;  
  62.     int i;  
  63.     for( i=1;i<=adj->VexNum;i++)  
  64.     {  
  65.     //  cout<<n<<endl;  
  66.         q=adj->vertex[i].firstedge;//q为头结点i所指向的表结点，i->q之间存在边  
  67.         if(q==NULL)//表示头结点后面没有跟其他结点  
  68.         {  
  69.             cout<<"没用从"<<adj->vertex[i].data<<"出发的节点"<<endl;  
  70.         }  
  71.         else  
  72.         {  
  73.             cout<<"从结点"<<adj->vertex[i].data<<"出发的边有"<<endl;  
  74.             while(q!=NULL)  
  75.             {  
  76.             //  cout<<adj->vertex[i].data<<"->"<<q->data<<endl;  
  77.                 cout<<adj->vertex[i].data<<"->"<<adj->vertex[q->adjvex].data<<endl;  
  78.                 q=q->next;//链表往后跳  
  79.             }  
  80.         }  
  81.     }  
  82. }  
  83. void main()  
  84. {  
  85.     int n;  
  86.     AdjList *adj=(AdjList *)malloc(sizeof(AdjList));  
  87.     CreateGraph(adj);  
  88.     DisplayGraph(adj);  
  89.     system("pause");  
  90. }  
  91. /* 
  92. 输入顶点数和边数 
  93. 6 6 
  94. 输入6个头结点的名称 
  95. a b c d e f 
  96. 输入6条边的起点和终点 
  97. 1 3 
  98. 2 4 
  99. 2 1 
  100. 4 3 
  101. 3 6 
  102. 3 5 
  103. 从结点a出发的边有 
  104. a->c 
  105. 从结点b出发的边有 
  106. b->a 
  107. b->d 
  108. 从结点c出发的边有 
  109. c->e 
  110. c->f 
  111. 从结点d出发的边有 
  112. d->c 
  113. 没用从e出发的节点 
  114. 没用从f出发的节点 
  115. 请按任意键继续. . . 
  116. */  

 



本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2011/04/15/2297028.html，如需转载请自行联系原作者


文章标签：
存储
嗯哼9925
目录
相关文章
闻缺陷则喜何志丹
|
14天前
|
人工智能 算法 测试技术
【图论】【拓扑排序】1857. 有向图中最大颜色值
【图论】【拓扑排序】1857. 有向图中最大颜色值
闻缺陷则喜何志丹
18 1
为梦而生~
|
5月前
|
存储 机器学习/深度学习 人工智能
图的存储及基本操作总结（邻接矩阵、邻接表）及C/C++代码实现
图的存储及基本操作总结（邻接矩阵、邻接表）及C/C++代码实现
为梦而生~
485 0
dm2e66eopcgq6
|
11月前
有向图、无向图找环
笔记
dm2e66eopcgq6
91 0
Lucky小黄人^_^
用邻接表表示图
用邻接表表示图
Lucky小黄人^_^
29 0
壹佰、
|
算法 Java
利用Dijkstra算法求顶点v1到其他各顶点的最短路径Java实现
利用Dijkstra算法求顶点v1到其他各顶点的最短路径Java实现
壹佰、
86 0
利用Dijkstra算法求顶点v1到其他各顶点的最短路径Java实现
CastenWang
|
机器学习/深度学习
有向图，无向图的邻接矩阵和邻接表模板
有向图，无向图的邻接矩阵和邻接表模板
CastenWang
151 0
有向图，无向图的邻接矩阵和邻接表模板
CastenWang
拓扑排序（邻接表实现）
拓扑排序（邻接表实现）
CastenWang
140 0
拓扑排序（邻接表实现）
zzqwtc
邻接表
笔记
zzqwtc
52 0
kyxdt4sqtmta6
|
存储 JavaScript 算法
邻接表详解（C/C++）
目录 一、概念 二、分类 1）无向图的邻接表 2）有向图的邻接表（出弧） 3）有向图的逆邻接表（入弧） 三.步骤 四、代码
kyxdt4sqtmta6
544 0
邻接表详解（C/C++）
川川菜鸟
|
算法
无向图邻接表（深度优先算法）
无向图邻接表（深度优先算法）
川川菜鸟
104 0

热门文章

最新文章

  • 1
    疑犯追踪第一季/全集Person Of Interest迅雷下载
  • 2
    【直播系列之一】1篇文章看懂峰值带宽、流量、转码、连麦、截图五大直播计费方式
  • 3
    理解事务的4种隔离级别
  • 4
    阿里云网站域名备案流程全过程讲解(图文)
  • 5
    在服务器的raid1中安装windows server系统（踩坑记录）
  • 6
    如何用Vue实现简易的富文本编辑器，并支持Markdown语法
  • 7
    怎么才能快速提高小程序留存率！
  • 8
    程序员请放下浮躁的心
  • 9
    如何解决域中普通用户只限于10台客户机加入域的数量问题
  • 10
    博客园模板 样式优化
  • 1
    未来技术纵横谈：区块链、物联网与虚拟现实的融合与创新
    34
  • 2
    软件体系结构 - 缓存技术（9）缓存穿透
    29
  • 3
    提升Android应用性能的实用技巧
    31
  • 4
    工具变量法(两阶段最小二乘法2SLS)线性模型分析人均食品消费时间序列数据和回归诊断（下）
    32
  • 5
    软件体系结构 - 缓存技术（8）缓存雪崩
    35
  • 6
    软件体系结构 - 缓存技术（7）Redis持久化方法
    35
  • 7
    Python用KShape对时间序列进行聚类和肘方法确定最优聚类数k可视化
    24
  • 8
    软件体系结构 - 缓存技术（6）淘汰策略
    31
  • 9
    基于R语言股票市场收益的统计可视化分析
    33
  • 10
    软件体系结构 - 数据分片（2）一致性哈希分片
    35

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）