数据结构与算法A 第七章图

• 在图这种非线性结构中，结点之间的关系可以是任意的：

  1. 线性结构：唯一前驱、唯一后继，反应一种线性关系
  2. 树形结构：唯一前驱、多个后继，反应一种层次关系
  3. 图结构：不加限制前驱的个数，也不加限制后继的个数，反应一种网状关系

• 线性表和树可以看做是受限图

图的定义和基本术语

• 图由表示数据元素的集合 V 和表示数据之间关系的集合 E 组成：记为G= (V，E)

  1. V 是顶点 (vertex) 集合
  2. E 是边 (edge) 的集合，即顶点的序偶

• 无向图：一条边的顶点序偶是无序的，即该边无方向。无序的偶对用()表示，(v1,v2)和(v2,v1)是同一条边

• 有向图：一条边的顶点序偶是有序地，即边有方向。有序偶对用<>表示，有向图的边也称为弧，<v1,v2>中 v1 成为弧尾或边的始点，v2 称为弧头或边的终点。<v1,v2>和<v2,v1>是不同的两条弧

• 带权图：每条边或弧都带权的图，可以用于表示从一个顶点到另一个顶点的距离、代价或耗费等

• 图的限制：

  1. 两个顶点之间的边不能多于一条
  2. 不考虑图中顶点到自身的边

• n:图中顶点的数目。e:边或弧的数目：

  1. 无向图中e的取值范围为[0,n(n-1)/2]
  2. 有向图中e的取值范围为[0,n(n-1)]

• 稀疏图：边数相对较少的图；稠密图：边数相对较多的图；完全图：任何两个顶点间都有边相关联的图

• 完全图具有最大的边数

• G’是图G的子图:图G= ( V，E )，G’= ( V’，E’)中，若 V’≤V，E’≤E，并且E’中的边所关联的顶点都在 V’中

• 连接一对邻接点v1,v2的边(v1,v2)被称为与顶点v1和v2相关联的边，或者称边(v1,v2)依附于顶点v1,v2

• 度：

  1. 无向图：顶点v的度是与该顶点相关联边的数目，记为D(v)
  2. 有向图：D(v) = ID(v) + OD(v)
     1. 把以顶点v为终点的弧的数目称为v的入度，记为ID(v)
     2. 把以顶点v为始点的弧的数目称为v的出度，记为OD(v)
     3. 把出度为0的点称为终端顶点或叶子

• 一般来说如果图中有n个顶点，e条边，D(vi)为顶点vi的度数，有e = 1/2(Σi D(vi))

• 路径：Vp，Vi1，Vi2，…，Vin，Vq，使得(Vp，Vi1) ， (Vi1，Vi2) ，…， (Vin，Vq)都在 E 中。路径长度定义为路径上边的数目

• 回路或环：第一个顶点和最后一个顶点相同的路径。不带回路的图称为无环图，不带回路的有向图称为有向无环图

• 序列中顶点不重复出现的路径成为简单路径。除了第一个和最后一个顶点外，其余顶点不重复的回路成为简单回路

• 有根的图：有向图中，若存在一个顶点v0，从此顶点有路径可以到达图中其他所有顶点，v0称为图的根

• 连通图：对于图中的任意两个顶点vi,vj，vi和vj都是联通的(无向图中从顶点vi到vj有路径)

• 连通分量：无向图中的极大连通子图

• 有向图 G 是强连通图：G中任意两个顶点vi,vj都有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径

• 有向图的强连通分量(分支)：有向图强连通的极大子图

• 连通图的生成树：含有该连通图全部顶点的一个极小连通子图。若连通图 G 的顶点个数是 n ,则 G 的生成树的边数为 n-1 ，反之不成立

• 如果无向图 G 的一个生成树 G’ 上添加一条边，则 G’中一定有环，反之如果 G’ 的边数小于 n-1 则 G’ 一定不连通

• 自由树：不带简单回路的无向图，是连通的，并且具有 n-1 条边

• 网络：带权的连通图

• 有向树：如果一个有向图只有一个顶点的入度为0，其余顶点的入度均为1

• 一个有向图的生成森林由若干个有向树组成

图的ADT

• 图的基本操作主要是插入、删除、查找等

• 与无序树一样，图的顶点之间没有次序。但是对于具体的图，根据制定的存储结构建立完成以后，图中的每一个顶点的所有邻接点之间就有了先后顺序

class Graph
{
// 图的ADT
public:
    int VerticesNum(); // 返回图的顶点个数
    int EdgesNum(); // 返回图的边数
    Edge FirstEdge(int oneVertex); // 第一条关联边
    Edge NextEdge(Edge preEdge); // 下一条兄弟边
    bool setEdge(int fromVertex,int toVertex,int weight); // 添一条边
    bool delEdge(int fromVertex,int toVertex); // 删边
    bool IsEdge(Edge oneEdge); // 判断oneEdge是否int FromVertex
    int FromVertex(Edge oneEdge); // 返回边的始点
    int ToVertex(Edge oneEdge); // 返回边的终点
    int Weight(Edge oneEdge); // 返回边的权
};

图的存储结构

相邻矩阵

• 图的相邻矩阵(adjacency matrix，或邻接矩阵)表示顶点之间的邻接关系，即有没有边

• 设 G = <V，E> 是一个有 n 个顶点的图，则图的相邻矩阵是一个二维数组 A[n，n]，定义如下：

• 对于 n 个顶点的图，相邻矩阵的空间代价都为O(n²)，与边数无关

• 无向图的相邻矩阵是对称的，顶点i的度是第i行元素或第i列元素累加之和。矩阵中1的个数的一半为图中边的数目

• 有向图的相邻矩阵不一定是对称的，第j列所有元素之和为顶底vj的入度ID(vj)；第i行的所有元素之和是顶点vi的出度OD(vi)。矩阵中1的个数为图的边数

• 网络(带权图)的相邻矩阵定义如下：

• 对于带权有向图，第i行所有0 < A[i,j] < 无限 的元素个数之和就是顶点vi的出度，第j列中所有0 < A[i,j] < 无限 的元素数目之和为顶点vj的入度

// 相邻矩阵
class Edge 
{ // 边类
public:
    int from,to,weight； // 边的始点, 终点, 权
    Edge() 
    { // 缺省构造函数
        from = -1; to = -1; weight = 0; 
    }
    Edge(int f,int t,int w)
    { // 给定参数的构造函数
        from = f; to = t; weight = w; 
    }
};
class Graph 
{
public:
    int numVertex; // 图中顶点的个数
    int numEdge; // 图中边的条数
    int *Mark; // 图的顶点访问标记
    int *Indegree; // 存放图中顶点的入度
};

class Graphm : public Graph
{
private:
    int ** matrix;
public:
    Graphm(int numVert) : Graph(numVert) 
    {  	//构造函数
        int i, j;
        matrix = (int **) new int* [numVertex];    //声明一个相邻矩阵；
        for (int i=0; i<numVertex; i++) 		//构造一个相邻矩阵；
            matrix[i]= new int[numVertex];
        for (int i=0; i<numVertex; i++) 		//初始化相邻矩阵；
            for (int j=0; j<numVertex; j++)
            matrix[i][j]=0;
    }
    ～Graph()
    {  			//析构函数
        for (int i=0; i<numVertex; i++) 			
            delete[] matrix[i];
        delete[] matrix;
    }
    Edge FirstEdge(int oneVertex) 
    { 	//返回顶点oneVertex的第一条边；
        Edge  myEdge;
        myEdge.from = oneVertex;  myEdge.to = -1;
        for (int i=0; i<numVertex; i++) 
        {
            if (matrix[oneVertex][i]!=0)
            {
                myEdge.to=i;	myEdge.weight = matrix[oneVertex][i];
                break;
            }
        }
        return myEdge;
    }
    Edge NextEdge(Edge preEdge) 
    { //返回与边preEdge有相同顶点的下一条边
        Edge  myEdge;
        myEdge.from = preEdge.from; 
        myEdge.to = -1;                         //-1可以判断是非边
        for (int i=preEdge.to+1; i<numVertex; i++) 
        {
            if (matrix[preEdge.from][i]!=0)
            {
                myEdge.to=i;	
                myEdge.weight = matrix[oneVertex][i];
                break;
            }
        }
        return myEdge;
    }
    void setEdge(int from, int to, int weight) 
    {  	 //为图设定一条边；
        if (matrix[from][to]<=0)
        {
            numEdge++;	
            indegree[to]++;
        }
        matrix[from][to]=weight;
    }
    void delEdge(int from, int to) 
    { 		//删掉图的一条边；
        if (matrix[from][to]>0)
        {
            numEdge--;	
            indegree[to]--;
        }
        matrix[from][to]=0; //0可以判断是非边
    }
};

邻接表

• 对于稀疏图，可以采用邻接表存储法:边较少，相邻矩阵就会出现大量的零元素,相邻矩阵的零元素将耗费大量的存储空间和时间

• 邻接表 ( adjacency list ) 链式存储结构，由顶点表和边表(依附于同一个顶点的边组织成一个单链表)组成

  1. 顶点表：对应n个顶点，包括顶点数据和指向边表的指针
  2. 边链表：对应m条边，包括与顶点 vi 邻接的另一顶点的序号和指向边表下一表目指针
     

• 无向图的邻接表表示：需要|V|＋ 2|E|个存储单元，无向图同一条边在邻接表中出现两次

• 有向图的邻接表（出边表）：需要|V|＋ |E|个存储单元，一条弧在邻接表中只出现一次，顶点vi边表的表目个数就是该顶点的出度。要知道顶点vi的入度则需遍历整个邻接表

• 有向图的逆邻接表（入边表）：顶点vi的边表中表示的是以该顶点为终点的边，顶点vi边表的表目个数就是该顶点的入度

• 带权图：每一个边结点需要设置一个域来保存权值信息

• 边表中的表目顺序按照顶点编号从小到大排序

// 用邻接表存储图代码见书p171

十字链表

• 十字链表是有向图的另一种链式存储结构，可以看成是邻接表和逆邻接表的结合：
  1. 每一条弧有一个表目，共有5个域：头 headvex、尾 tailvex 、下一条共尾弧 tailnextarc；下一条共头弧 headnextarc；弧权值等 info 域
  2. 顶点表目由3个域组成：data 域；firstinarc 第一条以该顶点为终点的弧；firstoutarc 第一条以该顶点为始点的弧
     

• 十字链表中很容易找到以vi为始点和终点的弧

• 从顶点结点vi的firstoutaec出发，由tailnextarc域链接起来的链表正好是原来的邻接链表结构

• 从顶点结点vi的firstinarc出发，由headnextarc域连接起来的链表正好是原来的逆邻接表结构

图的周游

• 图周游：定图G和任一顶点V0，从V0出发按照一定策略访问G中所有的顶点，每个顶点访问一次

• 图周游需要考虑：

  1. 非连通图：从一顶点出发，可能不能到达所有其它的顶点
  2. 存在回路的图：也有可能会陷入死循环

• 为了避免重复访问同一个顶点，在周游图的过程中应该几下顶点是否已经被访问过，若遇到已访问的顶点则不再访问：

  1. 顶点保留一标志位，初始时标志位置未访问（UNVISITED）
  2. 在周游过程中，当顶点被访问时，标志位置已访问（VISITED）

• 图的周游算法框架：

void graph_traverse(Graph& G) 
{
    // 对图所有顶点的标志位进行初始化
    for(int i=0; i<G.VerticesNum(); i++)
        G.Mark[i] = UNVISITED;
    // 检查图的所有顶点是否被标记过，如果未被标记，
    // 则从该未被标记的顶点开始继续遍历
    // do_traverse函数用深度优先或者广度优先
    for(int i=0; i<G.VerticesNum(); i++)
        if(G.Mark[i] == UNVISITED)
            do_traverse(G, i);
}

深度优先搜索

• 图的深度优先搜索(DFS)类似于树的先跟次序周游，深度优先周游方法的特点是尽可能先对纵深方向进行搜索

• 深度优先搜索的基本思想：

  1. 访问顶点V，然后访问该顶点未被访问过的邻接顶点V’
  2. 从V’出发递归地按照深度优先的方式周游下去
  3. 直到当一所有邻接点都被访问过的顶点U时，则回到已访问顶点序列中最后一个拥有未被访问顶点的下一邻接点W
  4. 再从W出发递归地按照深度优先的方式周游
  5. 最后，当任何已被访问过的顶点都没有未被访问的相邻顶点时，则周游结束
  6. 注：若G是连通图，则周游过程结束；否则选择一个尚未访问的顶点作为新的源点进行深度优先搜索，直到图中所有顶点均被访问

// 图的深度优先周游算法
void DFS(Graph& G, int v) 
{ // 深度优先搜索的递归实现
    G.Mark[v] = VISITED; // 把标记位设置为 VISITED
    Visit(G,v); // 访问顶点v
    for (Edge e = G.FirstEdge(v); G.IsEdge(e);e = G.NextEdge(e))
        if (G.Mark[G.ToVertex(e)] == UNVISITED)
            DFS(G, G.ToVertex(e));
    PostVisit(G,v); // 对顶点v的后访问
}

• 时间复杂度分析：
  1. 用相邻矩阵表示图时，所需时间为O(n)
  2. 用邻接表表示图，时间复杂度是O(n + e)

广度优先搜索

• 广度优先搜索(BFS)的遍历过程：
  1. 从图中的某个顶点 v0 出发，访问顶点V0
  2. 问V0邻接到的所有未被访问过的邻居顶点V01，V02，…V0i
  3. 再依次访问V01，V02，…V0i邻接到的所有未被访问的邻居顶点
  4. 重复上述过程直到与源点v有路径想通的顶点都被访问过为止
  5. 注：若G是连通图，则周游完成，否则在图G中选择一个尚未访问的顶点作为新源点进行BFS

• 广度优先搜索的过程类似于树的按层次次序周游。可以使用FIFO队列保存已被访问过的结点，从而使得先访问的顶点的邻接点在下一轮被优先访问

void BFS(Graph& G, int v) 
{
    using std::queue; queue<int> Q; // 使用STL中的队列
    Visit(G,v); // 访问顶点v
    G.Mark[v] = VISITED; Q.push(v); // 标记,并入队列
    while (!Q.empty()) 
    { // 如果队列非空
        int u = Q.front (); // 获得队列顶部元素
        Q.pop(); // 队列顶部元素出队
        for (Edge e = G.FirstEdge(u); G.IsEdge(e);
            e = G.NextEdge(e)) // 所有未访问邻接点入队
        if (G.Mark[G.ToVertex(e)] == UNVISITED)
        {
            Visit(G, G.ToVertex(e));
            G.Mark[G.ToVertex(e)] = VISITED;
            Q.push(G.ToVertex(e));
        }
    }
}

• 广度优先搜索的时间复杂度同深度优先搜索

拓扑搜索

• 对于有向无环图 G= (V，E) ，V 里顶点的线性序列称作一个拓扑序列，该顶点序列满足：若在有向无环图 G 中从顶点 vi 到 vj 有一条路径，则在序列中顶点 vi 必在顶点 vj 之前

• 拓扑排序 (topological sort)：将一个有向无环图中所有顶点在不违反 先决条件关系的前提下排成线性序列的过程称为拓扑排序

• 拓扑排序可以解决先决条件问题，即以某种线性顺序来组织多项任务，以便能够在满足先决条件的情况下逐个完成各项任务

• 拓扑排序的性质：

  1. 一个有向无环图顶点的拓扑序列并不是唯一的
  2. 若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的
  3. 环存在时不存在拓扑序列

• 进行有向图的拓扑排序的方法如下：

  1. 从有向图中选出一个没有前驱(入度为0)的顶点并输出
  2. 删除图中该顶点和所有以它为起点的弧
  3. 重复1,2可能出现两种情况：
     1. 顶点全部被输出，则完成了有向无环图的拓扑排序
     2. 不存在没有前驱的结点，当图中还有顶点没有输出时，说明有向图中有换

• 拓扑排序可以检查有向图中是否存在环

• 用邻接表作为有向图的存储结构来实现有向图的拓扑排序：，诶个顶点中加入一个存放该顶点的入度的域。检查数组就可以方便的找出入度为0的顶点，即没有前驱的顶点。删除该顶点及以之为尾的弧，即将边表中所有弧头顶点的入度-1

• 可把入度为0的顶点构造成一个队列。删除入度为0的定嗲，如果此时某个顶点的入度减为0，则将其插入队列中

void TopsortbyQueue(Graph& G) 
{
    for (int i = 0; i < G.VerticesNum(); i++) 
        G.Mark[i] = UNVISITED; // 初始化
    using std::queue; queue<int> Q; // 使用STL中的队列
    for (i = 0; i < G.VerticesNum(); i++) // 入度为0的顶点入队
        if (G.Indegree[i] == 0) Q.push(i);
    while (!Q.empty()) 
    { // 如果队列非空
        int v = Q.front(); Q.pop(); // 获得队列顶部元素， 出队
        Visit(G,v); G.Mark[v] = VISITED; // 将标记位设置为VISITED
        for (Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)) 
        {
            G.Indegree[G.ToVertex(e)]--; // 相邻的顶点入度减1
            if (G.Indegree[G.ToVertex(e)] == 0) // 顶点入度减为0则入队
                Q.push(G.ToVertex(e));
        } 
    }
    for (i = 0; i < G.VerticesNum(); i++) // 判断图中是否有环
        if (G.Mark[i] == UNVISITED) 
        {
            cout<<“ 此图有环！”; 
            break;
        } 
}

• 时间复杂度：O(n + e)

// 深度优先搜索实现的拓扑排序
int *TopsortbyDFS(Graph& G) 
{ // 结果是颠倒的
    for(int i=0; i<G.VerticesNum(); i++) // 初始化
        G.Mark[i] = UNVISITED;
    int *result=new int[G.VerticesNum()];
    int index=0;
    for(i=0; i<G.VerticesNum(); i++) // 对所有顶点
        if(G.Mark[i] == UNVISITED)
            Do_topsort(G, i, result, index); // 递归函数
    for(i=G.VerticesNum()-1; i>=0; i--) // 逆序输出
        Visit(G, result[i]);
return result;
}

// 拓扑排序递归函数
void Do_topsort(Graph& G, int V, int *result, int&index) 
{
    G.Mark[V] = VISITED;
    for (Edge e = G.FirstEdge(V);G.IsEdge(e); e=G.NextEdge(e)) {
        if (G.Mark[G.ToVertex(e)] == UNVISITED)
            Do_topsort(G, G.ToVertex(e),result, index);
    }
    result[index++]=V; // 相当于后处理
}

• 时间复杂度：
  1. 采用邻接表表示时，O(n + e)
  2. 采用相邻矩阵表示时，O(n²)

最短路径

• 最短路径问题：从带权图中找到A城市到B城市之间路径上的权值之和最小的方案

• 源点：路径上的第一个点；汇点、终点：路径上的最后一个点

单源路径问题

• 单源最短路径(single-source shortest paths)：给定带权图 G = <V，E>，其中每条边 (vi，vj) 上的权W[vi，vj] 是一个 非负实数 。计算从任给的一个源点 s 到所有其他各结点的最短路径

• Dijkstra算法基本思想：

  1. 把所有结点分成两组
     1. 第一组 U 包括已确定最短路径的结
     2. 第二组 V–U 包括尚未确定最路径的结点
  2. 按最短路径长度递增的顺序逐个把第二组的结点加到第一组中
  3. 按最短路径长度递增的顺序逐个把第二组的结点加到第一组中，直至从s出发可以到达的所有顶点都包括进第一组
  4. 在合并过程中，保持s到第一组各顶点的最短路径长度都不大于从s到第二组各顶点的最短路径长度
     1. 第一组顶点对应的距离值：从s到该顶点的最短路径长度
     2. 第二组顶点对应的距离值：从s到该顶点的值包括第一组的顶点为中间顶点的最短路径长度

• 具体过程：

  1. 初始化：第一组只包括源点s，第二组包括其它所有顶点。s距离值为0，第二组顶点的距离值确定如下：若有边<s，Vi>或（s，Vi），则Vi的距离值为边所带的权，否则为∞
  2. 过程：次从第二组的顶点中选一个其距离值为最小的顶点Vm加入到第一组中
     1. 每往第一组加入顶点Vm，要对第二组各顶点的距离值进行一次修正：若加进Vm做中间顶点，使从s到Vi的最短路径比不加Vm的短，则需要修改Vi的距离值
     2. 修改后再选距离值最小的顶点加入到第一组中，重复上述过程
     3. 结束条件：直到图的所有顶点都包括在第一组中或者再也没有可加入到第一组的顶点存在

• Dijkstra算法是用贪心算法设计的一个典型。每次从V-S中选择具有最短特殊路径长度的顶点u，确定从源点到u的最短路径

• Dijkstra单源最短路径算法

class Dist 
{ // Dist类，用于保存最短路径信息
public:
    int index; // 结点的索引值，仅Dijkstra算法用到
    int length; // 当前最短路径长度
    int pre; // 路径最后经过的结点
};

void Dijkstra(Graph& G, int s, Dist* &D) 
{ // s是源点
    D = new Dist[G. VerticesNum()]; // 记录当前最短路径长度
    for (int i = 0; i < G.VerticesNum(); i++) 
    { // 初始化
        G.Mark[i] = UNVISITED;
        D[i].index = i; D[i].length = INFINITE; D[i].pre = s;
    }
    D[s].length = 0; // 源点到自身的路径长度置为0
    MinHeap<Dist> H(G. EdgesNum()); // 最小值堆用于找出最短路径
    H.Insert(D[s]);
    for (i = 0; i < G.VerticesNum(); i++) 
    {
        bool FOUND = false;
        Dist d;
        while (!H.isEmpty()) 
        {
            d = H.RemoveMin(); //获得到s路径长度最小的结点
            if (G.Mark[d.index] == UNVISITED) 
            { //如果未访问过则跳出循环
                FOUND = true; break;
            } 
        }
        if (!FOUND) break; // 若没有符合条件的最短路径则跳出本次循环
        int v = d.index;
        G.Mark[v] = VISITED; // 将标记位设置为 VISITED
        for (Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)) // 刷新最短路
            if (D[G.ToVertex(e)].length > (D[v].length+G.Weight(e))) 
            {
                D[G.ToVertex(e)].length = D[v].length + G.Weight(e);
                D[G.ToVertex(e)].pre = v;
                H.Insert(D[G.ToVertex(e)]);
            } 
    }
}

• Dijkstra算法时间代价分析：O((n + e)loge)

• Dijkstra算法不支持负权值：如果存在总权值为负的回路，则将出现权值为 -无穷 的情况

每对顶点间的最短路径

• 每对顶点间的最短路径：给定一个带权图G = <V,E>，其中每条边(vi,vj)上的权W[vi,vj]是一个非负实数。要求计算对任意的顶点有序对<vi,vj>找出从顶点vi到顶点vj的最短路径

  1. F1:每次以一个顶点为源点反复执行Dijkstra算法，时间复杂度为O(n^3)
  2. F2:Floyd算法，是典型的动态规划算法，时间复杂度为O(n^3)，但是形式上简单

• Floyd算法用相邻矩阵adj表表示带权有向图，基本思路：

  1. 初始化 adj(0) 为相邻矩阵 adj
  2. 在矩阵 adj(0)上做 n 次迭代，递归地产生一个矩阵序列adj(1)，…，adj(k)，…，adj(n)
  3. 其中经过第k次迭代，adj(k)[i，j] 的值等于从结点vi 到结点 vj 路径上所经过的结点序号不大于 k 的最短路径长度

• 动态规划情况分析：由于第 k 次迭代时已求得矩阵 adj(k-1)，那么从结点 vi 到 vj 中间结点的序号不大于 k 的最短路径有两种情况：

  1. 中间不经过结点 vk，那么此时就有adj(k) [i，j] = adj(k-1)[i，j]
  2. 中间经过结点 vk，此时 adj(k) [i，j] < adj(k-1)[i，j]，那么这条由结点 vi 经过 vk 到结点 vj 的中间结点序号不大于k的最短路径由两段组成adj(k) [i，j] = adj(k-1)[i，k] + adj(k-1)[k，j]

• 确定最短路径：

  1. 设置一个n×n的矩阵path，path[i，j]是由顶点vi到顶点vj的最短路径上排在顶点vj前面的那个顶点，即当k是使得adj(k)[i,j]达到最小值，那么就置path[i,j]=path[k,j]
  2. 如果当前没有最短路径时，就将path[i，j]置为-1

• Floyd算法用相邻矩阵adj表表示带权有向图

void Floyd(Graph& G, Dist** &D) 
{
    int i,j,v;
    D = new Dist*[G.VerticesNum()]; // 申请空间
    for (i = 0; i < G.VerticesNum(); i++)
        D[i] = new Dist[G.VerticesNum()];
    for (i = 0; i < G.VerticesNum(); i++) // 初始化数组D
        for (j = 0; j < G.VerticesNum(); j++) 
        {
            if (i == j) 
            {
                D[i][j].length = 0;
                D[i][j].pre = i;
            } 
            else 
            {
                D[i][j].length = INFINITE;
                D[i][j].pre = -1;
            }
        }
    for (v = 0; v < G.VerticesNum(); v++)
        for (Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)) 
        {
            D[v][G.ToVertex(e)].length = G.Weight(e);
            D[v][G.ToVertex(e)].pre = v;
        }
    // 加入新结点后，更新那些变短的路径长度
    for (v = 0; v < G.VerticesNum(); v++)
        for (i = 0; i < G.VerticesNum(); i++)
            for (j = 0; j < G.VerticesNum(); j++)
                if (D[i][j].length > (D[i][v].length+D[v][j].length)) 
                {
                    D[i][j].length = D[i][v].length+D[v][j].length;
                    D[i][j].pre = D[v][j].pre;
                }
}

最小生成树

• 图 G 的生成树是一棵包含 G 的所有顶点的树，树上所有权值总和表示代价，在 G 的所有的生成树中代价最小的生成树称为图 G 的 最小生成树

• 两种生成最小生成树的算法：Prim算法和Kruskal算法都是贪心算法且都用到了最小生成树的MST性质

• 最小支撑树MST性质：对于带权的连通无向图G，其最小支撑树是一个包括G的所有顶点和部分边的图，这部分的边满足下列条件：

  1. 保证图的连通性
  2. 边权值总和最小

• MST性质：设 T(V，E) 是一棵正在构造的生成树。E 中有边 e= (vx，vy)，其中vx∈v，vy不属于V。e 的权 w(e) 是所有一个端点在V* 里，另一端不在V* 里的边的权中最小者。则一定存在 G 的一棵包括 T 的 MST 包括边e= ( vx，vy)

• MST不唯一，但是最小权值是确定的

Prim算法

• Prim算法具体操作：
  1. 从图中任意一个顶点开始，把这个顶点包括在MST里
  2. 然后，在那些其一个端点已在MST里，另一个端点还未在MST里的边中，找权最小的一条边（相同边存在，任选择其一），并把这条边和其不在MST里的那个端点包括进MST里
  3. 如此进行下去，每次往MST里加一个顶点和一条权最小的边，直到把所有的顶点都包括进MST里

• 算法结束时 V* = V , E* 包含了 G 中的 n-1 条边

// Prim算法
void Prim(Graph& G, int s, Edge* &MST) 
{ // s是始点，MST存边
    int MSTtag = 0; // 最小生成树的边计数
    MST = new Edge[G.VerticesNum()-1]; // 为数组MST申请空间
    Dist *D;
    D = new Dist[G. VerticesNum()]; // 为数组D申请空间
    for (int i = 0; i < G.VerticesNum(); i++) 
    { // 初始化Mark和D数组
        G.Mark[i] = UNVISITED;
        D[i].index = i;
        D[i].length = INFINITE;
        D[i].pre = s; // D[i].pre = -1 呢？
    }
    D[s].length = 0;
    G.Mark[s]= VISITED; // 开始顶点标记为VISITED
    int v = s;
    for (i = 0; i < G.VerticesNum()-1; i++) 
    {
// 因为v的加入，需要刷新与v相邻接的顶点的D值
    for (Edge e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e))
        if (G.Mark[G.ToVertex(e)] != VISITED &&(D[G.ToVertex(e)].length > e.weight)) 
        {
            D[G.ToVertex(e)].length = e.weight;
            D[G.ToVertex(e)].pre = v;
        }
    v = minVertex(G, D); // 在D数组中找最小值记为v
    if (v == -1) return; // 非连通，有不可达顶点
    G.Mark[v] = VISITED; // 标记访问过
    Edge edge(D[v].pre, D[v].index, D[v].length); // 保存边
    AddEdgetoMST(edge, MST, MSTtag++); // 将边加入MST
    }
}

// 在 Dist 数组中找最小值
int minVertex(Graph& G, Dist* & D) 
{
    int i, v = -1;
    int MinDist = INFINITY;
    for (i = 0; i < G.VerticesNum(); i++)
        if ((G.Mark[i] == UNVISITED) && (D[i] < MinDist))
        {
            v = i; // 保存当前发现的最小距离顶点
            MinDist = D[i];
        }
    return v;
}

• 时间复杂度：Prim 算法非常类似于 Dijkstra 算法，O(n²)

Kruskal 算法

• Kruskal算法使用贪心准则是从剩下的边中选择不会产生环路且具有最小权值的边加入到生成树中

• Kruskal算法的构造思想：

  1. 首先将 G 中的 n 个顶点看成是独立的 n 个连通分量，这时的状态是有 n 个顶点而无边的森林，可以记为 T = <V，{}>
  2. 然后在 E 中选择代价最小的边，如果该边依附于两个不同的连通分支，那么将这条边加入到 T 中，否则舍去这条边而选择下一条代价最小的边
  3. 依此类推，直到 T 中所有顶点都在同一个连通分量中为止，此时就得到图 G 的一棵最小生成树

• Kruskal算法中，把连通分量重的顶点作为集合元素，采用并查集的Find算法确定边的两个关联顶点所属的连通分支，采用Union算法合并两个连通分量

• Kruskal算法中，需要按照边权值递增的顺序依次查看边，可以把按边的权值组织优先队列。权值约小，优先级越高。用最小堆实现优先队列

// Kruskal算法
void Kruskal(Graph& G, Edge* &MST) 
{ // MST存最小生成树的边
    ParTree<int> A(G.VerticesNum()); // 等价类
    MinHeap<Edge> H(G.EdgesNum()); // 最小堆
    MST = new Edge[G.VerticesNum()-1]; // 为数组MST申请空间
    int MSTtag = 0; // 最小生成树的边计数
    for (int i = 0; i < G.VerticesNum(); i++) // 将所有边插入最小堆H中
        for (Edge e = G. FirstEdge(i); G.IsEdge(e); e = G. NextEdge(e))
            if (G.FromVertex(e) < G.ToVertex(e))// 防重复边
                H.Insert(e);
    int EquNum = G.VerticesNum(); // 开始有n个独立顶点等价类
    while (EquNum > 1) 
    { // 当等价类的个数大于1时合并等价类
        if (H.isEmpty()) 
        {
            cout << "不存在最小生成树." <<endl;
            delete [] MST;
            MST = NULL; // 释放空间
            return;
        }
        Edge e = H.RemoveMin(); // 取权最小的边
        int from = G.FromVertex(e); // 记录该条边的信息
        int to = G.ToVertex(e);
        if (A.Different(from,to)) 
        { // 边e的两个顶点不在一个等价类
            A.Union(from,to); // 合并边的两个顶点所在的等价类
            AddEdgetoMST(e,MST,MSTtag++); // 将边e加到MST
            EquNum--; // 等价类的个数减1
        }
    }
}

• Kruskal算法的时间复杂度是O(eloge)，主要取决于边数，适合于构造稀疏图的最小生成树

---