数据结构—图的存储结构-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构—图的存储结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

6.图

回顾：数据的逻辑结构

集合——数据元素间除 “同属于一个集合” 外，无其他关系。

线性结构——一个对一个，如线性表、栈、队列

树形结构——一个对多个，如树

图形结构——多个对多个，如图

6.1图的定义和术语

图: G=(V,E)
    V:顶点（数据元素）的有穷非空集合； 
    E:边的有穷集合。

无向图：每条边都是无方向的；

有向图：每条边都是有方向的。

数据结构—图的存储结构,数据结构考研,数据结构

完全图：任意两个点都有一条边相连。

无向完全图：n 个顶点，n(n-1)/2条边

有向完全图：n 个顶点，n(n-1)条边

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NdIzTjfy-1691238142116)(https://ts1.cn.mm.bing.net/th/id/R-C.bf9aad94a55a06758f0d0d4a2aa083bf?rik=VscqICD0R7hR%2fA&riu=http%3a%2f%2fdata.biancheng.net%2fuploads%2fallimg%2f190103%2f2-1Z103210110O8.gif&ehk=Oi7hLl6AEIQ%2f1UfWj%2fAO6riRvAKN51BTFvzwxhq%2bGSE%3d&risl=&pid=ImgRaw&r=0)]

稀疏图：有很少边或弧的图（e<nlogn）。

稠密图：有较多边或弧的图。

网：边/弧带权的图。

邻接：有边/弧相连的两个顶点之间的关系。

存在（v_i,v_j），则称v_i和v_j互为邻接点；

存在 <v_i,v_j>，则称v_i邻接到v_j，v_j邻接到v_i

关联（依附）：边/弧与顶点之间的关系。

存在（v_i,v_j）/ <v_i,v_j>，则称该边/弧关联于v_i和v_j

顶点的度：与该顶点相关联的边的数目，记为TD(v)

在有向图中，顶点的度等于该顶点的入度与出度之和。

顶点v的入度是以v为顶点的有向边的条数，记作ID(v)

顶点v的出度是以v为始点的有向边的条数，记作OD(v)

数据结构—图的存储结构,数据结构考研,数据结构

问：当有向图中仅1个顶点的入度为0，其余顶点的入度均为1，此时是何形状？

答：是树！而且是一棵有向树！

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rztk0NIk-1691238142118)(https://ts1.cn.mm.bing.net/th/id/R-C.4f3bd2363f037cff739f8e388db9b321?rik=W0cQmZrsrYAcEA&riu=http%3a%2f%2fivr-ahnu.cn%2flectures%2fos%2fimages%2f24.jpg&ehk=rL%2blBOSUE1GCU30Sl09HWmQqTnbVhZDKEDVVUvJxi1U%3d&risl=&pid=ImgRaw&r=0)]

路径：接续的边构成的顶点序列。

路径长度：路径上边或弧的数目/权值之和。

回路（环）：第一个顶点和最后一个顶点相同的路径。

简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。

简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的路径。

数据结构—图的存储结构,数据结构考研,数据结构

连通图（强连通图）

在无（有）向图G=(V,{E})中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）。

数据结构—图的存储结构,数据结构考研,数据结构

权与网

图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。

带权的图称为网。

子图

设有两个图G=(V,{E})、G1=(V1,{E1})，若V1⊆V,E1⊆E，则称G1是G的子图。

例：（b），（c）是（a）的子图

数据结构—图的存储结构,数据结构考研,数据结构

连通分量（强连通分量）

无向图G的极大连通子图称为G的连通分量。

极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。
有向图G的极大强连通子图称为G的强连通分量。

极大强连通子图意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。
极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。
生成树：包含无向图G所有顶点的极小连通子图。
生成森林：对非连通图，由各个连通分量的生成树的集合。

6.2图的存储结构

图的逻辑结构：多对多

图没有顺序存储结构，但可以借助二维数组来表示元素间的关系。

6.2.1邻接矩阵

1、数组（邻接矩阵）表示法

建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。
- 设图A=(V,E)有 n 个顶点。
- 图的邻接矩阵是一个二维数组。

无向图的邻接矩阵表示法

存在关系记为1，没有关系记为0

数据结构—图的存储结构,数据结构考研,数据结构

分析1：无向图的邻接矩阵是对称的。

分析2：顶点 i 的度 = 第 i 行（列）中1的个数。

特别：完全图的邻接矩阵中，对角元素为0，其余为1。

有向图的邻接矩阵表示方法

数据结构—图的存储结构,数据结构考研,数据结构

注：在有向图的邻接矩阵中，

第 i 行含义：以结点v_i为尾的弧（即出度边）；

第 i 列含义：以结点v_i为头的弧（即入度边）。

分析1：有向图的邻接矩阵可能是不对称的。

分析2：顶点的出度 = 第i行元素之和

顶点的入度 = 第i列元素之和

顶点的度 = 第i行元素之和 + 第i列元素之和

网（即有权图）的邻接矩阵表示法

数据结构—图的存储结构,数据结构考研,数据结构

邻接矩阵存储表示，用两个数组分别存储顶点表和邻接矩阵。

#define MaxInt 32767
#define MVNum 100  //最大顶点数
typedef char VerTexType;//设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
typedef struct{
  VerTexType vexs[MVNum];//顶点表
  ArcType arcs[MVNum][MVNum];//邻接矩阵
  int vexnum,arcnum;
}AMGraph;

2、采用邻接矩阵表示法创建无向网

算法思想：

输入总顶点数和总边数。
依次输入点的信息存入顶点表中。
初始化邻接矩阵，使每个权值初始化为最大值。
构造邻接矩阵。

Status CreateUDN(AMGraph &G){
  cin>>G.vexnum>>G.arcnum;//输入总顶点数，总边数
  for(i=0;i<G.vexnum;++i)
    cin>>G.vexs[i];//依次输入点的信息
  for(i=0;i<G,vexnum;++i)
    for(j=0;j<G.vexnum;++j)
      G.arcs[i][j]=MaxInt;//边的权值均设置为极大值
  for(k=0;k<G.arcnum;++k){
    cin>>v1>>v2>>w;//输入一条边所依附的顶点及边的权值
    i=LocateVex(G,v1);
    j=LocateVex(G,v2);//确定v1和v2在G中的位置
    G.arcs[i][j]=w;//边<v1，v2>的权值置为w
    G.arcs[j][i]=G.arcs[i][j];//置<v1，v2>的对称边<v2,v1>的权值为w
  }
  return OK;
}

补充算法：在图中查找顶点

int LocateVex(AMGraph G,VertexType u){
  int i;
  for(i=0;i<G.vexnum;++i)
    if(u==G.vexs[i]) return i;
  return -1;
}

3、邻接矩阵的优缺点

数据结构—图的存储结构,数据结构考研,数据结构

邻接矩阵有什么优点？

直观、简单、好理解
方便检查任意一对顶点间是否存在边
方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
方便计算任一顶点的“度”（从该店发出的边数为“出度”，指向该点的边数为“入度”）
- 无向图：对应行（或列）非0元素的个数
- 有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”。

邻接矩阵的缺点？

不便于增加和删除顶点
浪费空间——存稀疏图（点很多而边很少）有大量无效元素

——对稠密图（特别是完全图）还是很合算的
浪费时间——统计稀疏图中一共有多少条边。

6.2.2邻接表

1、邻接表表示法（链式）

数据结构—图的存储结构,数据结构考研,数据结构

顶点：按编号顺序将顶点数据存储在一维数组中；
关联同一顶点的边（以顶点为尾的弧）：用线性链表存储

无向图邻接表

特点：

邻接表不唯一
若无向图中有n个顶点，e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图。
无向图中顶点的度为第i个单链表中的结点数。

数据结构—图的存储结构,数据结构考研,数据结构

有向图邻接表

特点：找出度易，找入度难

顶点的出度就是第i个单链表中的结点个数。
顶点的入度为整个单链表中邻接点域值是i-1的结点个数。

数据结构—图的存储结构,数据结构考研,数据结构

图的邻接表存储表示

顶点的结点结构

typedef struct VNode{
  VerTexType data;//顶点信息
  ArcNode *firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];//AdjList表示邻接表类型

说明：例如，AdjList v; 相当于：VNode v[MVNum];

弧（边）的结点结构

#define MVNum 100
typedef struct ArcNode{//边结点
  int adjvex;//该边所指向的顶点的位置
  struct ArcNode *nextarc;//指向下一条边的指针
  OtherInfo info;//和边相关的信息
}ArcNode;

图的结构定义

typedef struct{
  AdjList vertices;
  int vexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;

2、采用邻接表创建无向网

算法思想：

输入总顶点数和总边数
建立顶点表

依次输入点的信息存入顶点表中

使每个表头结点的指针域初始化为NULL
创建邻接表

依次输入每条边依附的两个顶点

确定两个顶点的序号i和j，建立边结点

将此边结点分别插入到v_i和v_j对应的两个边链表的头部

Status CreateUDG(ALGraph &G){
  cin>>G.vexnum>>G.arcnum;//输入总顶点数，总边数
  for(i=0;i<G.vexnum;++i){//输入各点，构造表头结点表
    cin>>G.vertices[i].data;//输入顶点值
    G.vertices[i].firstarc=NULL;//初始化表头结点的指针域
  }
  for(k=0;k<G.arcnum;++k){//输入各边，构造邻接表
    cin>>v1>>v2;//输入一条边依附的两个顶点
    i=LocateVex(G,v1);
    j=LocateVex(G.v2);
    p1=new ArcNode;//生成一个新的边结点*p1
    p1->adjvex=j;//邻接点序号为j
    pi->nextarc=G.vertices[i].firstarc;
    G.vertices[i].firstarc=p1;//将新结点*p1插入顶点vi的边表头部
    p2=new ArcNode;//生成另一个对称的新的边结点
    p2->adjvex=i;
    p2->nextarc=G.vertices[j].firstarc;
    G.vertices[j].firstarc=p2;//将新结点*p2插入顶点vj的边表头部
  }
  return OK;
}