导图社区 图
这是一篇关于数据结构-图的思维导图,主要内容有图的定义、图的遍历、图的应用、图的存储、基本术语。
编辑于2022-10-23 18:07:41 重庆图
图的定义
图的定义
图是由顶点集合V和边集E组成的集合,记作G=(V,E)。
G中的顶点是有限非空集合。 线性表可以为非空表, 树也可以是空树, 但图不可以是空图. 即图中不能一个顶点也没有。
图与它们的不同表现在结点之间的关系上,在图结构中,顶点之间的关系可以是多对多,即某一顶点与其他顶点间的关系是任意的,既可以有关也可以无关。
抽象数据类型定义
FirstAdjVex(G, V)
图G存在,v是G中某个顶点,返回v的第一个邻接顶点。若顶点在G中没有邻接顶点,则返回“空”。
NextAdjVex(G, V, w)
图G存在,v是G中某个顶点,w是V的邻接顶点,返回v的(相对于w的)下一个邻接顶点。若w是V的最后一个邻接点,则返回“空”。
InsertVex(*G, v)
图G存在,v和图中顶点有相同特征,在图G中增添新顶点v。
DeleteVex(*G, v)
图G存在,v是G中某个顶点,删除G中顶点v及其相应的关系。
InsertArc(*G, v, w)
图G存在,v和w是G中的两个顶点,在G中增添弧<v,w>,若G是无向的,则还增添对称弧<w, v>。
DeleteArc(*G, v, w)
图G存在,v和w是G中的两个顶点,在G中删除弧<v, w>,若G是无向的,则还删除对称弧<w, v>。
DFSTraverse(G, Visit())
图G存在,Visit是顶点的应用函数,对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit(),一次且仅一次。一旦Visit()失败,则操作失败。
BFSTraverse(G, Visit())
图G存在,Visit()是顶点的应用函数,对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit(),一次且仅一次。一旦Visit()失败,则操作失败。
图的遍历
深度优先遍历DFS
首先访问图中某一起始顶点v,然后由v出发,访问与v邻接且未被访问的任一顶点w 1 ,再访问与w 1 邻接且未被访问的任一顶点…重复上述过程。当不能再继续向下访问时,依次退回到最近被访问的顶点,若它还有邻接顶点未被访问过,则从该点开始继续上述搜索过程,直至图中所有顶点均被访问过为止。
广度优先遍历BFS
广度优先搜索是一种分层的查找过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况,因此它不是一个递归的算法。为了实现逐层的访问,算法必须借助一个辅助队列,以记忆正在访问的顶点的下一层顶点。
图的应用
有向无环图的应用
拓补排序
关键路径
最短路径
图的存储
邻接矩阵表示法
图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
邻接表
所谓邻接表,是指对图G 中的每个顶点v i 建立一个单链表,第i 个单链表中的结点表示依附于顶点v i 的边(对于有 向图则是以顶点v i 为尾的弧),这个单链表就称为顶点v i 的边表(对于有向图则称为出边表)。边表的头指针和顶点 的数据信息采用顺序存储(称为顶点表),所以在邻接表中存在两种结点:顶点表结点和边表结点,
邻接多重法
邻接多重表是无向图的链式存储结构。
十字链表
十字链表是为了便于求得图中顶点的度(出度和入度)而提出来的。它是综合邻接表和逆邻接表形式的一种链式存储结构。
基本术语
无向图
若E是无向边(简称边)的有限集合时,则图G为无向图。边是顶点的无序对,记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v,或者说边(v, w)和顶点v, w相关联。
有向图
若E是有向边(也称弧)的有限集合时,则图G为有向图。弧是顶点的有序对,记为<v, w>,其中v,w是顶点,v称为弧尾,w称为弧头,<v,w>称为从顶点v到顶点w的弧,也称v邻接到w,或w邻接自v。
顶点的位置
从图的逻辑结构定义来看,图中的顶点是非线性序列,不能像线性序列排列有唯一的序列。在图中可以将任一个顶点看成是图的第一个顶点,同理,对于任一顶点而言,它的邻接点之间也不一定存在顺序关系。
邻接点
对于无向图G=(V, {E}),如果边(v1, v2)∈E,则称顶点v1与v2互为邻接点,即v1与v2相邻接。
完全图
一个具有n个结点的无向图,其边数小于等于 ,如果边数恰好等于 ,n个顶点的无向图称为完全图。
子图
图G=(V, E),G'=(V', E')中,V' V,E' E,并且E'中的边所关联的结点都在V'中,则称图G'是图G的子图。
路径与回路
在图G=(V, E)中,如果有结点序列Vp, Vi1, Vi2, ..., Vin, Vq,使得{(Vp, Vi1), (Vi1, Vi2), ..., (Vin, Vg)}∈E(若对有向图,则存在一系列弧),则称从结点Vp到结点Vq存在一条路径,路径长度就为这条路径上的边数。如果一条路径上的结点除Vp和Vq可以相同外,其他结点都不相同,则称此路径为一简单路径。当Vp=Vq时,简单路径Vp, Vi1, Vi2, ..., Vin, Vp称为回路(也称环)。
连通图和连通分量
对无向图G=(V, E)而言,如果从V1到V2有一条路径,称V1和V2是连通的,若图G中任意两个结点都是连通的,则称无向图G是连通图。无向图中的极大连通子图称为该无向图的连通分量。
权与网
在实际应用中,有时图的边或弧往往与具有一定意义的数值有关,与边(弧)相关的数称为权。将这种带权的图称为网。网有无向网、有向网。
生成树
生成树是无向连通图的一个极小连通子图,它含有图中的全部顶点和使任意顶点都连通的最少的边,
度
顶点V的度(degree)是与V相关联的边(弧)的数目,记作TD(V)。