图(未完)

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为: G(V, E) ,其中 G 表示一个图,V 是图 G 中顶点的集合,E 是图 G 中边的集合。

通常,在线性表中将数据元素称为元素,树中将数据元素称为结点,而图中,称为顶点(Vertex)

线性表和树中可以没有数据元素,称为空表和空树,但图中强调了顶点集合是非空的。

图中任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边表示,边集可以是空的。

相关定义

无向边:若顶点 $v_i$ 到 $v_j$ 之间的边没有方向,则称这条边为无向边(Edge),用无序偶对 ($v_i, v_j$) 或 ($v_j, v_i$) 表示。

若图中任意两个顶点之间的边都是无向边,则称该图为无向图(Undirected graphs)

有向边:若顶点 $v_i$ 到 $v_j$ 之间的边有方向,则称这条边为有向边,也称为弧(Arc),用有序偶对 <$v_i, v_j$> 来表示,其中 $v_i$ 称为弧尾(Tail),$v_j$ 称为弧头(Head)。

若图中任意两个顶点之间的边都是有向边,则称该图为有向图(Directed graphs)

在图中,若不存在顶点到其自身的边,且同一条边不重复出现,责成这样的图为简单图

在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含 n 个顶点的无向完全图有 n * (n - 1) / 2 条边。

在有向图中,如果任意两个顶点之间都存在方向相反的两条弧,则称该图为有向完全图。含 n 个顶点的有向完全图有 n * (n - 1) 条边。

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

与图的边或弧相关的数叫做权(Weight),带权的图称为网(Network)

假设有两个图 $G_1$ = ($V_1$, {$E_1$}) 和 $G_2$ = ($V_2$, {$E_2$}) ,如果 $V_2 \subseteq V_1$ 且 $E_2 \subseteq E_1$ ,则称 $G_2$ 为 $G_1$ 的子图(Subgraph)

对于无向图 G = (V, {E}) ,如果边 ($v_1$, $v_2$) $\in$ E ,则称 顶点 $v_1$ 和 $v_2$ 互为邻接点(Adjacent),即 $v_1$ 和 $v_2$ 相连。边 ($v_1$, $v_2$) 依附(incident)于顶点 $v_1$ 和 $v_2$ ,或 ($v_1$, $v_2$) 与顶点 $v_1$ 和 $v_2$ 相关联。顶点 v 的度(Degree)是和 v 相关联的边的数目,记为 TD(v)。

对于有向图 G = (V, {E}) ,如果弧 <$v_1$, $v_2$> $\in$ E ,则称顶点 $v_1$ 邻接到 $v_2$ ,顶点 $v_2$ 邻接自 $v_1$ 。弧 <$v_1$, $v_2$> 和顶点 $v_1$ 、 $v_2$ 相关联。以顶点 v 为头的弧的数目称为 v 的入度(InDegree),记为 ID(v) ;以 v 为尾的弧的数目称为 v 的出度(OutDegree),记为 OD(v) ;顶点 v 的度为 TD(v) = ID(v) + OD(v) 。

路径的长度是路径上的边或弧的数目。

第一个顶点和最后一个顶点相同的路径称为回路环(Cycle)。序列中顶点不重复出现的路径称为简单路径。除第一个和最后一个顶点,其余顶点不重复出现的回路,称为简单回路简单环

在无向图 G 中,如果从顶点 $v_1$ 到 $v_2$ 有路径,则称 $v_1$ 和 $v_2$ 是连通的。如果图中任意两个顶点都是连通的,则称该图为连通图(Connected Graph)

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

在有向图 G 中,如果对于每一对 $v_i 、 v_j \in V$ 、$v_i \ne v_j$ ,从 $v_i$ 到 $v_j$ 和 从 $v_j$ 到 $v_i$ 都存在路径,则称 G 是强连通图

有向图中的极大强连通子图称作有向图的强连通分量

连通图的生成树是一个极小的连通子图,含有图中全部的 n 的顶点,但只有足以构成一棵树的 n - 1 条边。

如果一个有向图洽有一个顶点入度为 0 ,其余顶点入度均为 1 ,则是一棵有向树。一个有向图的生成森林由若干棵有向树组成,含图中全部顶点,但只有足以构成若干棵不相交的有向树的弧。

图的抽象数据类型

ADT : 图(Graph)

Data :顶点的有穷非空集合和边的集合。

Operation :

  • create(按顶点集合边集构造图)
  • locateVertex(获取顶点位置)
  • getVertex(获取顶点的值)
  • putVertex(对顶点赋值)
  • getFirstAdjVertex(获取顶点的第一个邻接点)
  • getNextAdjVertex(获取顶点的下一个邻接点)
  • insertVertex(插入新顶点)
  • deleteVertex(删除顶点及相关的边或弧)
  • insertArc(添加弧)
  • deleteArc(删除弧)
  • dfsTraversal(深度优先遍历)
  • hfsTraversal(广度优先遍历)

endADT

图的存储结构

图的结构比较复杂,任意两个顶点之间都可能存在联系,所以无法以数据元素在内存中的物理位置来表示元素间的关系。而多重链表按最大度数顶点设计指针域,不仅存在空间浪费,结构不同造成的操作也很不方便。

邻接矩阵

图的邻接矩阵(Adjancency Matrix)存储方式是用两个数组表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

邻接矩阵中用 1 表示存在边或弧,0 表示不存在边或弧。如图为网图,可以用权值大小作为邻接矩阵中的值,不存在的边或弧用无穷大表示(权值可能为 0)。

邻接表

对于边数相对顶点较少的图,邻接矩阵会存在大量的空间浪费。

数组与链表相结合的存储方法称为邻接表(Adjacency List) :顶点用一个一维数组存储,每个数据元素需额外存储指向第一个邻接点的指针,data|firstedge ;每个顶点的所有邻接点构成一个链表,adjvex|next ,adjvex 存储邻接点在数组中的下标,next 指向下一个邻接点。

若是有向图,邻接表结构类似,以顶点为弧尾存储边表。也可以建立有向图的逆邻接表,以顶点的弧头建立边表。

对于网图,可以在边表结点中增加 weight 的数据域。

十字链表

对于有限图,邻接表是有缺陷的,入度和出度只能关注其一。而十字链表就是邻接表和逆邻接表的结合。

顶点表由数据域、入边表第一个结点指针和出边表第一个结点指针组成,如 data|firstin|firstout

边表由弧起点在顶点表中下标、弧终点在顶点中下标、入边表指针域和出边表指针域组成,网可以增加权值域,如 tailvex|headvex|headlink|taillink

邻接多重表

无向图的应用中,如果关注的是顶点,邻接表是不错的选择,但如果关注的是变,如删除一条边等操作,就需要对两个边表结点进行操作。

对边表结点进行改造,改为由边的两个顶点在顶点表中的下标及已付两个顶点的下一条边组成,这就是邻接多重表,如 ivex|ilink|jvex|jlink

边集数组

边集数组由两个一维数组组成。一个存储顶点信息;另一个存储边的信息,边数组中的数据元素由起点下标、终点下标和权值组成,如 begin|end|weight

图的遍历

从图中某一顶点出发,访问图中其余顶点,且使每个顶点仅被访问一次,这一过程叫图的遍历(Traversing Graph)。

todo

打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2016-2020 姜越

谢谢老板

支付宝
微信