8.0 graphs

1. 图的定义

1. Graph = (V, E)
   1. V：顶点集，一个非空确定顶点个数的集合
   2. E：边集

1.1 有向图(Directed graph)

1. 如果表示的边的元组是有序的，那么<v1,v2>和<v2,v1>是不同的
2. v1: 有向图边的始点
3. v2: 有向图边的终点

1.2 无向图(Undirected graph)

1. 如果表示边的元组是无序的，那么(v1，v2)和(v2，v1)是相同的边。

1.3 完全图(Complete graph)

1. 完全图(有向完全图):指有向图中每两个顶点都相互指向。

2. 一个有n个节点的有向图，其边的个数必定<= n*(n-1)。如果边的个数= n*(n-1)，则为是一个完全有向图

1. 无向完全图:就是指每两个顶点之间都有一条边。
2. 在一个有n个顶点的无向图中，边的个数 <= n(n-1)/2，如果刚好相等，则被称为完全无向图

1.4 顶点的度数

1. 对于无向图只有度数，而对于有向图不仅仅有入度，还有出度。

2. 顶点v的度数为d_v，TD(V)是顶点v的度数，在有向图中

   1. ID(v)：顶点v的入度是指向顶点v的边的个数
   2. OD(v)：顶点v的出度从v出发的边的个数
   3. TD(v)=ID(v)+OD(v)

   

3. 所有的度数加起来是边的个数的两倍。

1.5 子图

1. 如果图G和图G’，如果V’包含于V，E’包含于E,并且E’中顶点的边也在G’中，那么G’是G的子图

   

1.6 路径(path)

在图 G=(V，E)中，如果每j的边(i_j，i_j+1)在E中，1<= j< k，则顶点序列P=i₁，i₂，…,i_k是i₁到i_k的路径。

1.7 简单路径和环(Simple path and cycle)

1. 简单路径 : 路径除了第一个和最后一个顶点中没有出现相同的顶点
2. 简单回路:起点和终点相同的时候的简单路径

1.8 连通图和连通分量(Connected graph & Connected component)

1. 在无向图中，如果v1到v2之间有一条路径，那么v1和v2是连通的
2. 在无向图中，如果任意两个顶点是连通的，则该图是连通图
3. 极大连通子图:就是结点个数最多的连通的子图
4. 连通分量(Connected component)：若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为连通分量。

1.9 强联通图和强联通分量(Strong connected graph and strongly connected component)

1. 有向图中，对于每对不同的顶点 i 和 j，都包含从 i 到 j 和从 j 到 i 的有向路径，那么该有向图是强连通的。
   1. 简单来说就是既要过的去，也要回得来
2. 强连通分量：若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。

1.10 网络(Network)（加权图）

1. 当权值和代价分配给边时，得到的数据对象称为加权图和加权有向图
2. 网络是用来代指加权连通图和加权连通有向图（weighted connected digraph）

1.11 生成树(Spanning tree)

1. 连通图的生成树是其最小连通子图。n顶点生成树有n-1条边。
   1. 也就是保持联通的最小边数的图

2. ADT

AbstractDataType Graph {
    instances 实例
        a set V of vertices and a set E of edges 顶点集合V 和 边集E
    operations 操作
        Create(n):create an undirected graph with n vertices and no edges 创建一个n个顶点没有边的无向图
        Exist(i,j): return true if edge(i,j)exists; false otherwise 当且仅当存在边i、j的时候返回true
        Edges():return the number of edges in the graph 返回图的边的个数
        Vertices():return the number of vertices in the graph 返回图的顶点个数
        Add(i,j): add the edge(i,j) to the graph 将i、j边添加到图中
        Delete(i,j):delete the edge (i,j) 删除边i、j 
        Degree(i): return the degree of vertex i 返回顶点i的度数
        InDegree(i): synonym for degree 和度数相同
        OutDegree(i): synonym for degree 和度数相同}

3. 图的表示与实现

1. 有向图(graphs)
2. 无向图(digraphs)

3.1 邻接矩阵(Adjacency Matrix)

1. 无向图的邻接矩阵

   1. 无向图的每个顶点的度数等于矩阵中每一行或列的和
   2. 无向图的邻接矩阵是对称的

   

2. 有向图的邻接矩阵

   1. 出度对行求和
   2. 入度对列求和

   

3. 加权图(网络)的邻接矩阵

   1. 注意使用无穷标识的没有通路

   

   

3.1.1 代码

const int MaxNumEdges = 50// 最大边数
const int MaxNumVertices = 10//最大顶点数 
template<class NameType, class DistType> class Graph{
    private:
        SeqList<NameType> VerticesList(MaxNumVertices) //顶点表
        DistType Edge [MaxNumVertices] [MaxNumVertices]  //邻接矩阵，一定是方阵
        int CurrentEdges;//当前边数
        int FindVertex (Seqlist <NameType> &L; const  NameType &Vertex)
            {return L.Find(Vertex);}
        int GetVertexPos (const NameTyoe &Vertex)
            {return FindVertex(VerticesList);}// 给出了顶点Vertex在图中的位置
    public:
        Graph (const int sz=MaxNumEdges); 
        int GraphEmpty() const{return VerticesList.IsEmpty();}
        int GraphFull() const{return VerticesList.IsFull() || CurrentEdges= =MaxNumEdges;}

        int NumberofVertices(){return VerticesList.last;}
        int NumberofEdges() {return CurrentEdges;}
        NameType Getvalue(const int i) {return  i>=0 && i<VerticesList.last ? VerticesList.data[i] :  NULL;} 
        DistType Getweight (const int v1,const int v2);
        
        int GetFirstNeighbor(const int v); 
        int GetNextNeighbor(const int v1,const int v2);
        
        void InsertVertex(const NameType & Vertex);
        void InsertEdge(const int v1,const int v2, DistType weight);
        void removeVertex(const int v);
        void removeEdge(cosnt int v1,const int v2);
} 

template<class NameType, class DistType> Graph<NameType, DistType>::Graph(int sz) {
    for (int i=0;i<sz;i++)
        for (int j=0; j<sz; j++)
            Edge [i][j]=0;
    currentEdge=0;
    //进行图结构的初始化
    //边数组的默认初始化值均为0
}

template<class NameType, class DistType> int Graph<NameType, DistType>::GetFirstNeighbor(int v) {
    if (v!=-1) {
        for(int col=0; col<CurrentVertices; col++)
            if (Edge[v][col]>0 && Edge[v][col]<max)
                return col;
    }
    return -1;
}

3.2 邻接表(Linked-adjacency Lists)

邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对于图的每个顶点建立一个容器（ n 个顶点建立 n 个容器），第 i 个容器中的结点包含顶点 vi 的所有邻接顶点。当无向图中的边的个数比较少的时候，可以降低存储需要的空间的量。

• 通过 head 可以定位到每一类所构成的链表
• 当需要插入新的节点时，可以通过 head 定位到新的数据节点所属类别的表头，然后进行头插

e.g.插入 (1,2),(2,3),(2,5),(3,6),(5,4),(5,1) 六条边后，邻接表的信息如下：

e.g. 无向图：

e.g. 有向图（加权图）：（cost指的是权重）

3.2.1 代码

3.2.1.1 邻接表的声明

//邻接表的声明
const int Defaultsize = 10;
template <class NameType，class DistType> class Graph;
template <class DistType> struct Edge       //边的定义 {
    friend class Graph <NameType,DistType>;//友元函数
    int dest;//边的另一顶点在顶点表中的位置 
    DistType cost;//边上的权
    Edge<DistType> *link;//下一条边的链指针
    Edge() {}
    Edge(int D,DistType C):dest(D),cost(C),link(NULL){}
    int operate != (const Edge<DistType> &E) const {return dest != E.dest; }
}
template<class NameType, class DistType> struct Vertex {
    friend class Edge<DistType>;
    friend class Graph<NameType, DistType>; 
    NameType data;//顶点名字
    Edge<DistType> *adj;//出边表头指针
} 

3.2.1.2 图的类定义

//图的类定义
template<class NameType，class DistType> class Graph {
    private:
        Vertex<NameType, DistType> *NodeTable; //顶点表
        int NumVertices;//当前顶点数
        int MaxNumVertices;//最大顶点个数
        int NumEdges;//当前边数
        int GetVertexpos(const Type &Vertex);
    public:
        Graph(int sz);
        ~Graph();
        int GraphEmpty() const {return NumVertices= =0;}
        int GraphFull() const {return NumVertices= =MaxNumVertices;}
        int NumberOfVertices() {return NumVertices;}
        int NumberOfEdges() {return NumEdges;}
        NameType GetValue(const int i) {return i>=0 && i<NumVertices ? NodeTable[i].data: NULL;}
        void InsertVertex(const NameType &Vertex);
        void RemoveVertex(int v);
        void InsertEdge(int v1,int v2,DistType weight);
        void RemoveEdge(int v1,int v2); 
        DistType Getweight(int v1,int v2); 
        int GetFristNeighbor(int v);
        int GetNextNeighbor(int v1,int v2);
}

3.2.1.3 部分实现的方法

1. 构造方法

   template<class NameType,class DistType> Graph<NameType,DistType>::Graph(int sz=Defaultsize):NumVertices(0),MaxNumVertices(sz),NumEdge(0) {
       int NumVertices, NumEdges, k, j; 
       NameType name,tail,head;
       DistType weight; 
       NodeTable=newVertex<NameType>[MaxNumVertices]
          
       cin >> NumVertices;//输入顶点数
       for( int i=0; i<NumVertices; i++ ) {  
           cin >> name;
           InsertVertex(name);
       }
       cin >> NumEdges;//输入边数
       for( i=0; i<NumEdges; i++) { 
           cin >> tail >> head >> weight; 
           k=GetVertexpos(tail);
           j=GetVertexpos(head);
           InsertEdge(k,j,weight);
       }
   }
   

2. 根据数据值找到下标

   int Graph<NameType,DistType>::GetVertexpos(const NameType &Vertex) {
       for( int i=0; i<NumVertices; i++)
           if (NodeTable[i].data == Vertex)
               return i;
       return –1;
   }
   

3. 给出顶点V的第一个邻接顶点的位置

   template<class NameType,class DistType> int Graph<NameType,DistType>::GetFirstNeighbor(int v) {
       if (v!=-1) {
           Edge<DistType>* p=NodeTable[v].adj; 
           if (p!=NULL) return p->dest;
       }
       return –1;
   }
   

4. 找到下一个邻居

   template<class NameType,class DistType> int Graph<NameType,DistType>::GetNextNeighbor (int v1,int v2) {
       if (v1!=-1) {
           Edge<DistType> *p=NodeTable[v1].adj; 
           while (p!=NULL) {
               if(p->dest==v2 && p->link!=NULL)
                   return p->link->dest;
               else p=p->link;
           }
       }
       return –1;
   }
   

3.3 邻接多重表

3.3.1 无向图

在无向图中, 如果边数为m, 则在邻接表表示中需2m个单位来存储。 为了克服这一缺点, 采用邻接多重表, 每条边用一个结点表示

1. 各首元节点：

   

2. 其他节点结构：

   

   1. mark：标志域，用于标记此节点是否被操作过，例如在对图中顶点做遍历操作时，为了防止多次操作同一节点，mark 域为 0 表示还未被遍历；mark 为 1 表示该节点已被遍历；
   2. ivex 和 jvex：数据域，分别存储图中各边两端的顶点所在数组中的位置下标；
   3. ilink：指针域，指向下一个存储与 ivex 有直接关联顶点的节点；
   4. jlink：指针域，指向下一个存储与 jvex 有直接关联顶点的节点；
   5. info：指针域，用于存储与该顶点有关的其他信息，比如无向网中各边的权；

3.3.2 有向图

对有向图而言，需用邻接表和逆邻接表，如果把这两个表结合起来用有向图的邻接多重表(也称为十字链表)来表示一个有向图.

1. 有几条边，就有几个结点
2. data部分只记录first-in和first-out，也就是第一条出边和第一条入边。
3. v1表示边的起点，v2表示边的终点，p1指向v1作为起点的边，p2指向v2作为终点的边

4.图的遍历和连通性

图的遍历：从图中某一顶点出发访问图中其余顶点,且使每个顶点仅被访问一次

4.1 DFS(depth-first-search,深度优先搜索)

4.1.1 算法思想:

1. 从图中某个顶点V0出发,访问它,然后选择一个 V0邻接到的未被访问的一个邻接点V1出发深度优先遍历图。

2. 当遇到一个所有邻接于它的结点都被访问过了的结点U时,回退到前一次刚被访问过的拥有未被访问的邻接点W,再从W出发深度遍历。

3. 直到连通图中的所有顶点都被访问过为止.

4.1.2 算法实现

递归方法实现 算法中用一个辅助数组visited[]:

1. 0:未访问
2. 1:访问过了
3. 我们假设图为连通图

//利用的是邻接矩阵来表示的图
//主过程:
template<NameType,DistType> void Graph<NameType,DistType>::DFS( ) {
    int *visited=new int[NumVertices];
    for ( int i=0; i<NumVertices; i++)
        visited[i]=0;
        DFS(0,visited);//从顶点0开始深度优先搜索
        delete[] visited;//释放visited的空间
    }
//子过程
template<NameType,DistType> void Graph<NameType,DistType>::DFS(int v, visited[]) {
    cout<<GetValue(v)<<"";
    visited[v]=1;
    int w = GetFirstNeighbor(v);
    while (w!=-1) {
        if(!visited[w])
            DFS(w,visited);//最坏情况，就是每一次w都没有被访问过
        w = GetNextNeighbor(v,w);
    }
    //无论如何，最坏情况下访问次数，也就只能是图中所有边的个数。
    //也就是对邻接矩阵所有边会被扫一遍
}

4.1.3 算法分析

1. 用邻接表表示 O(n+e)
2. 用邻接矩阵表示 O(n²)

4.2 广度优先搜索(Breadth search)

4.2.1 算法思想

1. 从图中某顶点V0出发，在访问了V0之后依次 问v0的各个未曾访问过的邻接点
2. 然后分别从这些邻接点出发广度优先遍历图
3. 直至图中所有顶点都被访问到为止.

4.2.2 算法实现

算法同样需要一个辅助数组visited[] 表示顶点是否被访问过. 还需要一个队列,记正在访问的这一层和上一层的顶点. 算法显然是非递归的。

template<NameType,DistType> void Graph<NameType,DistType>::BFS(int v) {
    //这个算法使用了队列
    int* visited=new int[NumVertices];
    for (int i=0; i<NumVertices; i++)
        visited[i]=0;
    cout << GetValue(v) << "";

    //访问结点
    visited[v]=1;

    //使用队列来存储顶点
    queue<int> q;
    q.EnQueue(v);
    while(!q.IsEmpty()) {
        v= q.DeQueue();
        int w= GetFirstNeighbor(v);
        while (w!=-1) {
            if(!visited[w]) {
                cout<<GetValue(w)<<""; 
                visited[w]=1;
                q.EnQueue(w);
            }
            w= GetNextNeighbor(v,w);
            //访问完成一层的结点
        }
    }
    delete[] visited;
}

4.2.3 算法分析

1. 每个顶点进队列一次且只进一次，∴算法中循环语句至多执行n次。
2. 从具体图的存储结构来看
   1. 如果用邻接表：O(n+e)
   2. 如果用邻接矩阵: 对每个被访问过的顶点，循环检测矩阵中n个元素，∴时间代价为 O(n²)

4.3 非联通的遍历

以上讨论的是对一个无向的连通图或一个强连通图的有向图进行遍历，得到一棵深度优先或广度优先生成树。

但当无向图(以无向图为例)为非连通图时，从图的某一 顶点出发进行遍历(深度，广度)只能访问到该顶点所在的最大连通子图(即连通分量）的所有顶点。

下面是利用深度优先搜索求非连通图的连通分量算法 实际上只要加一个循环语句就行了.

Template<NameType,DistType> void Graph<NameType,DistType> :: components() {  
    int* visited = new int[NumVertices];
    for (int i=0;i<NumVertices;i++)
        visited[i]=0;
    for (i=0; i<NumVertices; i++)
        //只需要对于每一个顶点进行操作即可
        if (!visited[i]) {
            DFS(i,visited);
            outputNewComponent();
        }
        delete[] visited;
}     

5. 最小生成树

5.1 生成树

5.1.1 生成树的定义

1. 设G =(V，E)是一个连通的无向图(或是强连通有向图) 从图G中的任一顶点出发作遍历图的操作，把遍历走过的边的集合记为TE(G)，显然 G‘=(V，TE)是G之子图， G‘被称为G的生成树(spanning tree)，也称为一个连通图。
2. n个结点的生成树有n-1条边。
3. 生成树的代价(cost)：TE(G)上诸边的代价之和
4. 生成树不唯一

5.1.2 最小代价生成树（minimun-cost spanning tree）

各边权的总和为最小的生成树

e.g. 6个城市已固定，现从一个城市发出信息到 每一个城市如何选择或铺设通信线路，使花费（造价）最低。

两个算法：Prim, Kruskal.

算法思想:贪心算法(逐步求解)

5.2 贪心(Grandy)算法

1. Grandy策略：设：连通网络N={V,E}, V中有n个顶点。

   1. 先构造 n 个顶点，0 条边的森林 F ={T0,T1,…..,Tn-1}

   2. 每次向 F 中加入一条边。该边是一端在 F 的某棵树Ti上而另一端不在Ti上的所有边中具有最小权值的边。 这样使F中两棵树合并为一棵，树的棵数 - 1

   3. 重复上述操作n-1次

2. 也就是：去掉所有边，每次加入的边是当前最小的边，并且保证这个边不是回边。

5.2.1 最小生成树的类声明

边结构:tail + head + cost

const int MAXINT = 机器可表示的，问题中不可能出现的大数
class MinSpanTree;
class MSTEdgeNode {
    friend class MinSpanTree;
    private:
        int tail ,head;
        int cost;
};

class MinSpanTree {
    public : MinSpanTree(int SZ = NumVertices-1):
        MaxSize(SZ), n(0){edgevalue = new MSTEdgeNode[MaxSize];} 
    protected:
        MSTEdgeNode* edgevalue;//边值数组
        int MaxSize, n;//数组的最大元素个数和 //当前个数
}；

5.3 Kruskal算法

对边进行排序，然后一个一个生成

1. 把无向图的所有边排序（E是所有边的集合）

   

2. 一开始的最小生成树为（TE是最后生成出的边的集合）：

   

3. 在E中选一条代价最小的边(u,v)加入TE，一定要满足(u,v) 不和TE中已有的边构成回路，从E中删掉(u,v)

   

4. 一直到TE中加满n-1条边为止。

5.3.1 算法实现

1. 图用邻接矩阵表示，edge(边的信息)
2. 图的顶点信息在顶点表 Verticelist中
3. 边的条数为CurrentEdges
4. 取最小的边以及判别是否构成回路，
5. 取最小的边利用:最小堆(MinHeap)

void Graph<string,float>::Kruskal(MinSpanTree&T) {
    //结果赋值给T
    MSTEdgeNode e;
    MinHeap<MSTEdgeNode>H(currentEdges);
    int NumVertices=VerticesList.Last , u , v ;
    Ufsets F(NumVertices);//建立n个单元素的连通分量
    for(u=0;u<NumVertices;u++)
        for (v=u+1;v<NumVertices;v++)
            if(Edge[u][v]!=MAXINT) {
                e.tail=u;
                e.head=v;
                e.cost=Edge[u][v];
                H.insert(e);
                //完成堆的初始化，将每一条边插入到优先级队列中去
            }
    int count=1;//生成树边计数
    while(count<NumVertices) {
        H.RemoveMin(e);
        u=F.Find(e.tail);//找到并查集的树根
        v=F.Find(e.head);//找到并查集的树根
        if(u!=v){
            //并查集做回边检测，在同一个并查集中就是一个回边，不然就不是
            F.union(u,v);
            T.Insert(e);
            count++;//计数已经查找出来的个数
        }
        //最坏的情况时所有的边都被访问一次，比如目标边是最后一条边。
    }
}

public void kruskal() {
    int edgesAccepted;
    DisjSet s;
    priorityQueue h;
    Vertex u, v;
    SetType uset, vset;
    Edge e;
    h = readGraphIntoHeapArray( );
    h.buildHeap() ;
    s = new DisjSet( NUM_VERTICES );

    edgesAccepted = 0 ;
    while( edgesAccepted < NUM_VERTICES – 1 ){
        e = h.deleteMin() ;//Edge e = (u, v)
        uset = s. find(u);
        vset = s.find(v);
        if( uset != vset ) {
            edgesAccepted++;
            s.union( uset, vset );
        }
    }
}

5.3.2 算法分析

1. 建立e条边的最小堆
   1. 检测邻接矩阵O(n²)
   2. 每插入一条边，执行一次 fiterup() 算法：log₂e 所以，总的建堆时间为O(elog₂e)
2. 构造最小生成树时
   1. e次出堆操作：每一次出堆，执行一次filterdown(), 总时间为O(elog2e)
      • 没有考虑悬挂问题
   2. 2e次find操作：O(elog₂n)，树高是log2n
      • 从头开始生成，两个高为1的树，做union，才有高度为2的树
      • 两个高为2的树，做union，才有高度为3的树
      • 树的高度最坏情况下是log₂n，当切仅当第一个二叉树
   3. n-1次union操作：O(n)
   4. 所以，总的计算时间为O(elog₂e+elog₂n+n²+n)

5.4 Prim算法

结合顶点，考虑所有可达的边的权重大小

1. 设：原图的顶点集合V(有n个)生成树的顶点集合U(最后也有n个)，一开始为空TE集合为{}
2. 步骤：
   1. U={1}任何起始顶点，TE={}
   2. 每次生成(选择)一条边。这条边是所有边(u,v) 中代价(权)最小的边， u∈U,v∈V-U TE=TE+[(u,v)]; U=U+[v]。）把E中以U中的点为顶点的边，且这条边不在TE中，则在E中删掉这条边）
   3. 当U≠V，返回步骤2
3. 对于一般的图来讲，最小生成树不唯一。
4. 所以相应的Prim算法和Kruskal算法也会出现多解的情况。

5.4.1 示例

5.4.2 算法分析

1. 第一次的时候u只有1个元素，而第二次则有2个，以此类推。
2. 使用邻接矩阵实现的图，可以把时间复杂度降低到O(n²)

5.5 Prim算法实现

1. 使用两个数组Lowcost[ ]、nearvex[ ]
2. Lowcost[]:存放生成树顶点集合内顶点到生成树外各顶点的边上的当前最小权值
3. nearvex[]:记录生成树顶点集合外各顶点，距离集合内那个顶点最近。

算法过程：

1. 在Lowcost[ ]中选择nearvex[i]不等于-1,且lowcost[i] 最小的边用v标记它。

   则选中的权值最小的边为(nearvex[v],v), 相应的权值为lowcost[v]。

   例如在下图中第一次选中的v=5;则边(0，5)，是选中的权值最小的边，相应的权值为lowcost[5]=10。 反复做以下工作

2. 将nearvex[v] 改为-1，表示它已加入生成树顶点集合。将边(nearvex[v],v,lowcost[v])加入生成树的边集合。

3. 修改。

   取lowcost[i]=min{lowcost[i],Edge[v,i]}

   即用生成树顶点集合外各顶点i到刚加入该集合的新顶点 v的距离(Edge[v,i])与原来它所到生成树顶点集合中顶点的最短距离lowcost[i]做比较，取距离近的，作为这些集合外顶点到生成树顶点集合内顶点的最短距离。

4. 如果生成树顶点集合外的顶点i到刚加入该集合新顶点v的距离比原来它 到生成树顶点集合中顶点的最短距离还要近，则修改nearvex[i]: nearvex[i]=v

   表示生成树外顶点i到生成树的内顶点v当前距离最短。

5.5.1 示例

5.5.2 算法实现

void graph<string,float>::Prim(MinSpanTree&T){
    int NumVertices=VerticesList.last; 
    float*lowcost=new float[NumVertices]; 
    int * nearvex=new int[NumVertices];
    for (int i=1;i< NumVertices;i++) {
        lowcost[i] = Edge[0][i];//0到其他所有边的权值
        nearvex[i]=0;
    }
    nearvex[0]=-1;
    
    MSTEdgeNode e;
    for (int i=1; i< NumVertices; i++) {
        //for i 循环完，整个算法也就结束了
        float min=MAXINT;
        int v=0;
        for ( int j=1; j< NumVertices; j++){
            //for j,  选择最小的边
            if(nearvex[j]!=-1&&lowcost[j]<min) {
                v=j;
                min=lowcost[j];
            }
        }


        if(v) {
            e.tail=nearvex[v];
            e.head=v;
            e.cost=lowcost[v];
            T.Insert(e);
            //添加边进入最小生成树中去
            nearvex[v]=-1;
            
            //更新lowcost和nearvex
            for(int j=1; j< NumVertices; j++)
                if( nearvex[j]!=-1 && Edge[v][j]<lowcost[j] ) {
                    lowcost[j]=Edge[v][j];
                    nearvex[j]=v;
                }
        } //if
    } //for i
}

5.5.3 算法分析

1. 第一个for循环的复杂度是O(n)的
2. 第二个嵌套的for循环的复杂度是O(n²)的

6. 最短算法

1. 设G=(V,E)是一个带权图(有向，无向)，如果从顶点v到顶点w的一条路径为(v,v1,v2,…,w)，其路径长度不大于从v到w的所有其它路径的长度，则该路径为从 v 到 w 的最短路径。
2. 背景:在交通网络中，求各城镇间的最短路径。
3. 三种算法:
   1. 边上权值为非负情况的从一个结点到其它各结点的最短路径 (单源最短路径)(Dijkstra算法)
   2. 边上权值为任意值的单源最短路径
   3. 边上权值为非负情况的所有顶点之间的最短路径

6.1 Dijkstra算法

求含非负权值的单源最短路径

问题：

6.1.1 贪心算法

1. 起点V0，首先看和所有结点的直接连接。

   

2. 排好序后，V0-V1 10已经是最小的了，必然不可能再找到更短的路径

   

3. V0-V1 10选择好（红色）

   尝试V0-v2通过V1绕会不会比原来的更短(考虑V1-V2直连)，V0-V4从V1绕会不会比原来更短(考虑V2-V3直连)，如果短则更新

   此时V0-V3是三者中最小值，所以选择V0-V3

   

4. V0-V3 30选择好（红色）

   尝试通过V3绕行V2，计算直连，更新掉，然后重复

   

5. 

6.1.2 思想

按最短路径长度递增的次序产生最短路径。

一开始，在源点到直接有连线的诸顶点的 path中找最小的，去掉该点，然后找从源点到余下点中最短的path (这里可以不是直接连线，可以是经过前面已找到的最短path的顶点）

6.1.3 代码实现

const int NumVertices = 6;//大于所有边的权重的值
class graph {
    private:
        int Edge[NumVertices][NumVertices]; 
        int dist[NumVertices];
        int path[NumVertices];
        int S[NumVertices];
    public:
        void shortestpath(int,int);
};
void Graph::shortestpath(int n,int v) {  
    for( int i=0; i<n; i++) {
        //v为当前节点，dist数组是表示距离的数组
        //遍历n次
        
        //初始化
        dist[i] = Edge[v][i];
        s[i] = 0;
        
        if( i!=v && dist[i]< MAXNUM )
            path[i]= v;//如果可达，则用path数组记录下路径
        else
            path[i]=-1;//如果不可达，则用path数组记录下不可达(-1)
        }
    
        s[v]=1;
        dist[v]=0;
        //表示访问过当前节点，并且距离为0
        for( i=0; i<n-1; i++) {
            float min=MAXNUM;
            int u = v;
            for( int j = 0;  j < n;  j++)
                if( !s[j] && dist[j]<min ) {
                    //如果结点j还没有访问过，并且dist[j]小于最小值
                    u = j;
                    min = dist[j];
                }
            s[u]=1;
            for ( int w=0; w<n; w++)
                if( !s[w] && Edge[u][w] < MAXNUM && dist[u]+Edge[u][w] < dist[w]) {
                    //dist[u]就是起点到u的距离，下面是关键条件
                    dist[w]=dist[u]+Edge[u][w];
                    path[w]=u;
                }
        }//for
}   

6.1.4 算法分析

6.2 贝尔曼——福特改进算法

1. 边上权值为任意值的单源最短路径(贝尔曼—福特) dijkstra算法在边上权值为任意值的图上是不能正常工作的。

   

2. 构造一个最短路径长度数组

   dist¹[u],dist²[u],…dist^n-1[u]

   • dist¹[u]:是从源点v到终点u的只经过一条边的最短路径长度
   • dist¹[u]=Edge(v,u)
   • dist²[u]:是从源点v最多经过两条边到达终点u的最短路径长度；
   • dist³[u]： 是从源点v最多经过不构成带负长度边回路的三条边 的最短路径长度；
   • …
   • dist^n-1[u]：是从源点v最多经过不构成带负长度边回路的n-1条边的最短路径长度；

3. 不允许带负权值的边组成回路

6.2.1 递推公式

1. dist¹[u]=Edge(v,u);

2. dist^k[u]=min{dist^k-1 [u],min{dist^k-1[j]+Edge(j,u)} } （j=0,1,2,…,n-1）

   

3. 更新的时候都是根据前面结果，遍历计算存储

4. 所有第k步，只受第k-1步的影响

#### 6.2.2 代码实现

   void  Graph::BellmanFord(int n, int v) {
       //动态规划
       for(int i=0;i<n;i++) {
           //初始化dist距离数组
           dist[i]=Edge[v][i];
           if(i!=v && dist[i]<MAXNUM) path[i]=v;
           //初始化路径数组 
           else path[i]=-1; }
       
       for (int k = 2;k < n;k++)
           for(int u = 0;u < n;u++)
               if(u!=v)
                   for(i=0;i < n;i++)
                       //一直算到n-1步
                       if (Edge[i][u]>0 && Edge[i][u]<MAXNUM && dist[u]> dist[i]+Edge[i][u]){
                           dist[u]=dist[i]+Edge[i][u];
                           path[u]=i;
                       }
   }

时间复杂度:O(n³)

6.3 floyed算法

1. 前提：各边权值均大于0的带权有向图。
   1. 每个顶点到自己的代价为0
2. 方法：
   1. 把有向图的每一个顶点作为源点，重复执行Dijkstra算法n次，执行时间为O(n3)
   2. Floyed方法，算法形式更简单些，但是时间仍然是O(n3)

6.3.1 示例

在矩阵A上作n-1次迭代，设每次迭代结果分别为 A⁽⁰⁾,A⁽¹⁾,A⁽²⁾,…A⁽ⁿ⁾

注意：vi-v1-v2-vj 和 vi-v2-v1-vj 其实是不会同时考虑的，要么只存在一个，要么两个相等。

简单来说就是:每次都会选择一个中介点，然后遍历整个数组，更新相应的需要更新的数组。

6.3.2 代码实现

void Graph::Alllength(int n) {
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) {
            a[i][j]=Edge[i][j];
            if(i!=j&&a[i][j]<MAXNUM) path[i][j] = i;
            else path[i][j]=0;
            }
    for(int k=0; k<n; k++)
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if( a[i][k]+a[k][j]<a[i][j] ) {
                    a[i][j]=a[i][k]+a[k][j];
                    path[i][j]=path[k][j];
                }
}

算法复杂度:O(n³)

6.3.3 参考

最短路径问题—Floyd算法详解-CSDN博客

Floyd算法详解 通俗易懂 - 知乎 (zhihu.com)

7. 活动网络(Activity Network)（图的应用）

1. 用顶点表示活动的网络(AOV网络)
2. 用边表示活动的网络(AOE网络)

7.1 AOV网络

7.1.1 AOV网络结构

1. 图中顶点表示课程(活动)，有向边(弧)表示先决条件。 若课程i是课程j的预修课程，则图中有弧<i,j>
2. AOV网(Activity On Vertex network)
   • 用顶点表示活动，用弧表示活动间的优先关系的有向图称为AOV网。
3. 直接前驱，直接后继
   • <i,j>是网中一条弧，则i是j的直接前驱，j是i的直接后继。
4. 前驱，后继
   • 从顶点i->顶点j有一条有向路径，则称i是j的前驱，j是i的后继。
5. AOV网中，不应该出现有向环

7.1.2 AOV图的拓扑排序

1. 有向图G=(V,E),V里结点的线性序列(vi1,vi2,…,vin), 如果满足: 在G中从结点 vi 到 vj 有一条路径，则序列中结点 Vi 必先于结点 vj ，称这样的线性序列为一拓扑序列。
2. 不是任何有向图的结点都可以排成拓扑序列，有环图是显然没有拓扑排序的。

7.1.3 拓扑算法思想

1. 从图中选择一个入度为0的结点输出之。(如果一个图中，同时存在多个入度为0的结点，则随便输出任意一个结点)
2. 从图中删掉此结点及其所有的出边
3. 反复执行以上步骤
   1. 直到所有结点都输出了，则算法结束
   2. 如果图中还有结点，但入度不为0，则说明有环路

7.1.4 拓扑算法实现

1. 具体实现算法：AOV网用邻接表来实现，数组count存放各顶点的入度
2. 为了避免每次从头到尾查找入度为0的顶点，建立入度为0的顶点栈，栈顶指针为top，初始化时为-1.

1. //AOV网的声明
   class Graph {
       friend class <int,float> vertex;
       friend class <float> Edge;
       private:
           vertex <int, float>* nodeTable ; 
           int* count ;
           int n ;
       public:
           Graph ( const int vertices=0): n (vertices) {
               NodeTable=new vertex <int, float> [n];
               count=new int[n];
           }
           void topologicalorder() ;
   };
   //拓扑排序
   void Graph :: Topologicalsort () {
       int top=-1;
       //初始化无入度顶点
       for ( int i=0; i<n ;i++ )
           if (count[i]==0){
               count[i]= top ;
               top = i;
           }
       //进行正式排序
       for (int i=0 ; i<n ; i++)
           if (top == -1){
               //如果top变为-1，那么显然存在回路
               cout <<"Network has a cycle"<< endl;
               return;
           }else{
               int j = top;
               top = count[top];
               cout<<j<<endl;
               Edge<float>* l = NodeTable[j].adj;
               while(l) {
                   int k = l.dest;
                   if ( --connt[k] == 0)
                       //如果完成所有节点的删除
                       count[k] = top;
                       top = k;
               } 
               l = l->link;
           }
       }
   } 
   

   注意：在这里利用了count[]数组，让入度为0的count[]变为下一个入度为0的结点的count[]下标。

2. void topsort() throws CycleFound {
       Queue q;//队列或者栈都可以
       int counter = 0;
       Vertex v, w;
       q = new Queue();
       for each vertex v
           if( v.indegree == 0 )
               q.enqueue(v);
       while(!q.isEmpty()) {
           v = q.dequeue();
           v.topNum = ++counter;//Assign next number 
           for each w adjacent to v
               if( --w.indegree == 0 ) 
                   q.enqueue;
       }
       if( counter != NUM_VERTICES )
           throw new CycleFound();
   } 
   

7.1.5 算法分析

1. 算法分析：n个顶点，e条边
2. 建立链式栈O(n)，每个结点输出一次，每条边被检查一次O(n＋e)，所以为:O(n＋n＋e)

7.2 AOE网络

1. 用边表示活动的网络(AOE网络, Activity On Edge Network)又称为事件顶点网络
2. 顶点：
   • 表示事件(event)
   • 事件——状态。表示它的入边代表的活动已完成，它的出边代表的活动可以开始，如下图v0表示整个工程开始，v4表示a4，a5活动已完成a7，a8活动可开始。
3. 有向边：
   • 表示活动。
   • 边上的权——表示完成一项活动需要的时间

7.2.1 关键路径

1. 目的: 利用事件顶点网络，研究完成整个工程需要多少时间。加快那些活动的速度后，可使整个工程提前完成。（因为可以同时走很多条路，所以最长的一条路决定了整个工程需要的总时间）
2. 关键路径：具有从开始顶点(源点)->完成顶点(汇点)的最长的路径

7.2.2 定义

1. 对于事件:

   1. Ve[i]－表示事件Vi的可能最早发生时间:定义为从源点V0->Vi的最长路径长度, 如Ve[4]=7天

   2. Vl[i]－表示事件Vi的允许的最晚发生时间:是在保证汇点 Vn-1 在Ve[n-1]时刻(18)完成的前提下，事件Vi允许发生的最晚时间＝ Ve[n-1]－ Vi->Vn－1的最长路径长度。是从最后汇点时间长度-两者之间最长路径（再晚做就完不成了）

      1. 最早7：在这之前还没准备好做

      2. 最晚13：再不做来不及完成

2. 对于活动：

   1. e[k]－表示活动ak=<Vi,Vj>的可能的最早开始时间。 即等于事件Vi的可能最早发生时间。 e[k]=Ve[i]
   2. l[k]－表示活动ak= <Vi,Vj> 的允许的最迟开始时间 l[k]＝Vl[j]-dur(<i,j>);
   3. l[k]-e[k]－表示活动ak的最早可能开始时间和最迟允许开始时间的时间余量。也称为松弛时间。 (slack time)
   4. l[k]==e[k]－表示活动ak是没有时间余量的关键活动

   一开始的例子中

   1. a8的最早可能开始时间e[8]=Ve[4]=7
   2. 最迟允许开始时间l[8]=Vl[7]-dur(<4,7>) =14-7=7,所以a8是关键路径上的关键活动
   3. a9的最早可能开始时间e[9]=Ve[5]=7
   4. 最迟允许开始时间l[9]=Vl[7]-dur(<5,7>) =14-4=10
   5. 所以l[9]-e[9]=3, 该活动的时间余量为3，即推迟3完成不影响整个工程的完成，它不是关键活动

7.2.3 寻找关键路径的算法

1. 求各事件的可能最早发生时间

   从Ve[0]=0开始，向前推进求其它事件的Ve Ve[i]=max{Ve[j]+dur(< Vj,Vi >)}, <Vj,Vi>属于S2, i=1,2,…n－1

   j S2是所有指向顶点Vi的有向边< Vj,Vi >的集合

2. 求各事件的允许最晚发生时间

   从Vl[n-1]=Ve[n-1]开始，反向递推 Vl[i]=min{Vl[j]-dur (<Vi,Vj>)}, <Vi,Vj>属于S1, i=n-2,n-3,…0 j S1是所有从顶点Vi出发的有向边< Vi,Vj >的集合

3. 以上的计算必须在拓扑有序及逆拓扑有序的前提下进行，求Ve[i]必须使Vi的所有前驱结点的Ve都能求，求Vl[i]必须使Vi的所有后继结点最晚发生时间都能求。

4. 求每条边(活动)ak= <Vi,Vj> 的e[k], l[k]

   e[k]=Ve[i];

   l[k]=Vl[j]-dur(<Vi,Vj> ),k=1,2,…e

5. 如果e[k]==l[k]，则ak是关键活动

7.2.4 代码实现

AOE网用邻接表来表示，并且假设顶点序列已按拓扑有序与逆拓扑有序排好。如上例:

• 先正向推，然后反向推回来。(分别计算最早时间和最晚时间)

void Graph ::CriticalPath () {
    int i , j ;
    int p, k ;
    float e, l ;
    float * Ve=new float[n];
    float * Vl=new float[n];
    //初始化Ve数组
    for (i=0; i<n ; i++)
        Ve[i]=0;
    //开始正向拓扑计算，计算ve[]
    for (i=0; i<n ; i++) {
        Edge <float> * p=NodeTable[i].adj; 
        while (p!=NULL) {
            k = p.dest;
            if (Ve[i]+p. cost > Ve[k])
                Ve[k]=Ve[i]+p.cost ;
                p=p.link;
        }
    } 
    //反向Ve数组，初始化Vl数组
    for (i=0; i<n ; i++)
        Vl[i]=Ve[n-1];
    //反向计算事件最迟开始时间，计算vl[]
    for (i=n-2; i ; i--) {
        p=NodeTable[i].adj;
        while(p!=NULL) {
            k=p. dest;
            if (Vl[k]-p.cost<Vl[i])
                Vl[i]=Vl[k]-p.cost ; 
                p=p. link;
        }
    } 
    //用来比较最早开始时间和最晚开始时间，确定是否是关键路径
    for (i=0; i<n ;i++) {
        p=NodeTable[i].adj;
        while (p!=NULL) {
            k= p. dest;
            e=Ve[i];
            l=Vl[k]-p. cost;
        if(l==e)
            cout<<"<"<<i<<","<<k<<">"<<"is critical Activity"<<endl;
            p=p.link;
        }
    } 
}

7.2.5 算法分析