鱼C论坛

 找回密码
 立即注册
查看: 1317|回复: 10

[学习笔记] ★ 第五十六讲 图的存储结构3 |【邻接矩阵】★

[复制链接]
最佳答案
243 
发表于 2017-11-21 19:22:04 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

                               
登录/注册后可看大图


    


用一节课的时间,提高生活幸福感

------小甲鱼


欢乐傻笑并存

智慧邪恶同在


笔记内涵------





图的存储结构


图的存储结构相比较线性表与树来说就复杂很多。

我们回顾下:

        对于线性表来说,是一对一的关系,所以用数组或者链表均可简单存放。

        树结构是一对多的关系,所以我们要将数组和链表的特性结合在一起才能更好的存放。


那么我们的图,是多对多的情况,另外图上的任何一个顶点都可以被看作是第一个顶点,任一顶点的邻接点之间也不存在次序关系。

我们仔细观察以下几张图,然后深刻领悟一下:
Snip20171121_97.png
Snip20171121_98.png
Snip20171121_99.png
Snip20171121_100.png


你发现了吗:
游客,如果您要查看本帖隐藏内容请回复


因为任意两个顶点之间都可能存在联系

因此无法以数据元素在内存中的物理位置来表示元素之间的关系。
(内存物理位置是线性的,图的元素关系是平面的)

如果用多重链表来描述倒是可以做到,但在几节课前的树章节我们已经讨论过。

纯粹用多重链表导致的浪费是无法想像的
(如果各个顶点的度数相差太大,就会造成巨大的浪费)

所幸,前辈们已经帮想好了出路,我们接下来会谈图的五种不同的存储结构,大家做好准备哦~




邻接矩阵(无向图)


考虑到图是由顶点和边或弧两部分组成,合在一起比较困难。

那就很自然地考虑到分为两个结构来分别存储。

顶点因为不区分大小、主次

所以用一个一维数组来存储是狠不错的选择。

而边或弧由于是顶点与顶点之间的关系,一维数组肯定就搞不定了。

那我们不妨考虑用一个二维数组来存储。

于是我们的邻接矩阵方案就诞生了!

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图

一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

Snip20171121_101.png


我们可以设置两个数组,顶点数组为vertex[4]={V0,V1,V2,V3}。

边数组arc[4][4]为对称矩阵(0表示不存在顶点间的边,1表示顶点间存在边)。

对称矩阵:
        所谓对称矩阵就是n阶矩阵的元满足
  1. a[i][j]=a[j][i](0<=i,j<=n)
复制代码


即从矩阵的左上角到右下角的主对角线为轴,右上角的元与左下角相对应的元全都是相等的。

有了这个二维数组组成的对称矩阵,我们就可以很容易地知道图中的信息:
        &#9674;要判定任意两顶点是否有边无边就非常容易了;

        &#9674;要知道某个顶点的度,其实就是这个顶点Vi在邻接矩阵中第i行(或第i列)的元素之和;

        &#9674;求顶点Vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[ i ][ j ]为1就是邻接点咯。





邻接矩阵(有向图)


无向图的边构成了一个对称矩阵,貌似浪费了一半的空间。

那如果是有向图来存放,会不会把资源都利用得很好呢?

Snip20171121_102.png


可见顶点数组vertex[4]={V0,V1,V2,V3},弧数组arc[4][4]也是一个矩阵。

但因为是有向图,所以这个矩阵并不对称。

例如由V1到V0有弧,得到arc[1][0]=1,而V0到V1没有弧,因此arc[0][1]=0。

另外有向图是有讲究的,要考虑入度和出度,顶点V1的入度为1。

正好是第V1列的各数之和,顶点V1的出度为2,正好是第V1行的各数之和。

在图的术语中,我们提到了这个概念,事实上也就是每条边上带有权的图就叫网。

Snip20171121_103.png


这里“∞”表示一个计算机允许的、大于所有边上权值的值。




代码实现


仅供参考:
  1. // 时间复杂度为O(n+n^2+e)

  2. #define MAXVEX 100                        // 最大顶点数
  3. #define INFINITY 65535                // 用65535来代表无穷大

  4. typedef struct
  5. {
  6.         char vexs[MAXVEX];                                // 顶点表
  7.         int arc[MAXVEX][MAXVEX];                // 邻接矩阵
  8.         int numVertexes, numEdges;                // 图中当前的顶点数和边数
  9. } MGraph;

  10. // 建立无向网图的邻接矩阵
  11. void CreateMGraph(MGraph *G)
  12. {
  13.         int i, j, k, w;
  14.        
  15.         printf("请输入顶点数和边数:\n");
  16.         scanf("%d %d", &G->numVertexes, &G->numEdges);
  17.        
  18.         for( i=0; i < G->numVertexes; i++ )
  19.         {
  20.                 scanf("%c", &G->vexs[i]);
  21.         }
  22.        
  23.         for( i=0; i < G->numVertexes; i++ )
  24.         {
  25.                 for( j=0; j < G->numVertexes; j++ )
  26.                 {
  27.                         G->arc[i][j] = INFINITY;                        // 邻接矩阵初始化
  28.                 }
  29.         }
  30.        
  31.         for( k=0; k < G->numEdges; k++ )
  32.         {
  33.                 printf("请输入边(Vi,Vj)上的下标i,下标j和对应的权w:\n");                // 这只是例子,提高用户体验需要进行改善
  34.                 scanf("%d %d %d", &i, &j, &w);
  35.                 G->arc[i][j] = w;
  36.                 G->arc[j][i] = G->arc[i][j];                        // 是无向网图,对称矩阵
  37.         }
  38. }
复制代码




这位鱼油,如果喜欢本系列笔记,请订阅 专辑&#9758;传送门)(不喜欢更要订阅

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2017-11-28 06:19:46 | 显示全部楼层
早起学习!!!!!!!!!!!!!

点评

我很赞同!: 5.0
我很赞同!: 5
  发表于 2017-11-28 07:59

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
不二如是 + 5 + 5 支持楼主!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-1-1 15:30:59 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-4-19 13:47:00 From FishC Mobile | 显示全部楼层
为什么我执行CreateMGraph函数里面的scanf函数后程序就不执行了,显示停止工作
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-4-20 20:25:08 | 显示全部楼层
lijialijialijia 发表于 2018-4-19 13:47
为什么我执行CreateMGraph函数里面的scanf函数后程序就不执行了,显示停止工作

在main主函数中先定义变量G,然后为这个指针申请动态存储空间,否则会提示指针没有初始化。

MGraph *G;
G=(MGraph*)malloc(sizeof(MGraph));
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-5-4 15:49:32 | 显示全部楼层
仅供参考
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-5-8 19:33:29 | 显示全部楼层
23424242424242
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-5-14 21:24:08 | 显示全部楼层
都是同一个图
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-5-23 16:42:28 | 显示全部楼层
线性表、树、图
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2018-11-22 21:15:27 | 显示全部楼层
代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2018-12-11 16:14

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表