当前位置:   article > 正文

非线性表——图——基本概念/存储结构_有6个顶点(顶点编号为a~f)的无向带权图g,其邻接矩阵a为上三角矩阵,按列为主

有6个顶点(顶点编号为a~f)的无向带权图g,其邻接矩阵a为上三角矩阵,按列为主

9.1基本概念

图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)。

其中: V(G)是顶点的有限集。 E(G)是边的有限集,边是顶点的无序对或有序对。

如果图G(V,E)和图G’(V’,E’),满足:    则称G’为G的子图。

有向图

E(G)是有向边(也称弧)的有限集,弧是顶点的有序对。

记为<v,w>,v,w是顶点,v为弧尾,w为弧头。

无向图

无向图G由两个集合V(G)和E(G)组成。

其中: V(G)是顶点的有限集。 E(G)是边的有限集,边是顶点的无序对。

记为(v,w)或(w,v),并且(v,w)=(w,v)。

完全图——有n个顶点和n(n-1)/2条边的无向图

有向完全图——有n个顶点和n(n-1)条弧的有向图

稀疏图——具有很少边或弧的图(如少于nlogn)

稠密图——具有很多边或弧的图

权——与图的边或弧相关的数

网——带权的图

对于无向图G=(V,E),若边(v, v’) ∈E,则称:v和 v’互为邻接点,边(v, v’)依附于顶点v和 v’,边(v, v’)和顶点v,v’相关联。

对于有向图G=(V,A),若弧<v, v’> ∈A,则称:v邻接到 v’, v’邻接自 v,弧<v, v’>和顶点v,v’相关联。

路径长度—沿路径边的数目或沿路径各边权值之和

简单路径—序列中顶点不重复出现的路径

简单回路—除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路

连通—从顶点V到顶点W有路径,则称V和W是连通的。

连通图—任意两个顶点都是连通的无向图。

强连通图—有向图G中,如果对每一对任意两点,从Vi到Vj和从Vj到Vi都存在路径,则称G是强连通图。

连通分量—非连通图的每一个连通部分称连通分量。

强连通分量—有向图中的强连通子图

有向树—若一有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一棵有向树。

有向图的生成森林—由若干棵有向树组成,

含有图中全部顶点,但只有足以构成若干棵互不相交的有向树的弧。

9.2存储结构

9.2.1邻接矩阵式

无向图的邻接矩阵对称,可压缩存储;

有n个顶点的无向图需存储空间为n(n+1)/2 。

有向图邻接矩阵不一定对称;

有n个顶点的有向图需存储空间为n²。

(1)无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 。

(2)有向图中顶点Vi的出度是A中第i行元素之和,顶点Vi的入度是A中第i列元素之和。

网络(带权的图)的邻接矩阵可定义为:

 

  1. #define MAX_VERTEX_NUM 20
  2. typedef enum{ DG,DN,AG,AN }GraphKind;
  3. //有向图 有向网 无向图 无向网
  4. //图的邻接矩阵
  5. typedef struct ArcCell {
  6. VRType adj; //顶点关系类型,无权图用10表示相邻否; 带权图则为权值类型
  7. InfoType *info; //边或弧相关信息指针
  8. }AdjMatrix[ MAX_VERTEX_NUM][MAX_VERTEX_NUM ];
  9. //图的表示
  10. typedef struct {
  11. VertexType vexs[MAX_VERTEX_NUM];//顶点向量
  12. AdjMatrix arcs; //邻接矩阵
  13. int vexnum,arcnum; //图的当前顶点数和弧数
  14. GraphKind kind; //图的种类标志
  15. }MGraph;

 

例题:

已知有一个6个顶点(顶点编号0-5)的有向带权图G,其邻接矩阵A为上三角矩阵,它的压缩存储如下:

 (1)写出图G的邻接矩阵A; (2)画出有向带权图G;

 

 9.2.2.1邻接表式

为图中每个顶点建立一个单链表

(1)无向图中顶点Vi的度为第i个单链表中的结点数;

(2)有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为所有单链表中邻接点域值是i的结点个数(必须遍历整个邻接表)。

缺点:判定vi,vj之间是否有边或弧,需搜索第i或j个链表,不及邻接矩阵方便。

第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧)

 n个顶点e条边,邻接表中有n个表头结点, 2e个边结点

n个顶点e条弧,邻接表中有n个头结点, e个弧结点

  1. //边(弧)结点
  2. typedef struct ArcNode {
  3. int adjvex;//邻接点域,存放与Vi邻接的点在表头数组中的位置
  4. struct ArcNode *nextarc;//链域,指示下一条边或弧
  5. InfoType *info;//存储与边或弧相关的信息,如权值
  6. }ArcNode ;
  1. //顶点结点
  2. typedef struct VNode{
  3. VertexType data; //存放顶点信息
  4. ArcNode *firstarc; //指示链表中第一个结点
  5. }VNode, AdjList[ MAX_VERTEX_NUM ];
  1. //图类型
  2. typedef struct{
  3. AdjList vertices;//顶点表列(邻接表)
  4. int vexnum, arcnum;//图的当前顶点数和弧数
  5. int kind;//图的种类标志
  6. }ALGraph;

9.2.2.2逆邻接表

为便于确定顶点的入度 ;

对每个结点建立以Vi为头的弧的单链表。

9.2.2.2十字链表

将有向图的邻接表,逆邻接表结合起来。

易找到以顶点Vi为尾的弧,以顶点Vi为头的弧 ;

易确定顶点的出度,入度。

 

  1. //弧结点
  2. typedef struct ArcBox {
  3. int tailvex, headvex;//弧尾、弧头在表头数组中位置
  4. struct ArcBox *hlink;//指向弧头相同的下一条弧
  5. struct ArcBox *tlink; //指向弧尾相同的下一条弧
  6. InfoType *info; //指向与弧相关的信息
  7. }ArcBox;
  1. //顶点结点
  2. typedef struct VexNode {
  3. VetexType data; //存储与顶点有关信息
  4. ArcBox *firstin;//指向以该顶点为弧头的第一个弧
  5. ArcBox *firstout; //指向以该顶点为弧尾的第一个弧
  6. }VexNode;
  1. //图结构
  2. typedef struct{
  3. VexNode xlist[MAX_VERTEX_NUM];//顶点表列
  4. int vexnum,arcnum;//图的当前顶点数和弧数
  5. }OLGraph;


9.2.3无向图的邻接表

邻接多重表与十字链表类似

 

  1. //边结点
  2. //每个边结点同时链接在两个链表上
  3. typedef struct EBox{
  4. VisitIf mark; //标志域
  5. int ivex,jvex; //边的两个顶点在表头数组中位置
  6. struct EBox *ilink,*jlink;
  7. //分别指向依附于ivex和jvex的下一条边
  8. InfoType *info; //指向与弧相关的信息
  9. }EBox;
  1. //顶点结点
  2. //每一个顶点只对应一个顶点结点
  3. //以顺序结构存储,以便随机访问某一顶点
  4. typedef struct VexBox{
  5. VertexType data; //存储与顶点有关的信息
  6. EBox *firstedge;//指向第一条依附于该顶点的边
  7. }VexBox;
  1. //图类型
  2. typedef struct {
  3. VexBox adjmulist[MAX_VERTEX_NUM]; // 顶点表列
  4. int vexnum, arcnum; //无向图的当前顶点数和弧数
  5. }AMLGraph;

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/873984
推荐阅读
相关标签
  

闽ICP备14008679号