数据结构第七章

发布时间:2024年01月03日

图(Graph)G由两个集合V和E组成,记为G=(V, E),其中V是顶点的有穷非空集合,E是V中顶点偶对的有穷集合,这些顶点偶对称为边。V(G)和E(G)通常分别表示图G的顶点集合和边集合,E(G)可以为空集。若EG)为空,则图G只有顶点而没有边。

子图:假设有两个图G=(V,E)和G1=(V1,E1);如果V1V,E1E,则称G1为G的子图。

完全图:任意两个顶点都有一条边相连。(指的是无向图)

无向完全图和有向完全图:对于无向图,若具有n(n-1)/2条边,则称为无向完全图;对于有向图,若具有n(n-1)条弧,则称为有向完全图。

稀疏图和稠密图:有很少条边或弧(如e<nlogn)的图称为稀疏图,反之称为稠密图

权和网:在实际应用中,每条边可以标上具有某种含义的数值,该数值称为该边上的权,这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。

邻接点:对于无向图G,如果图的边(v, v1)E,则称顶点v和v1互为邻接点,即v和v1相邻接。

关联(依附):边/弧与顶点之间的关系;边(v, v')依附于顶点v和v1,或者说边(v, v1)与顶点v和v1相关联。

顶点的度:与该顶点相关联的边的数目,记为TD(v);在有向图中,顶点的度等于该顶点的入度与出度之和,顶点v的入度是以v为终点的有向边的条数,记作ID(v),顶点的出度是以v为始点的有向边的条数,记作OD(v)。

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

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

回路(环):第一个顶点和最后一个顶点相同的路径

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

简单回路(简单环):除路径起点和终点相同外,其余顶点均不相同的路径。

连通:两个顶点之间有路径,则称这两个顶点是连通的。

连通图:对于图中任意两个顶点都是连通的,则称该图是连通图

强连通图:在有向图中对于任意两个顶点是连通的,则称该图是强连通图。

连通分量:指的是无向图中的极大连通子图(极大连通子图意思为该子图是G的连通子图,将G的任何不在该子图中的顶点加入,子图不再连通)

强连通分量:有向图的极大强连通子图

极小连通子图:该子图是G的连通子图,在该子图中删除任何一条边子图不再连通

连通图的生成树:包含无向图所有顶点的极小连通子图

有向树:有一个顶点的入度为0,其余顶点的入度均为1的有向图称为有向树

生成森林:对于非连通图,由各个连通分量的生成树的集合


图的基本概念:

1、有向图

若E是有向边(也称弧)的有限集合时,则图G为有向图。弧是顶点的有序对,记为<v, w>,其中v,w是顶点,v称为弧尾,w称为弧头,<v,w>称为从顶点v到顶点w的弧,也称v邻接到w,或w邻接自v。

图(a)所示的有向图G可表示为:

2、无向图

若E是无向边(简称边)的有限集合时,则图G为无向图。边是顶点的无序对,记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v,或者说边(v, w)和顶点v, w相关联。

图(b)所示的无向图G2可表示为:

无向图是对称的

3、完全图(也称简单完全图)

对于无向图,∣E∣的取值范围是0 到n ( n ? 1 ) / 2 ,有n ( n ? 1 ) / 2 条边的无向图称为完全图,在完全图中任意两个顶点之间都存在边。对于有向图,∣E∣的取值范围是0 到n ( n ? 1 ) ,有n ( n ? 1 ) 条弧的有向图称为有向完全图,在有向完全图中任意两个顶点之间都存在方向相反的两条弧。

4、稠密图、稀疏图

边数很少的图称为稀疏图,反之称为稠密图。稀疏和稠密本身是模糊的概念,稀疏图和稠密图常常是相对而言的。一般当图G满足∣ E ∣ < ∣ V ∣ l o g ∣ V时,可以将G 视为稀疏图。

5、子图

设有两个图G = ( V , E ) 和G ′ = ( V ′ , E ′ ) ,若V '是V 的子集,且E ′?是E 的子集,则称G ′ G的子图。

6、出度、入度

出度:以尾为弧

入度:以头为弧

对于无向图,顶点v的度是指依附于该顶点的边的条数,记为T D ( v )。在具有n 个顶点、e 条边的无向图中,e=\frac{1}{2}n\sumi=1 TDv_{i}

7、回路或环

第一个顶点和最后一个顶点相同

8、连通图

图中任意两顶点连通,则这个图为连通图(它是无向图)

9、非连通图

如果一个图有n个顶点和小于n-1条边,就是非连通图

10、生成树

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n ,则它的生成树含有n ? 1 条边(无向图)

11、生成森林

一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一颗有向树。生成森林由多个有向树组成。


图的存储结构:

数组表示法:

用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)

其中图用0或1来表示,网用权或者∞来表示




网的邻接矩阵:

定义:? ? ? ? ? ? ? ? ? ? ? ? ? ?

A[i][j]=W_{i,j}? 若<v_{i},v_{j}>或(v_{i},v_{j}

? ? ? ? ? ? ? ? ?∞? ?反之

图的邻接表特点:有e条边就会有2e个1对称,即:w_{ij}=w_{ji}

邻接表:

邻接表是一种常用的图的数据结构,用于表示图中顶点之间的关系。它通过使用链表来存储每个顶点的邻接点。

在邻接表中,图的顶点被表示为一个数组,数组的每个元素都是一个链表。链表中的每个节点表示一个邻接点,节点中存储了与该顶点相邻的顶点的信息。

连接点域:指示与定点邻接的点v_{i}在图中位置(下标)

链域:下一条边或弧的结点

数据域:数据域存储和边或弧相关的信息,如权值

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?头结点

data数据firstarc(指针)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?表结点
?

adjvex? ??? ? ? ? ? nextarc? ? ? ? info

若无向图中有n个顶点,e条边,则它的邻接表需n个头结点和2e个表结点

若有向图中有n个顶点,e条边,则它的邻接表需n个头结点和e个表结点

图的遍历(相当于树):

深度优先搜索类似于树的先序遍历(广度=层次)。如其名称中所暗含的意思一样,这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点v,然后由v出发,访问与v邻接且未被访问的任一顶点w_{i}再访问与w_{i}邻接且未被访问的任一顶点…重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直至图中所有顶点均被访问过为止。

图的连通性:

最小生成树:

一颗生成树就的代价就是树上各代价之和。对于一个带权连通无向图G = ( V , E ) ,生成树不同,其中边的权值之和最小的那棵生成树(构造连通网的最小代价生成树),称为G的最小生成树。

克鲁斯卡尔算法:

构造最小生成树的过程如下图所示。初始时为只有n个顶点而无边的非连通图T = V ,每个顶点自成一个连通分量,然后按照边的权值由小到大的顺序,不断选取当前未被选取过且权值最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入T ,否则舍弃此边而选择下一条权值最小的边。以此类推,直至T 中所有顶点都在一个连通分量上。

我们将下面左图的邻接矩阵通过程序转化为右图的边集数组,并且对它们按权值从小到大排序

拓扑排序

对一个AOV网进行拓扑排序的算法有很多,下面介绍比较常用的一种方法的步骤:

①从AOV网中选择一个没有前驱的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。如果输出顶点数少了,哪怕是少了一个,也说明这个网存在环(回路),不是AOV网。

文章来源:https://blog.csdn.net/yst12138/article/details/135305667
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。