数据结构入门（6）

  本系列文章将简要介绍数据结构课程入门知识，文章将结合我们学校（吉大）数据结构课程内容进行讲述。文中算法大部分来自朱允刚老师上课的讲解，朱老师是我遇到最认真负责的老师，很有幸能成为朱老师的学生。

注：以下内容只是对与图相关的定义的简单阐述，深入理解请学习离散数学图论。 图（Graph）是一种较线性表和树更为复杂的非线性结构。在图结构中，对结点（图中常称为顶点）的前驱和后继个数不加限制，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。

图状结构可以描述各种复杂的数据对象。

图的应用极为广泛，特别是近年来的迅速发展，已经渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。

设G是无向图，v∈V(G)，E(G)中以v为端点的边的个数，称为顶点v的度。 若G是有向图，则v的出度是以 v 为始点的边的个数，v 的入度是以 v 为终点的边的个数 ，顶点的度=入度+出度。 顶点的度数之和是边数的两倍

设G是图，若存在一个顶点序列vp ,v1 ,v2 ,…… ,vq-1 ,vq 使得 ,< v1 ,v2> , ……,< vq-1,vq>或 (vp ,v1 ),(v1 ,v2 ),……,(vq-1 ,vq )属于E(G)，则称vp到vq存在一条路径，其中vp 称为起点，vq称为终点。 路径的长度是该路径上边的个数。 如果一条路径上除了起点和终点可以相同外，再不能有相同的顶点，则称此路径为简单路径。 如果一条简单路径的起点和终点相同，且路径长度大于等于2，则称之为简单回路。

设G，H是图，如果 V ( H ) ⊆ V ( G ) V(H)\subseteq V(G) V(H)⊆V(G)， E ( H ) ⊆ E ( G ) E(H)\subseteq E(G) E(H)⊆E(G)，则称H是G的子图，G是H的母图。如果H是G的子图，并且V(H) = V(G)，则称H为G的支撑子图。

设G是图，若存在一条从顶点vi到顶点vj的路径，则称vi与vj可及（连通）。 若G为无向图，且V(G)中任意两顶点都可及，则称G为连通图。 若G为有向图，且对于V(G)中任意两个不同的顶点vi和vj， vi与vj可及， vj与vi也可及，则称G为强连通图 设图G = (V，E)是无向图，若G的子图GK是一个连通图，则称GK 为G的连通子图。 设图G = (V，E)是有向图，若G的子图GK是一个强连通图，则称GK 为G的强连通子图。 对于无向图G的一个连通子图GK，如果不存在G的另一个连通子图 G’，使得V(GK)⊂V(G’)，则称GK为G的连通分量。（GK再加一个顶点就不连通了） 对于有向图G的一个强连通子图GK，如果不存在G的另一个强连通子图G’，使得V(GK)⊂V(G’)，则称GK为G的强连通分量。

设G = (V, E)是图，若对图中的任意一条边l，都有实数w(l)与其对应，则称G为权图，记为G = (V, E, w)。记w(u, v)表示w((u, v))或w()，规定： ∀u∈V, 有w((u, u))=0或w()=0 ∀u, v∈V, 若(u, v)∉E(G)或∉E(G)，则w((u, v))=＋∞或w()= ＋∞

若σ=（v0,v1,v2,……，vk） 是权图G中的一条路径，则 ∣ σ ∣ = ∑ i = 1 k w ( v i − 1 , v i ) |\sigma|=\sum_{i=1}^kw(v_{i-1},v_i) ∣σ∣=∑i=1k​w(vi−1​,vi​) 称为加权路径 σ 的长度或权重。 权通常用来表示从一个顶点到另一个顶点的距离或费用。

用顺序方式或链接方式存储图的顶点表v0,v1,…vn−1，图的边用 n*n 阶矩阵 A=(aij) 表示，A 的定义如下: ⑴若非权图，则:

⑵若权图，则:

称矩阵 A 为图的邻接矩阵

特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图所需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称；有n个顶点的有向图所需存储空间为n²

顺序存储顶点表。 对图的每个顶点建立一个单链表(n个顶点建立n个单链表)，第 i 个单链表中的结点包含顶点vi的所有邻接顶点（边链表）。 由顺序存储的顶点表和链接存储的边链表构成的图存储结构被称为邻接表。 边链表

与顶点 v 邻接的所有顶点以某种次序组成的单链表称为顶点 v 的边链表。

边链表的每一个结点叫做边结点，对于非权图和权图边结点结构分别为:

其中, VerAdj存放 v 的某个邻接顶点在顶点表中的下标； link存放指向 v 的边链表中结点 VerAdj 的下一个结点的指针。 cost 存放边(v, VerAdj)或的权值

关于图的遍历可视化可以看看这个网站https://visualgo.net/zh/dfsbfs

深度优先遍历又被称为深度优先搜索 DFS ( Depth First Search ) 基本思想:

递归算法

迭代算法

将所有顶点的vis[ ]值置为0, 初始顶点v0入栈；

检测栈是否为空，若栈为空，则算法结束；

从栈顶弹出一个顶点v，如果v未被访问过则： 访问v，并将vis[v]值更新为1； 将v的未被访问的邻接顶点入栈

执行步骤 2。

图深度优先遍历的次序不唯一

基本思想：

图的广度优先遍历类似于树的层次遍历，是一种分层的搜索过程，每前进一层可能访问一批顶点，不像深度优先搜索那样有时需要回溯。因此，广度优先搜索不是一个递归过程，也不需要递归算法。 为了实现逐层访问，算法中使用了一个队列，记忆还未被处理的节点，用以确定正确的访问次序。 与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组 vis[ ]，给被访问过的顶点加标记。

求无向图的连通分量数 思想：每遍历一个连通分量，计数器加1

判断图中是否有环（有向图） 有向图：在深度优先遍历过程中，一个顶点会经历3种不同的状态：

AOV网:在有向图中，顶点表示活动（或任务），有向边表示活动（或任务）间的先后关系，称这样的有向图为AOV网(Activity On Vertex Network)。

拓扑序列： 就是把AOV网中的所有顶点排成一个线性序列，若AOV网中存在有向边 Vi → Vj ，则在该序列中，Vi必位于Vj之前。 拓扑排序： 构造AOV网的拓扑序列的过程被称为拓扑排序。

注：如果通过拓扑排序能将AOV网的所有顶点都排入一个拓扑序列中，则该AOV网络中必定不会出现有向环；相反，如果不能把所有顶点都排入一个拓扑序列，则说明AOV网络中存在有向环，此AOV网络所代表的任务是不可行的。

注意：对于任何无回路的AOV网，其顶点均可排成拓扑序列，其拓扑序列未必唯一。

AOV网(Activity On Vertex):顶点表示活动或任务(Activity)，有向边表示活动（或任务）间的先后关系。 AOE网(Activity On Edges):有向边表示活动或任务(Activity) ，用边上的权值表示活动的持续时间，顶点称为事件(Event)：表示其入边的任务已完成，出边的任务可开始的状态。

事件 vj的最早发生时间 ve(j) v e ( j ) = { 0 j=0 m a x i { v e ( i ) + w ( < i , j > ∣ < i , j > ∈ E ( G ) ) } j=2, … ,n ve(j)=\begin{cases} 0& \text{j=0}\\{max_i\{ve(i)+w(|∈E(G))\}}& \text{j=2,…,n} \end{cases} ve(j)={0maxi​{ve(i)+w(∣∈E(G))}​j=0j=2,…,n​

事件 vj的最迟发生时间vl(j) v l ( j ) = { v e ( n ) j=n m i n k { v l ( k ) − w ( < j , k > ∣ < j , k > ∈ E ( G ) ) } j=n-1, … ,1 vl(j)=\begin{cases} {ve(n)}& \text{j=n}\\{min_k\{vl(k)-w(|∈E(G))\}}& \text{j=n-1,…,1} \end{cases} vl(j)={ve(n)mink​{vl(k)−w(∣∈E(G))}​j=nj=n-1,…,1​

活动 ai 的最早开始时间 e(i) 设活动 ai在有向边 < vj, vk >上，e(i)=ve(j)

活动 ai的最迟开始时间l(i) 不会引起时间延误的前提下，活动ai允许的最迟开始时间。设活动ai在有向边上, 则 l(i) = vl(k)-weight()

关键路径：从源点到汇点的最长路径。 关键活动：关键路径上的活动，活动的最早开始时间等于活动的最迟开始时间，即l(i)＝e(i) . 求关键活动的步骤

注：如果图中顶点未按拓扑序编号 方案1：先执行拓扑排序，将拓扑序存入数组Topo，即Topo[i]为拓扑序中第i个顶点的编号。 方案2：执行拓扑排序过程中，弹栈选出入度为0的顶 点，更新该顶点的邻接顶点的入度时(入度减1)，同时更新其ve值。从而无需调用VertexEarliestTime函数.

注：如果图中顶点未按拓扑序编号，解决方法同上