数据结构 408-6-4 - 数据结构 - 计算机科学 | Flüstern = Whispering's Blog = 无需过去，无关未来，只有现在

# 最小生成树

生成树：连通图的生成树是包含图 G 中全部顶点的一个极小连通子图

最小生成树：对于一个带权连通无向图 G=(V,E)，生成树不同，每棵树的权 (即树中所有边上的权值之和) 也可能不同。设 R 为 G 的所有生成树的集合，若 T 为 R 中边的权值之和最小的生成树，则 T 称为 G 的最小生成树 (MST)

最小生成树可能有多个，但边的权值之和总是唯一最小的
最小生成树的边数 = 顶点数 - 1，砍掉一条则不连通，增加一条则会出现回路
如果一个连通图本身就是一颗树，则其最小生成树就是它本身
只有连通图才有生成树，非连通图只有生成森林

Prim 算法：

从某一个顶点构建生成树；每次将代价最小的新顶点纳入生成树，直到所有的顶点都纳入为止
时间复杂度：O (|V|*|V|)，适合用于边稠密图
实现思想：
- 从 V0 开始，总共需要 n-1 轮处理
- 每一轮处理：循环遍历所有结点，找到 lowCast 最低的，且还没有加入树的顶点
- 再次循环遍历，更新还没有加入的各个顶点的 lowCast 值（每一轮时间复杂度为 2n）

Kruskal 算法：

每次选择一条权值最小的边，使这两头连通 (原本已经连通的就不选)，直到所有结点都连通
时间复杂度：O (|E|log2|E|)，适合用于边稀疏图
实现思想：
- 初始：将各条边按权值排序
- 共执行 e 轮，每轮判断两个顶点是否属于同一集合 (并查集来判断)，需要 O (log2e)，总时间复杂度为 O (elog2e)

# 最短路问题

# BFS 求无权图的单源最短路径问题

注：无权图可以视为一种特殊的带权图，只是每条边的权值都为 1

//求顶点u到其他节点的最短路径
void BFS_MIN_Distance(Graph G,int u){
    //d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;++i){
        d[i]=INF; //初始化路径长度
        path[i]=-1; //最短路径从哪个顶点过来
    }
    d[u]=0;
    visited[u]=true;
    EnQueue(Q,u);
    while(!isEmpty(Q)){  //BFS算法主过程
        DeQueue(Q,u);    //队头元素出队
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
            if(!visited[w]){  //w为u的尚未访问的邻接顶点
                d[w]=d[u]+1;  //路径长度加1
                path[w]=u;    //最短路径应从u到w
                visited[w]=true; //设已访问标记
                EnQueue(Q,w); //顶点w入队
            }
    }
}

# Dijkstra 算法

BFS 算法求单源最短路径只适用于无权图，或所有边的权值都相同的图

带权路径长度 —— 当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

数组定义：

final：标记各顶点是否已找到最短路径
dist：最短路径长度
path：路径上的前驱

算法过程：

从 V0 开始，初始化三个数组信息
循环遍历所有节点，找到还没确定最短路径且 dist 最小的顶点 Vi，令 final [i]=true
检查所有邻接自 Vi 的顶点，若其 final 值为 false，则更新 dist 和 path 信息
循环遍历所有结点，找到还没有确定的最短路径，且 dist 最小的顶点 Vi，令 final [i]=true

结论：Dijskra 算法不适用于有负权值的带权图

时间复杂度： $O(n^2)$

# Floyd 算法

求解出图中每两个顶点之间的最短路

//准备工作，根据图的信息初始化矩阵A和path
for(int k=0;k<n;k++){  //考虑以Vk作为中转点
    for(int i=0;i<n;i++){   //枚举矩阵中每两个节点
        for(int j=0;j<n;j++){
            if(A[i][j]>A[i][k]+A[k][j]){ //以Vk为中转点的路径更短
                A[i][j]=A[i][k]+A[k][j]; //更新最短路径长度
                path[i][j]=k;            //中转点
            }
        }
    }
}

时间复杂度： $O(n^3)$ ，空间复杂度： $O(n^2)$

Floyd 算法不能解决带有负权回路的图（有负权值的边组成回路），这种图有可能没有最短路径。

Floyd 算法可以解决带有负权边的图

# 有向无环图 (DAG)

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称 DAG 图

将表达式转为有向无环图步骤：

把各个操作数不重复地排成一排
标出各个运算符的生效顺序 (先后顺序有点出入无所谓)
按顺序加入运算符，注意分层
从底向上逐层检查同层的运算符是否可以合并

# 拓扑排序

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

每个顶点出现且仅出现一次
若顶点 A 在序列中排在顶点 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径

或者：

拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后面。每个 AOV 网都有一个或多个拓扑排序序列

拓扑排序实现：

从 AOV 网中选择一个没有前驱 (入度为 0) 的顶点并输出
从网中删除顶点和所有以它为起点的有向边
重复上面两步骤，直到当前的 AOV 网为空或当前网中不存在无前驱点为止

#define MaxVertexNum 100   //图中最大顶点数
typedef struct ArcNode{   //边表节点
    int adjvex;           //该边指向的顶点的位置
    struct ArcNode *nextarc;  //指向下一条弧的指针
    //InfoType info;      //网的权值
}ArcNode;
typedef struct VNode{   //顶点表结点
    VertexType data;   //顶点信息
    ArcNode *firstarc;  //指向第一个依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;  //邻接表
    int vexnum,arcnum;   //图的顶点数和弧数
} Graph;                 //Graph是以邻接表存储的图类型
bool TopologicalSort(Graph G){
    InitStack(S);    //初始化栈，存储入度为0的顶点
    for(int i=0;i<G.vexnum;i++){
        if(indegree[i]==0)
            Push(S,i);   //将所有入度为0的节点进栈
    }
    int count=0;  //计数，记录当前已经输出的顶点数
    while(!IsEmpty(S)){  //栈不为空，存在入度为0的节点
        Pop(S,i);   //栈顶元素出栈
        print[count++]=i;  //输出栈顶点
        for(p=G.vertices[i].firstarc;p;p->nextarc){
            //将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S,v);  //入度为0，入栈
        }
    }
    if(count<G.vexnum)
        return false;   //排序失败，有向图中有环路
    else
        return true;  //拓扑排序成功
}

时间复杂度：O (|V|+|E|)

逆拓扑排序实现：

从 AOV 网中选择一个没有后继 (出度为 0) 的顶点并输出
从网中删除顶点和所有以它为终点的有向边
重复上面两步骤，直到当前的 AOV 网为空

逆拓扑排序实现（DFS 算法）：

void DFSTranverse(Graph G){
    for(i=0;i<G.vexnum;++i)
        visited[i]=false;   //访问标记数组初始化
    for(i=0;i<G.vexnum;++i) //从0号节点开始遍历
        if(!visited[i])     //对每个连通分量调用一次DFS
            DFS(G,i);       //vi未访问过，从vi开始DFS
}

void DFS(Graph G,int v){  //从顶点v出发，深度优先遍历图G
    visited[v]=true;      //设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        if(!visited[w])   //w为v的尚未访问的邻接点
            DFS(G,w);
    print(v);
}

# 关键路径

AOE 网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销 (如完成活动所需要的时间)，称之为用边表示活动的网络，简称 AOE 网

AOE 网性质：

只有在某顶点所代表的事件发生后，从该顶点出发的各种有向边所代表的活动才能开始
只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动可以并行进行的

在 AOE 网中仅有一个入度为 0 的顶点，称为开始顶点 (源点)，它表示整个工程的开始；也仅有一个出度为 0 的顶点，称为结束顶点 (汇点)，它标志整个工程的结束

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动

完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长

事件 $v_k$ 最早发生时间 ve (k)—— 决定了所有从 $v_k$ 开始的活动能够开工的最早时间

活动 $a_i$ 的最早开始时间 e (i)—— 指该活动的起点所表示的事件的最早发生时间

事件 $v_k$ 最迟发生时间 vl (k)—— 它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间

活动 $a_i$ 的最迟开始时间 l (i)—— 它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差

活动 $a_i$ 的时间余量 d (i)=l (i)-a (i)，表示在不增加完成整个工程所需总时间的情况下，活动 ai 可以拖延的时间

若一个活动的时间余量为零，则说明该活动必须要如期完成，d (i)=0 即 l (i)=e (i) 的活动是关键活动

由关键活动组成的路径就是关键路径

求关键路径步骤：

求所有事件的最早发生时间 ve
- 按拓扑排序序列，依次求各个顶点的 ve (k)
- ve (源点)=0，ve (k)=Max {ve (j)+Weight ( $v_j,v_k$ )}， $v_j$ 为 $v_k$ 的任意前驱
求所有事件的最迟发生时间 vl
- 按逆拓扑排序序列，依次求各个顶点的 vl (k)
- vl (汇点)=ve (汇点)，vl (k)=Min {vl (j)-Weight ( $v_k,v_j$ )}， $v_j$ 为 $v_k$ 的任意后继
求所有活动的最早发生时间 e
- 若边 $<v_k,v_j>$ 表示活动 $a_i$ ，则由 e (i)=ve (k)
求所有活动的最迟发生时间 e
- 若边 $<v_k,v_j>$ 表示活动 $a_i$ ，则由 l (i)=vl (j)-Weight ( $v_k,v_j$ )
求所有活动的时间余量 d，d (i)=0 的活动就是关键活动，由关键活动可得关键路径
- d(i)=l(i)-e(i)

若关键活动耗时增加，则整个工程的工期将增加

缩短关键活动的时间，可以缩短整个工程的工期

当缩短到一定程度时，关键活动可能会变成非关键活动

可能由多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工程的目的

数据结构考研408