图的定义和术语及存储结构共37页文档

}
3 67
adj
8
01 12 23 34 45 56 67 78
2
3
dfs(adj,1)
1
4
5
1
6
7
dfs(adj,2)
2
8
2
8
3
8
3
8
4
5
6
7
1
void dfs(adj,v)
1
{ visited[v-1]=1;
cout<<v;
2
for(p=adj[v-1].firstarc;p!=NULL;p=p->next) if(visited[p->adjvex-1]==0) dfs(adj,p->adjvex); 4 5
2
3
dfs(adj,1)
1
4
5
1
6
7
2
8
2
8
3
8
3
8
4
5
6
7
void dfs(adj,v)
1
{ visited[v-1]=1;
cout<<v;
2
for(p=adj[v-1].firstarc;p!=NULL;p=p->next) if(visited[p->adjvex-1]==0) dfs(adj,p->adjvex); 4 5
图的二种常见的遍历形式： •深度优先搜索 •广度优先搜索
1、深度优先（DFS）搜索
访问方式：从图中某顶点v出发：
1）访问顶点v； 2）从v的未被访问的邻接点出发，继续对图进行深度优先遍历， 若从某点出发所有邻接点都已访问过，退回前一个点继续上述过 程，若退回开始点，结束。

计算机中图的名词解释在计算机领域中，图（Graph）是一种常见的数据结构，用于描述对象之间的关系和相互作用。

图的概念最早由数学家欧拉提出，并且在计算机科学中得到广泛运用。

本文将从图的基本概念和操作开始，逐步介绍计算机中图的相关术语和应用。

1. 图的基本概念图由节点（Node）和边（Edge）组成。

节点表示对象或实体，边表示节点之间的连接关系。

图可以分为有向图（Directed Graph）和无向图（Undirected Graph）。

在有向图中，边具有方向性，表示从一个节点流向另一个节点；而在无向图中，边没有方向性，表示两个节点之间的相互关系。

2. 图的存储方式为了在计算机中表示和处理图，常见的存储方式有邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。

邻接矩阵是一个二维数组，其中行和列表示节点，矩阵的值表示节点之间是否有边相连。

邻接表则使用链表的形式来表示节点之间的连接关系，每个节点对应一个链表，链表中存储了与该节点相连的其他节点。

3. 图的遍历图的遍历是指沿着图中的路径，依次访问所有节点的过程。

常见的图遍历算法有深度优先搜索（Depth-First Search）和广度优先搜索（Breadth-First Search）。

深度优先搜索先选择一个起始节点，沿着路径一直深入直到无法继续，然后回溯到其他未访问的节点，继续深入；而广度优先搜索则是从起始节点开始，并逐层扩展，逐层访问。

4. 最短路径算法最短路径算法用于计算两个节点之间的最短路径，即路径上边的权值之和最小。

其中，最常用的最短路径算法是狄克斯特拉算法（Dijkstra Algorithm）。

该算法通过逐步更新节点到其他节点的距离，找到起始节点到目标节点的最短路径。

5. 拓扑排序拓扑排序（Topological Sorting）是一种对有向无环图进行排序的算法。

在有向图中，如果节点 A 的边指向节点 B，那么 B 必须在 A 之后才能出现在排序结果中。

A
B C D
第 5 页
E
7.1 图的定义与术语
3、无向图——无向图G是由两个集合V(G)和 E(G)组成的。 其中：V(G)是顶点的非空有限集。 E(G)是边的有限集合，边是顶点的 无序对，记为 (v,w) 或 (w,v)，并且 (v,w)=(w,v)。
第 6 页
7.1 图的定义与术语

例如：
G2 = <V2,E2> V2 = { v0 ,v1,v2,v3,v4 } E2 = { (v0,v1), (v0,v3), (v1,v2), (v1,v4), (v2,v3), (v2,v4) }
V5
第 15 页
7.1 图的定义与术语
非 连 通 图
V0
V1
V2
V3
V0
V1 V3
V2
强连通分量
第 16 页
7.1 图的定义与术语
7、生成树
包含无向图 G 所有顶点的极小连通子图称为G生 成树。 极小连通子图意思是：该子图是G的连通子图， 在该子图中删除任何一条边，子图不再连通。
V0 V2 V3 V4 V3 连通图G1 V1 V0 V1 连通 所有顶点 V4 无回路
第 22 页
7.2 图的存储结构 3、有向图的逆邻接表 顶点：用一维数组存储（按编号顺序） 以同一顶点为终点的弧：用线性链表存储。
vexdata V0 V1 0 1 v0 v1 v2
v3
firstarc 3 0 0 ^ ^
V2
V3
2 3
^
^
2
章 类似于有向图的邻接表，所不同的是： 以同一顶点为终点弧：用线性链表存储
Boolean visited[MAX]; // 访问标志数组

操作结果: 在图G中增添新顶点v。
DeleteVex(&G, v) //删除顶点 初始条件: 图G存在， v和G中顶点有相同特性 。 操作结果:删除G中顶点v及其相关的弧。
InsertArc(&G, v, w) //插入弧 初始条件:图G存在，v 和w是G中两个顶点。 操作结果:在G中增添弧<v,w>，若G是无向的， 则还增添对称弧<w,v>。
DestroyGraph (&G ) // 销毁 初始条件:图G存在。 操作结果:销毁图G 。
LocateVex(G, u) // 定位 初始条件:图G存在，u 和G中顶点有相同特性 。 操作结果: 若G中存在顶点u ，则返回该顶点在 图中位置 ；否则返回其它信息。
GetVex(G, v)// 求值 初始条件:图G存在，v 是G中某个顶点。 操作结果:返回v的值。
//{有向图，有向网，无向图，无向网}
typedef struct ArcCell {// 弧的定义 VRType adj;//VRType是顶点关系类型。对无权图，
//用1或0表示相邻否；对带权图，则为权值类型。 InfoType *info; // 该弧相关信息的指针 } ArcCell ,
AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM];
V2
V3
0110 0000 0001 10 0 0
//－ －图的数组(邻接矩阵)存储表示－－
#define INFINITY INT_MAX //最大值∞ #define MAX_VERTEX_NUM 20//最大顶点个数 typedef enum{DG,DN,UDG, UDN }graphkind；
表示，称为无向边；

（4）网的邻接矩阵
网的邻接矩阵可定义为：
wi,j 若<vi, vj>或(vi, vj) ∈VR A[i][j] =
∞ 反之
例如，下图列出了一个有向网和它的邻接矩阵。
V1
5
V2
5 7
3
84
4
V6
79
V3
8 9 5 6
1
6
V5
5
5
5
V4
3 1
(a) 网N
精选ppt (b) 邻接矩阵
7
（5）图的构造
01
∧
2 1∧
精选ppt
2 0∧∧
0 2∧∧
19
（3）C语言描述
#define MAX_VERTEX_NUM 20
typedef struct ArcBox {
int
tailvex, headvex;
//该弧的尾和头顶点的位置
struct ArcBox * hlink, * tlink;
//分别为弧头相同和弧尾相同的弧的链域
精选ppt
14
在无向图的邻接表中， 顶点Vi的度恰为第i个
B
链表中的结点数。
A
0A 1 4
1B 0 4 5
F
2C 3 5
3D 2 5
4E 0 1
5F
1
2 3 精选ppt
C D
E
15
有向图的邻接表
A
B
E 0A
CF
1B
可见，在有向图的 2 C 邻接表中不易找到 3 D 指向该顶点的弧 4 E
精选ppt
精选ppt
9
7.2.2邻接表表示法(Adjacency List)

继续进行 ·3
·4
搜索。
·5
·6
·7
·3 ·1
·2
·4 从结点 5 出发的搜索序列：
5、6、2、3、1、4、7 适用的数据结构：栈
图的遍历
2、广度（宽度）优先搜索:
• 树：
A
B
C
D
EFG H
I JK
树的按层次进行访问的次序： A、B、C、D、E、F、G、H、 I、J、K、L
适用的数据结构：队列
L A
1
·1
2
12
11
·2
·11
·12
3
6
7
10
·3 ·6 ·7
·10
4
5
8
9
·4 ·5 ·8
·9
图的广度优先的访问次序：
1、2、11、12、3、6、7、10、4、5、8、9
适用的数据结构：队列
图的连通性问题
2、有向图的强连通分量的求法：续 •强连通分量的求法：
1、对有向图 G 进行深度为主的搜索，按照退 出该结点的次序给结点进行编号。最先退 出的结点的编号为 1，其它结点的编号按 次序逐次增大 1。
点1
3 已在U中
16 21 35
0 0 0
lowcost 表示最小距离
4∞ 0
adjvex 表示相应结点(在V －U中的)
5∞
0
lowcost adjvex
U1
6
5 1
25 35 4
3
6
4
2
566 图G
数组：closedge[ 6 ]
00 15 2 20 35 0 46 2 54 2
lowcost adjvex

生成森林:一个有向图的生成森林由若干棵有向树组成,含有图 生成森林:一个有向图的生成森林由若干棵有向树组成, 中全部的结点,但只有足以构成若干棵不相交的有向树的弧. 中全部的结点,但只有足以构成若干棵不相交的有向树的弧. A B C F F E D E 图7.5 一个有向图及其生成森林 A B D C
(B, E), (C, D), (D, F), (B, F), (C, F) }
由顶点集和边 集构成的图称 作无向图.
B A F
C D E
15
A
21 2
9 11
弧或边带权的图
B
3
7
E
有向网或 分别称作有向网 有向网 无向网. 无向网
C
F B A E C A
设图G=(V,{VR}) 和 图 G′=(V′,{VR′}), B 且 V′V, VR′VR, 子图. 则称 G′ 为 G 的子图 子图
一般地,如果顶点 的度记为TD(vi),那么一个有 个顶点,e条 个顶点, 一般地,如果顶点vi的度记为 ,那么一个有n个顶点 条
1 边或弧的图,满足如下关系: 边或弧的图,满足如下关系:e = 2
n
∑ TD ( v
i =1
i
)
路径( ):在无向图 中从顶点v到顶点 路径(Path):在无向图 ):在无向图G=(V, {E})中从顶点 到顶点 的一个顶点序列 中从顶点 到顶点v'的一个顶点序列 (v = vi,0, vi,1, …, vi,m = v'),其中 i,j-1, vi,j)∈E,1≤j≤m.若G是有向图,则路 是有向图, ,其中(v ∈ , ≤≤ . 是有向图 径也是有向的,顶点序列满足<v 径也是有向的,顶点序列满足 i,j-1, vi,j>∈E,1≤j≤m. ∈ , ≤≤ . 路径的长度:路径上的边或弧的数目. 路径的长度:路径上的边或弧的数目. 回路或环(Cycle):第一个顶点和最后一个顶点相同的路径. ):第一个顶点和最后一个顶点相同的路径 回路或环( ):第一个顶点和最后一个顶点相同的路径. 简单路径:序列中顶点不重复出现的路径. 简单路径:序列中顶点不重复出现的路径. 简单回路或简单环:除了第一个顶点和最后一个顶点之外, 简单回路或简单环:除了第一个顶点和最后一个顶点之外,其余顶点不 重复出现的回路. 重复出现的回路. 连通:在无向图 中 如果从顶点v到顶点 有路径,则称v和 是连通的 到顶点v'有路径 是连通的. 连通:在无向图G中,如果从顶点 到顶点 有路径,则称 和v'是连通的. 连通图( ):对于图中任意两个顶点 连通图(Connected Graph):对于图中任意两个顶点 i, vj∈V,vi和vj都 ):对于图中任意两个顶点v , 是连通的图. 是连通的图. 连通分量( ):指无向图中的极大连通子图 连通分量(Connected Component):指无向图中的极大连通子图. ):指无向图中的极大连通子图.

END
图的定义和术语及存储结构 （精选）
11、战争满足了，或曾经满足过人的 好斗的 本能， 但它同 时还满 足了人 对掠夺 ，破坏 以及残 酷的纪 律和专 制力的 欲望。 ——查·埃利奥 特 12、不应把纪律仅仅看成教育的手段 。纪律 是教育 过程的 结果， 首先是 学生集 体表现 在一切 生活领 域—— 生产、 日常生 活、学 校、文 化等领 域中努 力的结 果。— —马卡 连柯(名 言网)
13、遵守纪律的风气的培养，只有领 导者本 身在这 方面以 身作则 才能收 到成效 。—— 马卡连 柯 14、劳动者的组织性、纪ቤተ መጻሕፍቲ ባይዱ性、坚毅 精神以 及同全 世界劳 动者的 团结一 致，是 取得最 后胜利 的保证 。—— 列宁 摘自名言网
15、机会是不守纪律的。——雨果
16、业余生活要有意义，不要越轨。——华盛顿 17、一个人即使已登上顶峰，也仍要自强不息。——罗素·贝克 18、最大的挑战和突破在于用人，而用人最大的突破在于信任人。——马云 19、自己活着，就是为了使别人过得更美好。——雷锋 20、要掌握书，莫被书掌握；要为生而读，莫为读而生。——布尔沃

短路径，逐个把第二组中的顶点加到第一组中去，直至S=V。
上一页 下一页 返 回
7.5 应用举例及分析
C2
例7.1拓扑排序实用程序。 对应该有向图，用邻接链 表结构存储此图。程序首 先调用建立有向图邻接链 表的算法，建立有向图的 邻接链表，在此邻接链表 结构上，实现对有向图的 拓扑排序并输出结果。
e1
//每条弧对应一个结点
//顶点的入度 //顶点的信息 //每个顶点对应一单链表
上一页 下一页 返 回
typedef struct {VEXNODE adjlist[MAXLEN]; //邻接链表 int vexnum,arcnum; //有向图的顶点数目、弧数目 int kind; //有向图的 kind = 1 }ADJGRAPH; ADJGRAPH creat_adjgraph() { EDGENODE * p; Int I,s,d;
上一页 下一页 返 回
6、 连通，强连通
若从顶点Vi到Vj(i≠j)有路径，则称Vi和Vj是连通的。
如果无向图中任意两个顶点Vi和Vj都是连通的，则称该
无向图是连通图。无向图中极大连通子图称为连通分量。 在有向图中，若任意两个顶点Vi和Vj都连通，即从Vi到 Vj和Vj到Vi都有路径，则称该有向图为强连通图。有向图中 的极大连通子图称为该有向图的强连通分量。
上一页
下一页
返 回
7 ．3
图 的 遍 历
图的遍历：从图中某顶点出发对图中每个
顶点访问一次，而且只访问一次，这一过程称
为图的遍历。
图的遍历方法有：深度优先搜索遍历和广
度优先搜索遍历。
上一页
下一页
返 回
7.3.1 深度优先搜索遍历 算法描述：从图中某个顶点V出发，首先访问

REPORTING
WENKU DESIGN
大规模图的存储与处理
大规模图的存储
随着图数据的规模不断增大，传统的关系型数据库已经无 法满足存储和查询需求。为了解决这个问题，需要采用分 布式存储系统来存储大规模图数据。
大规模图的查询处理
大规模图查询处理需要高效的数据结构和算法，以支持大 规模图数据的快速查询和遍历。
广度优先遍历
队列实现
使用一个队列来存储遍历过程中的节点，按照节点的层次顺序进行遍历，即先 访问离起始节点最近的节点，再依次访问其他节点。
层次遍历
按照层次顺序遍历图中的节点，从起始节点开始，先访问其所有未被访问过的 邻居节点，然后再依次访问这些邻居节点的未被访问过的邻居节点，以此类推。
遍历算法的应用场景
定义
图是由顶点（或节点）和边组成的数 据结构，用于表示对象及其之间的关 系。
特点
图是一种非线性数据结构，可以表示 复杂的关系和网络结构，具有灵活性 、直观性和可视化等优点。
图的组成元素
顶点（节点）
表示对象或实体，可以是任意类型的数据。
边
表示顶点之间的关系或连接，可以是有向或无向 的。
权重
表示边的强度或连接的紧密度，可以是任意实数 或数据类型。
随着深度学习技术的不断发展，图神 经网络将会有更多的应用场景和优化 空间。同时，随着图数据的规模不断 增大，如何高效地训练和部署图神经 网络也是未来的研究方向之一。
THANKS
感谢观看
REPORTING
https://
图的存储方式
REPORTING
WENKU DESIGN
邻接矩阵
定义
邻接矩阵是表示图的一种数据结构，其中每个元素表示顶点之间的连接关系。如果两个顶点 之间存在一条边，则对应的矩阵元素值为1；否则为0。

56、书不仅是生活，而且是现在、过 去和未 来文化 生活的 源泉。 ——库 法耶夫 57、生命不可能有两次，但许多人连一 次也不 善于度 过。— —吕凯 特 58、问渠哪得清如许，为有源头活水来 。—— 朱熹 59、我的努力求学没有得到别的好处， 只不过 是愈来 愈发觉 自己的准备的头脑有特别的 亲和力 。 27、自信是人格的核心。
28、目标的坚定是性格中最必要的力 量泉源 之一， 也是成 功的利 器之一 。没有 它，天 才也会 在矛盾 无定的 迷径中 ，徒劳 无功。- -查士 德斐尔 爵士。 29、困难就是机遇。--温斯顿．丘吉 尔。 30、我奋斗，所以我快乐。--格林斯 潘。
拉
60、生活的道路一旦选定，就要勇敢地 走到底 ，决不 回头。 ——左

一、图的定义一、图的定义图是一系列顶点（结点）和描述顶点之间的关系边（弧）组成。

图是数据元素的集合，这些数据元素被相互连接以形成网络。

其形式化定义为：G=（V，E）V={Vi|Vi∈某个数据元素集合}E={(Vi,Vj)|Vi,Vj∈V∧P(Vi,Vj)}其中，G表示图，V是顶点的集合，E是边或弧的集合。

在集合E 中，P(Vi,Vj)表示顶点Vi和顶点Vj之间有边或弧相连。

二、图的术语顶点集：图中具有相同特性的数据元素的集合称为顶点集。

边（弧）：边是一对顶点间的路径，通常带箭头的边称为弧。

弧头：每条箭头线的头顶点表示构成弧的有序对中的后一个。

弧尾：每条箭头线的尾顶点表示构成弧的有序对中的前一个顶点，称为弧尾或始点。

度：在无向图中的顶点的度是指连那个顶点的边的数量。

在有向图中，每个顶点有两种类的的度：出度和入度。

入度：顶点的入度是指向那个顶点的边的数量。

出度：顶点的出度是由那个顶点出发的边的数量。

权：有些图的边（或弧）附带有一些数据信息，这些数据信息称为边（或弧）的权（weigh）。

三、图的分类有向图：在一个图中，如果任意两顶点构成的偶对（Vi,Vj）是有序的，那么称该图为有向图。

这里Vi是弧尾，Vj是弧头。

这表示有一个从顶点Vi到顶点 Vj的路径。

但是从Vj到Vi是不可能的。

无向图：在一个图中，如果有任意两顶点构成的边（Vi,Vj），（Vi,Vj）和（Vj ，Vi）是相同的。

在一个无向图中，如果任意两个顶点之间都有边相连，则称该图为无向完全图。

无向完全图又称完全图。

在一个有向图，如果任意两个顶点之间都是弧相连，则称该图为有向完全图。

有很少条边或弧的图称为稀疏图，反之称为稠密图。

四、图的基本操作1.SetNode()：在图中增加一个新的顶点2.GetNode()：获取图中指定顶点3.SetEdge()：在两个顶点之间添加指定权值的边或弧4.GetEdge()：获取两个顶点之间的边5.DelEdge()：删除两个顶点之间的边或弧6.GetNumOfVertex()：获取邻接矩阵顶点数7.GetNumOfEdge()：获取邻接矩阵边或弧的数目8.GetIndex()：获取指定顶点在数组中的索引9.IsEdge()：判断两个顶点之间是否存在边或弧10.IsNode()：判断指定结点是否是图的顶点。

例7.1
245
1
3
6
G1
图G1中：V(G1)={1,2,3,4,5,6} E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>}
例7.2 1
57
32
46
G2
图G2中：V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
<v,w>表示从v到w的弧， 谓词P(v,w)定义了弧<v,w>的意义或信息} 差不多操作P：
}
差不多操作
CreatGraph(&G, V, VR) // 按定义(V, VR) 构造图 DestroyGraph(&G): // 销毁图 LocateVex(G, u); // 假设G中存在顶点u，那么返回该顶点在 图中“位 置” ；否那么返回其它信息。 GetVex(G, v); // 返回 v 的值。
PutVex(&G, v, value); // 对 v 赋值value。
差不多操作
FirstAdjVex(G, v); // 返回 v 的“第一个邻接点” 。假设该顶点
/N/在extGAd中jV没ex有(G邻, 接v, w点)，; 则返回“空”。 // 返回 v 的（相关于 w 的） “下一个邻接 点”。假设 w 是 v 的最后一个邻接点，那么返回“空”。
typedef struct { // 图的定义 VertexType vexs[MAX_VERTEX_NUM];// 顶点 信息 AdjMatrix arcs; // 弧的信息 int vexnum, arcnum; // 顶点数，弧数 GraphKind kind; // 图的种类标志 } MGraph;