Created Date: 2020-01-31 14:21:43
Last Upgraded Date: 2020-02-07 14:51:27


树和森林

树和森林的实现

树的存储结构

  • 双亲表示法
    Data域 存储结点的数据信息
    Parent域 存储结点的双亲在数组中的序号。
    实现求双亲操作很方便，但对于求某节点的孩子节点的操作需要查询整个数组，实现求兄弟的操作也比较困难。

  • 孩子表示法

    1. 多重链表
      链表中的每个结点包括一个数据域和多个指针域。数据域存储树中结点的自身信息，每个指针指向该结点的一个孩子结点。
    2. 数组+单链表
      一维数组顺序存储树中各节点的信息，并将各结点的孩子信息组成一个单链表。

  • 双亲 - 孩子表示法
    将各结点的孩子结点组成一个单链表，同时用一维数组顺序存储树中的各节点，数组元素包括结点的自身信息、双亲结点在数组中的序号以及该结点的孩子结点链表的头指针。

  • 孩子 - 兄弟表示法
    firstchild data nextsibling
    二重链表表示法
    查找某结点的孩子结点比较方便，如果在每一个结点中增加一个指向双亲的指针，就可以方便地找到各结点的祖先。

树、森林和二叉树的转换

  1. 树转化为二叉树
    把树当作有序树看待：约定树中每一个结点的孩子结点按从左到右的次序顺序编号。
    连线：树中所有相邻兄弟结点之间加一条线。
    删线：对树中的每一个结点，只保留它与第一个孩子结点之间的连线，删去它与其他孩子结点之间的连线。
    美化：以树的根结点为轴心，将这棵树顺时针转动45度使其层次分明。
    树作这样的转化所构成的二叉树是唯一的。
    树转化成的二叉树，其根结点无右子树。

  2. 森林转化为二叉树
    依次将森林中每棵树转化成相应的二叉树。
    从第二棵二叉树开始，依次把当前的二叉树作为前一棵二叉树根结点的右子树，此时所得到的二叉树就是由森林转化得到的二叉树。
    森林转化成的二叉树，其根结点有右子树。

  3. 二叉树转化为森林
    连线：若结点p是其双亲结点F的 左孩子，则把从结点p延沿右分支所找到的所有结点和结点F用线连起来。
    删线：删除二叉树中所有结点和其右孩子结点之间的连线。
    美化：整理，使结构层次分明。

树的遍历

指按照某种顺序访问树中的每个结点，并使每个结点被访问一次且只被访问一次。

  1. 树的先根遍历
    若树为空，遍历结束。否则，
    访问根结点；
    按照从左到右的顺序先根遍历根结点的每一棵子树。
    与二叉树先序遍历结果序列相同。

  2. 树的后根遍历
    若树为空，遍历结束。否则，
    按照从左到右的顺序后根遍历根结点的每一棵子树；
    访问根结点。
    与二叉树中序遍历结果序列相同。

  3. 树的层次遍历
    又称为树的广度遍历。从树的第一层（根结点）开始，自上至下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
    借助队列，结构按下述步骤层序遍历树：
    1）初始化队列，并将根结点入队。
    2）当队列非空时，取出队头结点p，转步骤3）；如果队列为空，则结束遍历。
    3）访问取出的结点p；如果结点p有孩子，则依次将它们入队列。
    4）重复步骤2）、3），直到队列为空。

森林的遍历

  1. 森林的先根遍历
    若森林为空，返回；否则，
    访问森林中第一棵树的根结点；
    先根遍历第一棵树的根结点的子树森林；
    先根遍历除第一棵外其他树组成的森林。
    与二叉树先序遍历结果序列相同。

  2. 森林的中根遍历
    若森林为空，返回；否则，
    中根遍历第一棵树的根结点的子树森林；
    访问森林中第一棵树的根结点；
    中根遍历除第一棵外其他树组成的森林。
    与二叉树中序遍历结果序列相同。

  3. 森林的后根遍历
    若森林为空，返回；否则，
    后根遍历第一棵树的根结点的子树森林；
    后根遍历除第一棵外其他树组成的森林；
    访问森林中第一棵树的根结点。
    与二叉树后序遍历结果序列相同。

等价类及其表示

等价关系与等价类

先把每一个对象看作是一个单元素集合，然后依次将一个等价对中两个元素所在的集合合并。

并查集

指能够完成查找、合并功能的集合。
支持以下三种操作：

  1. Ufsets(n)：构造函数，将并查集中n个元素初始化为n个只有一个单元素的子集合。
  2. Union(S1,S2)：把集合S2并入集合S1中。要求S1与S2互不相交，否则没有结果。
  3. Find(d)：查找单元素d所在的集合，并返回该集合的名字。

等价类问题的解法
对于并查集来说，每个子集（等价类）用一棵树表示，子集合中每个元素用树中的一个结点表示。用树的根结点来代表相应的等价类集合。
等价类树用双亲表示法表示（当然根据需要可以建立集合名字表示该集合的树的根结点之间的对应关系）；此外，树的根结点的双亲域的值设为-k（parent=-k），其中k为该树中的结点数（即所代表等价类中的元素数目）。
对于任意给定的集合元素D，只要通过双亲指针向上一直走到树的根结点，就可以得到元素D所在的等价类（用根结点代表相应的等价类）。对于两个集合的并，只要将其中一个集合的根结点设置为另一个集合的根结点的孩子即可。

性能改进——避免产生退化的树
Union(i,j)的加权规则WeightedUnion()：合并两个集合时，先判断两集合中元素的个数，如果以i为根的树中的结点个数少于以j为根的树中的结点个数，则让j成为i的双亲；否则，让i成为j的双亲。
执行一次WeightedUnion()比执行一次Union()时间要多，但仍在常量界限O(1)范围内。查找操作Find()保持不变，其查找时间的上界不超过树的高度加1。

优化查找的折叠规则：设j是以i为根的树中的一个结点，则对于从j到根i的路径上的每一个结点k，如果k的双亲不等于i，则把i设置为k的双亲。
使用折叠规则完成一次查找，所需时间比Find()多，但是能改善树的性能，减少以后查找操作所需的时间。



图

图的基本概念

图的定义

无向图 undirected graph
有向图 directed graph
以下讨论限制于：图中不能有从顶点到自身的环（即自身环）；两个顶点v和w之间相关联的边不能多于一条。


图的术语

  1. 完全图 complete graph
  2. 权 weight
  3. 带权图=网络 network
  4. 邻接点 adjacent vertex
  5. 子图 subgraph
  6. 顶点的度 degree
  7. 路径 path
  8. 路径长度 path length
  9. 简单路径与回路 cycle
  10. 连通图与连通分量 connected graph and connected component
  11. 强连通图与强连通分量 strongly connected digraph
  12. 生成树 spanning tree

图的基本操作

  1. InsertVertex(d)
  2. InsertEdge(v1,v2)
  3. DeleteVertex(d)
  4. DeleteEdge(v1,v2)
  5. GetWeight(v1,v2)
  6. GetFirstNeighbor(int v)
  7. GetNextNeighbor(int v1,int v2)
  8. Travers()
  9. IsEmpty()

图的存储结构

邻接矩阵

顶点信息 —— 顶点表
顶点关系 —— 邻接矩阵

N个定点的图其邻接矩阵是一个二维数组arcs[N][N]，定义如下。
[image:705B5107-1A6B-4C3A-AF6A-BE39846E0496-16898-0000936F10705A3B/D67FBC64-A83D-4414-B986-F6E0D1787DE3.png]
无向图的邻接矩阵一定是对称的，将第i行的元素值或第i列的元素值累加起来就得到顶点i的度。
有向图的邻接矩阵不一定对称，将第j列的所有元素值累加起来就得到顶点Vj的入度ID(Vj)；将第i行的所有元素值累加起来就得到顶点Vi的出度OD(Vi)。
对于网络（或带权图）邻接矩阵定义如下。
[image:C8816614-D7FC-4C3D-AB38-07F1F7D967D9-16898-00009392C7625CB8/56365ACE-F02E-4A11-98CA-FFCADDEF32AF.png]
对于带权有向图，第i行中所有非零且不等于∞的元素数目就是顶点i的出度；第j列中所有非零且不等于∞的元素数目就是顶点j的入度。


无向图邻接矩阵类模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
template <class ElemType>
class AdjMatrixUndirGraph 
{
protected:
// 邻接矩阵的数据成员:
    int vexNum, vexMaxNum, arcNum;          // 顶点数目、允许的顶点最大数目和边数
    int **arcs;                             // 存放边信息邻接矩阵
    ElemType *vertexes;                     // 存放顶点信息的数组 
    mutable Status *tag;                    // 标志数组

public:
// 邻接矩阵类型的方法声明:
    AdjMatrixUndirGraph(ElemType es[], int vertexNum, int vertexMaxNum = DEFAULT_SIZE); 
        // 以数组es[]为顶点,顶点个数为vertexNum,允许的顶点最大数目为vertexMaxNum,边数为0的无向图
    AdjMatrixUndirGraph(int vertexMaxNum = DEFAULT_SIZE);   
        // 构造允许的顶点最大数目为vertexMaxNum,边数为0的无向图
    ~AdjMatrixUndirGraph();                 // 析构函数
    void Clear();                         // 清空图             
    bool IsEmpty();                 // 判断无向图是否为空 
    int GetOrder(ElemType &d) const;// 求顶点的序号   
    Status GetElem(int v, ElemType &d) const;// 求顶点的元素值 
    Status SetElem(int v, const ElemType &d);// 设置顶点的元素值
    int GetVexNum() const;                  // 返回顶点个数            
    int GetArcNum() const;                  // 返回边数          
    int FirstAdjVex(int v) const;       // 返回顶点v的第一个邻接点          
    int NextAdjVex(int v1, int v2) const;        // 返回顶点v1的相对于v2的下一个邻接点          
    void InsertVex(const ElemType &d);           // 插入元素值为d的顶点       
    void InsertArc(int v1, int v2);              // 插入顶点为v1和v2的边             
    void DeleteVex(const ElemType &d);           // 删除元素值为d的顶点           
    void DeleteArc(int v1, int v2);              // 删除顶点为v1和v2的边             
    Status GetTag(int v) const;                  // 返回顶点v的标志         
    void SetTag(int v, Status val) const;      // 设置顶点v的标志为val       
    AdjMatrixUndirGraph(const AdjMatrixUndirGraph<ElemType> &g);    // 复制构造函数
    AdjMatrixUndirGraph<ElemType> &operator =(const AdjMatrixUndirGraph<ElemType> &g); 
        // 赋值语句重载
  void Display();                            // 显示邻接矩阵无向图
};

邻接表

是邻接矩阵的改进，把邻接矩阵的每一行改为一个单链表。
顶点结点：表示每一个顶点。其中保存着该顶点的嘻嘻和指向该结点相应的边（弧）链表的指针。用顺序表存储，假设顶点的序号为数组的下标。
对于无向图：
边链表：依附于同一个顶点的边链接在同一个单链表中。
边结点：边链表中的每一个结点代表一条边。其中保存着与该边相关联的另一个顶点的序号和指向同一链表中下一个边结点的指针。
对于有向图：
弧链表：从同一个顶点发出的弧链接在同一个单链表中。
弧结点：弧链表中的每一个结点代表一条弧。其中保存着该弧的弧头顶点序号和指向同一链表中下一个弧结点的指针。
对于带权图：
边（弧）结点中另保存该边（弧）上的权值。


邻接表的边（弧）链表中，各个边（弧）结点的链入顺序是任意的，可根据边结点输入次序而定。
设图有n个顶点和e条边：用邻接表表示无向图时，需要n个顶点结点和2e个边结点；用邻接表表示有向图时，需要n个顶点结点和e个边结点（不考虑逆邻接表）。当e很小时，可以大量节省存储空间。
此外，把关联于同一个顶点的所有边（弧）链接在一个单链表中，可以大大方便图的操作。


有向网邻接表顶点结点类模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class ElemType, class WeightType>
struct AdjListNetWorkVex
{
// 数据成员:
    ElemType data;                      // 数据元素值
    AdjListNetworkArc<WeightType> *firstarc;
        // 指向邻接链表边结点的指针

// 构造函数:
    AdjListNetWorkVex();                // 无参数的构造函数
    AdjListNetWorkVex(ElemType val, 
        AdjListNetworkArc<WeightType> *adj = NULL);
        // 有参数的构造函数
};

有向网邻接表弧结点类模板

1
2
3
4
5
6
7
8
9
10
11
12
template <class WeightType>
struct AdjListNetworkArc
{
// 数据成员:
    int adjVex;                             // 弧头顶点序号
    WeightType weight;                      // 边的权值
    AdjListNetworkArc<WeightType> *nextarc; // 下一条边结点的指针 
// 构造函数:
    AdjListNetworkArc();                    // 无参数的构造函数
    AdjListNetworkArc(int v, WeightType w, AdjListNetworkArc<WeightType> * next = NULL);
          // 构造邻接点为v，权为w的邻接边
};

有向网邻接表类模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
template <class ElemType, class WeightType>
class AdjListDirNetwork
{
protected:
// 邻接表的数据成员:
    int vexNum, vexMaxNum, arcNum;                  // 顶点数目、允许的顶点最大数目和边数
    AdjListNetWorkVex<ElemType, WeightType> *vexTable;  // 顶点表
    mutable Status *tag;                            // 标志数组             
    WeightType infinity;                            // 无穷大的值 

public:
// 抽象数据类型方法声明及重载编译系统默认方法声明:
    AdjListDirNetwork(ElemType es[], int vertexNum, int vertexMaxNum = DEFAULT_SIZE, 
        WeightType infinit = (WeightType)DEFAULT_INFINITY);
        // 以数组es[]为顶点数据,顶点个数为vertexNum,允许的顶点最大数目为vertexMaxNum,
        // infinit表示无穷大,边数为0构造有向网
    AdjListDirNetwork(int vertexMaxNum = DEFAULT_SIZE, 
        WeightType infinit = (WeightType)DEFAULT_INFINITY);
        // 构造允许的顶点最大数目为vertexMaxNum,infinit表示无穷大,边数为0的有向网
    ~AdjListDirNetwork();                        // 析构函数
    void Clear();                                // 清空有向网            
    bool IsEmpty();                              // 判断有向网是否为空 
    int GetOrder(ElemType &d) const;             // 求顶点的序号  
    Status GetElem(int v, ElemType &d) const;    // 求顶点的元素值 
    Status SetElem(int v, const ElemType &d);    // 设置顶点的元素值
    WeightType GetInfinity() const;              // 取无穷大的值           
    int GetVexNum() const;                       // 求有向网的顶点个数            
    int GetArcNum() const;                       // 求有向网的边数个数            
    int FirstAdjVex(int v) const;                // 求有向网中顶点v的第一个邻接点          
    int NextAdjVex(int v1, int v2) const;        // 求有向网中顶点v1的相对于v2的下一个邻接点           
    void InsertVex(const ElemType &d);           // 插入元素值为d的顶点       
    void InsertArc(int v1, int v2, WeightType w);// 插入从顶点为v1到v2、权为w的边            
    void DeleteVex(const ElemType &d);           // 删除元素值为d的顶点           
    void DeleteArc(int v1, int v2);              // 删除从顶点为v1到v2的边            
    WeightType GetWeight(int v1, int v2) const;  // 求从顶点为v1到v2的边的权值
    void SetWeight(int v1, int v2, WeightType w);// 设置从顶点为v1到v2的边的权值
    Status GetTag(int v) const;                  // 求顶点v的标志      
    void SetTag(int v, Status tag) const;        // 设置顶点v的标志为tag     
    AdjListDirNetwork(const AdjListDirNetwork<ElemType, WeightType> &copy); // 复制构造函数
    AdjListDirNetwork<ElemType, WeightType> &operator =
        (const AdjListDirNetwork<ElemType, WeightType> &copy); // 重载赋值运算符 
    void Display(); // 显示有向网邻接表 
};

邻接多重表

图的每一条边用一个边结点表示，由六个域组成。
标记域 tag 标记该边是否被处理过或搜索过
信息域 weight 存储边的权值
顶点域 adjvex1 adjvex2 该边所依附的两个顶点在图中的序号
链接指针 nextarc1 nextarc2 指向下一条依附于顶点adjvex1/adjvex2的边
顶点结点 包含data域存储有关顶点的信息、firstarc域指向第一条依附于该顶点的边 == 所有的顶点结点组成一个顺序表


十字链表

图的每一条边用一个弧结点表示，由六个域组成。
标记域 tag 标记该边是否被处理过或搜索过
信息域 weight 存储边的权值
顶点域 tailvex headvex 弧尾顶点序号和弧头顶点序号
链接指针 tailnextarc headnextarc 指向下一条以顶点tailvex为始点（弧尾）的弧和下一条以顶点headvex为终点（弧头）的弧
顶点结点 包含data域存储有关顶点的信息、firstinarc域指向第一条以该顶点为终点的弧、firstoutarc域指向第一条以该顶点为始点的弧 == 所有的顶点结点组成一个顺序表


图的遍历与连通性

对于给定的图，沿着一些边（弧）访问图中所有的顶点，且使每个顶点仅被访问一次。

深度优先遍历

深度优先搜索
1）访问结点v，并标记v已被访问。
2）取顶点v的第一个邻接顶点w。
3）若顶点w不存在，算法结束；否则继续步骤4）。
4）若顶点w未被访问，则访问结点w，并标记w已被访问。
5）使w为顶点v的在原来w之后的下一个邻接顶点，转到步骤3）。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <class ElemType>
void DFSTraverse(const AdjMatrixUndirGraph<ElemType> &g, void (*Visit)(const ElemType &))
// 初始条件：存在图g
// 操作结果：对无向图g进行深度优先遍历
{
    int v;
    for (v = 0; v < g.GetVexNum(); v++)
        g.SetTag(v, UNVISITED);// 对每个顶点设置未访问标志

    for (v = 0; v < g.GetVexNum(); v++)
        
        if (g.GetTag(v) == UNVISITED)
            DFS(g, v , Visit);// 从尚未访问的顶点v开始进行深度优先搜索 
}

template <class ElemType>
void DFS(const AdjMatrixUndirGraph<ElemType> &g, int v, void (*Visit)(const ElemType &))
// 初始条件：存在图g
// 操作结果：从顶点v出发进行深度优先搜索
{   
    ElemType e; 
    g.SetTag(v, VISITED);       // 设置顶点v已访问标志
    g.GetElem(v, e);            // 取顶点v的数据元素值 
    Visit(e);                   // 访问顶点v
    for (int w = g.FirstAdjVex(v); w != -1; w = g.NextAdjVex(v, w))
        if (g.GetTag(w) == UNVISITED)
            DFS(g, w , Visit);  // 从v的尚未访问过的邻接顶点w开始进行深度优先搜索
}

图中n个顶点，e条边。
存储结构为邻接表，时间复杂度为O(n+e)。
存储结构为邻接矩阵，时间复杂度为O(n^2)。


广度优先遍历

广度优先搜索
1）访问结点v，并标记v已被访问，同时顶点v入队列。
2）当队列空时算法结束，否则继续步骤3）。
3）队头顶点出队列为v。
4）取顶点v的第一个邻接顶点w。
5）若顶点w不存在，转步骤3）；否则继续步骤6）。
6）若顶点w未被访问，则访问结点w，并标记w已被访问，同时顶点w入队列；否则继续步骤7）。
7）使w为顶点v的在原来w之后的下一个邻接顶点，转到步骤5）。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
template <class ElemType>
void BFSTraverse(const AdjMatrixUndirGraph<ElemType> &g, void (*Visit)(const ElemType &))
// 初始条件：存在图g
// 操作结果：对图g进行广度优先遍历
{
    int v;
    for (v = 0; v < g.GetVexNum(); v++)
        g.SetTag(v, UNVISITED); // 对每个顶点作未访问标志

    for (v = 0; v < g.GetVexNum(); v++)
        if (g.GetTag(v) == UNVISITED) 
            BFS(g, v , Visit);  // 从尚未访问的顶点v开始进行广度优先搜索
}

template <class ElemType>
void BFS(const AdjMatrixUndirGraph<ElemType> &g, int v, void (*Visit)(const ElemType &))
// 初始条件：存在图g
// 操作结果：从顶点v出发进行广度优先搜索
{   
    LinkQueue<int> q;
    int u, w;
    ElemType e;
    g.SetTag(v, VISITED);                       // 作访问标志
    g.GetElem(v, e);                            // 取顶点v的数据元素值 
    Visit(e);                                   // 访问顶点v
    q.EnQueue(v);                               // 顶点v入队 
    while (!q.IsEmpty())    {   
       q.DelQueue(u);
       for (w = g.FirstAdjVex(u); w != -1; w = g.NextAdjVex(u, w))
            if (g.GetTag(w) == UNVISITED){ // 对u尚未访问过的邻接顶点w进行访问
                g.SetTag(w, VISITED);   
                g.GetElem(w, e);    
                Visit(e);   
                q.EnQueue(w);
            }   
    }
}

图中n个顶点，e条边。
存储结构为邻接表，时间复杂度为O(n+e)。
存储结构为邻接矩阵，时间复杂度为O(n^2)。


连通分量

非连通图有k个连通分量，就要k次调用DFS或BFS才能访问图中的所有顶点。
深度优先生成森林、广度优先生成森林。


最小生成树 Minimum-cost spanning tree

克鲁斯卡尔算法 Kruskal

避圈法
1）初始化，在并查集中，连通网络的每一个顶点独立成一个等价类，连通网络的所有的边建立最小堆，最小生成树T中没有任何边，T中边的条数计数器i为0。
2）如果T中边的条数计数器i等于顶点数减1，则算法结束；否则继续步骤3）。
3）选取堆顶元素代表的边(v,u)，同时调整堆。
4）利用并查集的运算检查依附于边(v,u)的两个顶点v和u是否在同一个连通分量（即并查集的同一个子集合）上，如果是则转步骤2）；否则继续步骤5）。
5）将边(v,u)加入到最小生成树T中，同时将这两个顶点所在的连通分量合并成一个连通分量（即并查集中的相应两个子集合并成一个子集），继续步骤2）。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
template <class ElemType, class WeightType>
void MiniSpanTreeKruskal(const AdjMatrixUndirNetwork<ElemType, WeightType> &g)
// 初始条件：存在网g
// 操作结果：用Kruskal算法构造网g的最小代价生成树
{
    int count, VexNum = g.GetVexNum();
    KruskalEdge<ElemType, WeightType> KEdge;
    MinHeap<KruskalEdge<ElemType, WeightType> > ha(g.GetEdgeNum());
    ElemType  *kVex, v1, v2;
    kVex = new ElemType[VexNum];    // 定义顶点数组,存储顶点信息 
    for (int i = 0; i < VexNum; i++)
        g.GetElem(i, kVex[i]);
    UFSets<ElemType> f(kVex,VexNum);// 根据顶点数组构造并查集 
    for (int v = 0; v < g.GetVexNum(); v++)
        for (int u = g.FirstAdjVex(v); u >= 0; u = g.NextAdjVex(v, u))
            if (v < u)          {   // 将v < u的边插入到最小堆 
                g.GetElem(v, v1); 
                g.GetElem(u, v2);
                KEdge.vertex1 = v1;
                KEdge.vertex2 = v2;
                KEdge.weight = g.GetWeight(v,u);
                ha.Insert(KEdge);
            }
    count = 0;                      // 表示已经挑选的边数

    while (count < VexNum - 1)  {   
        ha.DeleteTop(KEdge);        // 从堆顶取一条边
        v1 = KEdge.vertex1;
        v2 = KEdge.vertex2;
        if (f.Differ(v1, v2))   {   // 边所依附的两顶点不在同一棵树上
            cout << "边:( " << v1 << ", " << v2 << " ) 权:" << KEdge.weight << endl ; // 输出边及权值
            f.Union(v1, v2);        // 将两个顶点所在的树合并成一棵树
            count++;
        }
    }
}

连通网络中n个顶点，e条边。
初始建堆，需要e次调用堆的插入操作，时间复杂度为O(elog2e)。
构造最小生成树，最多调用e次堆的删除操作、2e次并查集的查找操作和n-1次并查集的合并操作，时间复杂度分别为O(elog2e)、O(elog2e)和O(n)。
总时间复杂度O(elog2e)。
Kruskal算法适用于稀疏的（顶点个数较多而边数较少）连通网络。


普里姆算法 Prim

1）输入：一个加权连通图，其中顶点集合为V，边集合为E；
2）初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}，为空；
3）重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4）输出：使用集合Vnew和Enew来描述所得到的最小生成树。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
template <class ElemType, class WeightType>
void MiniSpanTreePrim(const AdjMatrixUndirNetwork<ElemType, WeightType> &g, int u0)
// 初始条件：存在网g,u0为g的一个顶点
// 操作结果：用Prim算法从u0出发构造网g的最小代价生成树
{
   WeightType min;
   ElemType v1, v2;
   int vexnum = g.GetVexNum();
   CloseArcType<ElemType, WeightType> * closearc;

   if (u0 < 0 || u0 >= vexnum)
      throw Error("顶点u0不存在!"); // 抛出异常

    int u, v, k;                        // 表示顶点的临时变量 
    closearc = new CloseArcType<ElemType, WeightType>[vexnum];  // 分配存储空间
    for (v = 0; v < vexnum; v++)    {   // 初始化辅助数组adjVex，并对顶点作标志，此时U = {v0}
        closearc[v].nearvertex = u0;
        closearc[v].lowweight = g.GetWeight(u0, v);
    }
    closearc[u0].nearvertex = -1;
    closearc[u0].lowweight = 0;
    
    for (k = 1; k < vexnum; k++) {  // 选择生成树的其余g.GetVexNum() - 1个顶点
        min = g.GetInfinity();
        v = u0;// 选择使得边<w, adjVex[w]>为连接V-U到U的具有最小权值的边
        for (u = 0; u < vexnum; u++)
           if (closearc[u].lowweight != 0 && closearc[u].lowweight < min) {
              v = u;
              min = closearc[u].lowweight;
           }
        if (v != u0) {
           g.GetElem(closearc[v].nearvertex, v1);
           g.GetElem(v, v2);     
           cout << "边:( " << v1 << ", " <<  v2 << " ) 权:" << min << endl ; // 输出边及权值
           closearc[v].lowweight = 0;       // 将w并入U
           for (u = g.FirstAdjVex(v); u != -1 ; u = g.NextAdjVex(v, u))     // 新顶点并入U后重新选择最小边
              if (closearc[u].lowweight != 0 && (g.GetWeight(v, u) < closearc[u].lowweight))    {   // <v, w>为新的最小边
                closearc[u].lowweight = g.GetWeight(v, u);
                closearc[u].nearvertex = v;
              }
        }
        
    }
    delete []closearc;          // 释放存储空间  
}

连通网络中n个顶点，e条边。
辅助数组closearc[]初始化，n-1次for循环，时间复杂度为O(n)。
把n-1个顶点加入U中，对每加入一个顶点到U，有两个并列的for循环分别实现查找具有最小权值的边和修改辅助数组closearc[]，时间复杂度均为O(n)。
总时间复杂度O(n^2)。
Prim算法适用于边稠密的连通网络。


最短路径

弧上权值为非负情形的单源点最短路径问题 —— Dijkstra

根据初始点，挨个的把离初始点最近的点一个一个找到并加入集合，集合中所有的点的d[i]都是该点到初始点最短路径长度，由于后加入的点是根据集合S中的点为基础拓展的，所以也能找到最短路径。
1）清除所有点的标号;
2）设d[0]=0，其他d[i]=INF; //INF是一个很大的值，用来替代正无穷
3）循环n次
{
在所有未标号结点中，选出d值最小的结点x;
给结点x标记;
对于从x出发的所有边(x,y)，更新d[y] = min{d[y], d[x]+w(x,y) }


简单易懂——Dijkstra算法讲解_Machine Learning with Turing’s Cat-CSDN博客
数据结构（十二）：最短路径(Dijkstra算法) - 简书


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
template <class ElemType, class WeightType>
void ShortestPathDij(const AdjListDirNetwork<ElemType, WeightType> &g, int v0, 
    int *path, WeightType *dist)
// 操作结果: 用Dijkstra算法求有向网g从顶点v0到其余顶点v的最短路径path和路径长度dist[v],
//  path[v]存储最短路径上终点的前一顶点的顶点号
{
    WeightType minVal, infinity = g.GetInfinity();
    int v, u;
    for (v = 0; v < g.GetVexNum(); v++){    // 初始化path和dist及顶点标志
        dist[v] = (v0 != v) ? g.GetWeight(v0, v) : 0;
        if (dist[v] == infinity)
            path[v] = -1;
        else 
            path[v] = v0;
        g.SetTag(v, UNVISITED); // 置顶点标志
    }
    g.SetTag(v0, VISITED);      // U={v0}

    for (int i = 1; i < g.GetVexNum(); i++){    // 求g.GetVexNum() - 1个顶点的最短路径  
        minVal = infinity;
        u = v0;
        for (v = 0; v < g.GetVexNum(); v++)   // 查找最小的最短路径 
            if (g.GetTag(v) == UNVISITED && dist[v] < minVal)       {
                // g.GetTag(v) == UNVISITED表示v∈V - U
                u = v;
                minVal = dist[v];
            }
        g.SetTag(u, VISITED);   // 将u并入U

        for (v = g.FirstAdjVex(u); v != -1; v = g.NextAdjVex(u, v))
            if (g.GetTag(v) == UNVISITED && minVal + g.GetWeight(u, v) < dist[v])   {
                // 如v∈V - U且minVal + g.GetWeight(u, v) < dist[v],则修改dist[v]及path[v]
                dist[v] = minVal + g.GetWeight(u, v);
                path[v] = u;
            }
    }
}

弧上权值为任意值的单源点最短路径问题（自学）—— BellmanFord


数据结构（十一）：最短路径(Bellman-Ford算法) - 简书


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template <class ElemType, class WeightType>
void ShortestPathBellmanFord(const AdjListDirNetwork<ElemType, WeightType> &g, int v0, 
    int *path, WeightType *dist)
// 操作结果: 用BellmanFord算法求有向网g从顶点v0到其余顶点v的最短路径path和路径长度dist[v],
//  path[v]存储最短路径上终点的前一顶点的顶点号
{
    WeightType *distTemp, minVal, infinity = g.GetInfinity();
    int v, u, vexNum = g.GetVexNum();
    distTemp = new WeightType[vexNum];
    for (v = 0; v < vexNum; v++){   // 初始化path和dist
        dist[v] = (v0 != v) ? g.GetWeight(v0, v) : 0;
        if (dist[v] == infinity)
            path[v] = -1;
        else 
            path[v] = v0;
    }

    for ( int  k = 2; k < vexNum ; k++) {
        for (v = 0; v < vexNum; v++)
            distTemp[v] = dist[v];
        for (u = 0; u < vexNum ; u++) 
            if (u != v0)
                for (v = 0; v < vexNum; v++) 
                    if (v != v0 && distTemp[u] > dist[v] + g.GetWeight(v, u)) {
                        distTemp[u]= dist[v] + g.GetWeight(v, u);
                        path[u] = v;
                    }
        for (v = 0; v < vexNum; v++)
            dist[v] = distTemp[v];
   }
}

所有顶点之间的最短路径 —— Floyd

通过一个图的权值矩阵 求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵 ，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);
空间复杂度为O(n^2)。


数据结构（十三）：最短路径(Floyd算法) - 简书


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template <class ElemType, class WeightType>
void ShortestPathFloyd(const AdjListDirNetwork<ElemType, WeightType> &g, int **path, 
    WeightType **dist)
// 操作结果: 用Floyd算法求有向网g中各对顶点u和v之间的最短路径path[u][v]和路径长度
//  dist[u][v],path[u][v]存储从u到v的最短路径上至此顶点的前一顶点的顶点号,dist[u][v]
//  存储从u到v的最短路径的长度
{
    for (int u = 0; u < g.GetVexNum(); u++)
        for (int v = 0; v < g.GetVexNum(); v++)
        {   // 初始化path和dist
            dist[u][v] = (u != v) ? g.GetWeight(u, v) : 0;
            if (u != v && dist[u][v] < g.GetInfinity())
               path[u][v] = u;  // 存在边<u,v>
            else
               path[u][v] = -1;                                         // 不存在边<u,v>
        }

    for (int k = 0; k < g.GetVexNum(); k++)
        for (int i = 0; i < g.GetVexNum(); i++)
            for (int j = 0; j < g.GetVexNum(); j++)
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    // 从i到k再到j的路径长度更短
                    dist[i][j] = dist[i][k] + dist[k][j]; 
                    path[i][j] = path[k][j];
                }
}

活动网络

用顶点表示活动的网络 AOV —— 拓扑排序

Activity On Vertex
AOV网络中不能出现有向回路（有向环）。
对AOV网络构造它的拓扑有序序列，即将AOV网络中的各个顶点排列成一个线性有序的序列，使得AOV网络中所有的前驱和后继关系都能得到满足。
拓扑排序 <==> 没有有向环
一个AOV网络的拓扑有序序列不是唯一的。


拓扑排序简单方法
1）在AOV网络中选一个没有直接前驱的顶点v；并输出之。
2）从图中删去该顶点，同时删去所有从顶点v发出的弧。
3）重复以上步骤1）和2），直到没有直接前驱的顶点全部输出。如果图中所有顶点已全部输出，则拓扑有序序列形成，拓扑排序完成；否则说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了，这时AOV网络必定存在有向环。


使用栈（或队列）的拓扑排序算法
1）建立入度为零的顶点栈。
2）当入度为零的顶点栈为空时算法转步骤6），否则继续步骤3）。
3）入度为零的顶点栈中栈顶元素v出栈，并输出之顶点v。
4）从AOV网络中删去顶点v和多有从顶点v发出的弧<v,j>，并将顶点j的入度减1。
5）如果顶点j入度减至0，则将该顶点进入入度为零的顶点栈；转步骤2）。
6）如果输出顶点个数少于AOV网络的顶点个数，则输出网络中存在有向环的信息；算法结束。
为了建立入度为零的顶点栈，可以不另外分配存储空间，直接利用顶点的入度数组InDegree[]中入度为零的元素，建立入度为零的静态链栈。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template <class ElemType>
Status TopSort(const AdjListDirGraph<ElemType> &g)
// 初始条件：存在有向图g
// 操作结果：如g无回路,则输出g的顶点的一个拓扑序列,并返回SUCCESS,否则返回FAIL
{
    int *indegree = new int[g.GetVexNum()]; // 顶点入度数组       
    int v, u, count = 0, top = -1;
    ElemType e;
    StatIndegree(g, indegree);              // 统计顶点的入度
    

    for (v = 0; v < g.GetVexNum(); v++)
        if (indegree[v] == 0)  {            // 入度为0的顶点入栈 
            indegree[v] = top;
            top = v;
        }

    while (top != -1)   {   // 栈非空
        v = top;
        top = indegree[v];
        g.GetElem(v, e);
        cout << e << "  ";
        count++;            // 对输出顶点进行记数
        for (u = g.FirstAdjVex(v); u != -1; u = g.NextAdjVex(v, u))
            // 对v的每个邻接点u入度减1
            if (--indegree[u] == 0) {// u入度为0,将u入栈
               indegree[u] = top;
               top = u;
            }
    }
    delete []indegree;                      // 释放indegree所占用的存储空间

    if (count < g.GetVexNum()) return FAIL; // 图g有回路
    else return SUCCESS;                    // 拓扑排序成功
}

AOV网络中n个顶点，e条边。
搜索入度为零的顶点建立链栈，for循环，时间复杂度为O(n)。
（网络中没有回路）所有顶点都需要进一次栈，出一次栈，时间复杂度为O(n)。
顶点入度减1的运算，执行e次，时间复杂度O(e)。
总时间复杂度O(n+e)。


用边表示活动的网络 AOE —— 关键路径

Activity On Edges
AOE网络中不能出现有向回路（有向环）。
AOE网络中不能出现多个入度为0的顶点。
AOE网络中只有一个入度为0的顶点（称为源点）用于彼岸是这个开始事件；只有一个出度为0的顶点（称为汇点）用于表示这个完成事件。由于活动有先后或并行，从源点到汇点的路径可能不止一条，相应路径上所有活动的持续时间之和可能是不同的，但只有当各条路径上的所有活动都完成了，整个工程才算完成。整个工程完成所需的最短时间取决于从源点到汇点的最长路径长度，这条路径最长的路径就叫做关键路径（critical path），关键路径上的所有活动都是关键活动（即不按期完成就会影响整个工程完成的活动）。
定义以下相关量找出关键活动：
1）事件Vi的最早可能发生时间Ve[i]（V early）
2）事件Vi的最迟允许发生时间Vl[i]（V late）
3）活动ak的最早可能开始时间e[k]
4）活动ak的最迟允许开始时间l[k]
5）活动ak的时间余量l[k]-e[k]（时间余量为零的活动室关键活动）


计算关键路径的算法步骤
1）输入n个顶点和e条带权的有向边，建立邻接表结构。
2）从源点V0出发，令Ve[0]=0，按拓扑有序的顺序计算每个顶点的Ve[j]（j=1,2,…,n-1）。若拓扑排序中遍历的顶点数小于n，则说明网络中存在有向环，不能继续求关键路径。
3）从汇点Vn-1出发，令Vl[n-1]=Ve[n-1]，按拓扑有序顺序求各顶点的Vl[i]（i=0,1,…,n-2）。
4）根据各顶点Vi和Ve[i]和Vl[i]的值，求各条弧ak的e[k]和l[k]。
5）输出关键活动ak（e[k]==l[k]即为关键活动）。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
template <class ElemType, class WeightType>
Status CriticalPath(const AdjListDirNetwork<ElemType, WeightType> &g)
// 初始条件：存在有向网g
// 操作结果：如g无回路,则输出g的关键活动,并返回SUCCESS,否则返回FAIL
{
    int *indegree = new int[g.GetVexNum()]; // 顶点入度数组
    WeightType *ve = new int[g.GetVexNum()];    // 事件最早发生时刻数组
    WeightType *vl = new int[g.GetVexNum()];  // 事件最迟发生时刻数组
    LinkQueue<int> q;                   // 用于存储入度为0的顶点
    LinkStack<int> s;                   // 用于实现逆扑序序列的栈
    int ee, el, u, v, count = 0;
    ElemType e1, e2;

    for (v = 0; v < g.GetVexNum(); v++)     // 初始化事件最早发生时刻
        ve[v] = 0;
    StatIndegree(g, indegree);              // 统计顶点的入度
    for (v = 0; v < g.GetVexNum(); v++) // 遍历顶点
        if (indegree[v] == 0)   // 建立入度为0的顶点队列
            q.EnQueue(v);

    while (!q.IsEmpty())    {   // 队列非空
        q.DelQueue(u);          // 取出一个入度为0的顶点
        s.Push(u);              // 顶点u入栈,以便得逆拓扑排序序列
        count++;                // 对顶点进行记数
        for (v = g.FirstAdjVex(u); v != -1; v = g.NextAdjVex(u, v))     {
            // v为弧<u,v>的弧头顶点,对u的每个邻接点入度减1
            if (--indegree[v] == 0) // v入度为0,将v入队
                q.EnQueue(v);
            if (ve[u] + g.GetWeight(u, v) > ve[v])  // 修改ve[v]
                ve[v] = ve[u] + g.GetWeight(u, v);
        }
    }
    delete []indegree;          // 释放indegree所占用的存储空间

    if (count < g.GetVexNum())  {
        delete []ve;            // 释放ve所占用的存储空间
        return FAIL;            // 网g有回路
    }

    s.Top(u);                               // 取出栈顶,栈顶为汇点
    for (v = 0; v < g.GetVexNum(); v++)     // 初始化事件最迟发生时刻
        vl[v] = ve[u];

    while (!s.IsEmpty())      { // s非空
        s.Pop(u);
        for (v = g.FirstAdjVex(u); v != -1; v = g.NextAdjVex(u, v)) // v为u的一个邻接点
            if (vl[v] - g.GetWeight(u, v) < vl[u])  // 修改vl[u]
                vl[u] = vl[v] - g.GetWeight(u, v);
    }

    for (u = 0; u < g.GetVexNum(); u++) {   // 求ee, el和关键路径
        for (v = g.FirstAdjVex(u); v != -1; v = g.NextAdjVex(u, v))     {   // v为u的一个邻接点
            ee = ve[u]; el = vl[v] - g.GetWeight(u, v);
            if (ee == el)   {   // <u, v>为关键活动
                g.GetElem(u, e1);
                g.GetElem(v, e2);
                cout << "<" << e1 << "," << e2 << "> ";
            }
        }
    }
    
    delete []ve;                // 释放ve所占用的存储空间
    delete []vl;                // 释放vl所占用的存储空间
    return SUCCESS;             // 操作成功
}

AOE网络中n个顶点，e条边。
求各顶点的Ve[i]和Vl[i]，时间复杂度为O(n+e)。
求各个活动的e[k]和l[k]，时间复杂度为O(n+e)。
总时间复杂度O(n+e)。
不是任一关键活动加速就一定能使整个工程提前完成。
在存在多条关键路径的情况下，只有加快那些处在所有关键路径上的公共关键活动的进度，才能提前完成整个工程。而这些关键活动的加速是有限度的，即不能改变关键路径。