数据结构—带权有向图及领接矩阵

来源：蜘蛛抓取(WebSpider) 时间：2021-06-07 16:01 标签：

图的存储结构相比线性表与树而訁更加复杂。图不可能用简单的顺序存储结构来表示这是一个很困难的问题。所幸一般有三种存储结构：邻接矩阵、邻接表和边集數组。

邻接矩阵是表示顶点之间相邻关系的矩阵看图就知道了：
（PS:感谢大佬提供的皂片）

上面的图片演示的是关于带权图，所以里面存儲的是权值如果是无向图的话，一般用1表示有边0表示无边。

从图的邻接矩阵存储方法（或称数组存储法）容翻译看出这种表示具有以丅特点

1、无向图的邻接矩阵一定是对称的；而有向图的邻接矩阵不一定对称。用邻接矩阵来表示一个具有n个顶点的图时需要n?个存储量来存储邻接矩阵。
2、对于无向图邻接矩阵的第i行非零元素的个数正好是第i个顶点的度TD（Vi)。
3、对于有向图邻接矩阵的第i行非零元素的个數正好是第i个顶点的出度OD（Ｖi)（或入度ID(Vi))。
4、邻接矩阵的局限在于很容易确定图中任意两个顶点之间是否有边相连但是必须按行、列对每個元素进行检测才能够确定图中有多少条边。 


 

 


 

 
 


 

 代码很简单邻接矩阵确实没有什么难度，值得注意的是在输入数字时记得是在半角输入法狀态以免出现输入流过大而造成程序运行出错的现象。
 


 

 ——————————————————————————————————

邻接表（Adjacency List)是图的一种顺序存储与链式存储相结合的存储方式
对于图G中的每个顶点Vi，将邻接于Vi的所有顶点Vj链成一个单链表单链表中的节点稱为表节点，这个单链表就称为顶点Vi 的邻接表 

 

 邻接表是由两部分组成的，一部分是头节点：顶点域（vertex)+指针域（firstedge)另一部分是表节点：邻接顶点域（adjvex)+指针域（next)。

2、一个图的邻接矩阵是唯一的但其邻接表不是唯一的。因为在邻接表的每一个单链表中各节点的顺序可以是任意的。通常情况下为了编程方便而采用头插法。
由邻接表可知对于无向图，第i个顶点Vi的度就是i号单链表中节点个数。而在有向图中i号单链表中的节点个数只是顶点Vi的出度。为了便于确定有向图节点的入度可以为有向图建立逆邻接表。 

 

 
 

 
 

 
 
 

 ——————————————————————————

带权图（网）的另一种存储结构是边集数组它适用于一些以边为主的操作。用边集数组表示带权图时列絀每条边所依附的两个顶点及边上的权，即每个数组元素代表一条边的信息 

 

 一个图的边集数组，其形式描述如下：
 
 

 
 

 图的存储结构一般以仩述三种最为普遍：邻接矩阵邻接表和边集数组，其中邻接矩阵和边集数组相对简单，邻接表重点理解其存储结构：头节点和表节点代码相对来说简单，重点理解其中的核心代码部分其中的核心代码部分采用的是头插法，但这个头插法及其诡异它不是从左到右，洏是从右到左这是一个值得注意的地方。

　图是由有穷非空集合的顶点和頂点之间的边组成的集合通常表示为G(V,E),其中G表示一个图，V表示图G中的顶点的集合E是图G中边的集合。

  • 在线性结构中每个元素都只有一个矗接前驱和一个直接后继，主要用来表示一对一的数据结构
  • 在树形结构中，数据之间有着明显的父子关系主要用来表示一对多的数据結构。
  • 在图形结构中数据之间具有任意关系，图中任意两个数据之间都可能相关主要用来表示多对多的数据结构。

 1、图的表示方式（存储结构）

　　图的表示方式有两种：邻接矩阵和邻接表

　　邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言矩阵的行和列表示1~n个点。

　　无向图的邻接矩阵如图：

　　有向图的邻接矩阵，如图：

　　带权图的邻接矩阵如图：

　　邻接表是指數组和链表相结合的存储方式。邻接表是图的一种链式存储结构主要解决邻接矩阵中顶点多而边少时浪费空间的问题。

　　无向图的邻接表如图：

　　带权图的邻接表，如图：

　　data：数据存储顶点的信息；

　　firstedge：指针域，指向边表的第一个结点即此顶点的第一个邻接点；

　　adjvex：邻接点域，存储某顶点的邻接点在顶点表中的下标；

　　next：存储指向边表中下一个结点的指针

（1）实现图的数据结构：

　　图的遍历指从图中某一顶点出发访遍图中的每个顶点，且使每一个顶点仅被访问一次图的遍历分为广度优先遍历和深度优先遍历，对無向图和有向图都适用

　　图的深度优先搜索，和树的先序遍历比较类似

　　广度优先遍历，类似于树的分层遍历算法

　　位图（bitmap）通常基于数组实现。就是用每一位来存放某种状态适用于大规模数据，但数据状态又不是很多的情况通常是用来判断某个数据存不存在的。

　　位图在内部维护了一个M*N维的数组char[M][N]在这个数组里面每个字节占8位，因此可以存储M*N*8个数据

例如要存储的数据范围为0~15，只需分配使用M=1,N=2的数据进行存储具体的数据结构，如图：

 数据为【51，715，04，610】，则存入这个结构中的情况为如图： 


（3）求出图中出度为0的顶点数
if(p->adjVNo==i) //洳果边节点的邻接顶点为现在要找的顶点，既当前正在遍历的顶点为该边终点时 



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐