部分图算法学习

Graphs

1. 图的定义

1. Graph = (V, E)
   1. V: nonempty finite vertice set(顶点集) 一个非空确定顶点个数的集合
   2. E: edge set(边集)

1.1. 有向图

1. If the tuple denoting an edge is ordered, then <v1,v2> and <v2,v1> are different edges. (如果表示的边的元组是有序的，也就是<v1,v2>和<v2,v1>是不同的)
2. v1: 有向图边的始点
3. v2: 有向图边的终点

img

1. In a directed graph with n nodes, the number of edges <=n*(n-1). If “=” is satisfied, then it is called a complete directed graph.(一个有n个节点的有向图，其边的个数<= n*(n-1)，如果相等，则为是一个完全有向图)
2. 完全图(有向完全图):指有向图中每两个顶点都相互指向。

1.2. 无向图

1. If the tuple denoting an edge is unordered, then (v1,v2) and (v2,v1) are the same edge.(如果表示边的元组是无序的，则(v1，v2)和(v2，v1)是相同的边。)
2. In an undirected graph with n nodes, the number of edges <= n*(n-1)/2. If “=” is satisfied, then it is called a complete undirect graph.(在一个有n个顶点的无向图中，边的个数 <= n(n-1)/2，如果刚好相等，则被称为完全无向图)
3. 完全图(无向完全图):就是指每两个顶点之间都有一条边。

img

1.3. 其他图

1. 以下两种图在我们的数据结构中不进行讨论

img

1. 不考虑 自环(ring) 和 多重边 的多重图。
2. 完全图分为有向和无向

1.4. 顶点的度数

1. 对于无向图只有度数，而对于有向图不仅仅有入度，还有出度。
2. degree dv of vertex v, TD(v): is the number of edges incident on vertex v. In a directed graph :(顶点v的度数为dv，TD(V)是顶点v的度数，在有向图中)
   1. in-degree of vertex v is the number of edges incident to v, ID(v).(顶点v的入度是指向顶点v的边的个数)
   2. out-degree of vertex v is the number of edges incident from the v, OD(v). (顶点v的出度从v出发的边的个数)
3. 性质:(度数)TD(v)=ID(v)+OD(v)（total degree）

img

1.5. 图的性质

img

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

1.6. 子图

1. Graph G=(V,E),G’=(V‘,E‘), if V’包含于V, E’包含于E, and the vertices incident on the edges in E’ are in V’, then G’ is the subgraph of G. For example: 如果图G和图G’，如果V’包含于V，E’包含于E,并且E’中顶点的边也在G’中，那么G’是G的子图

img

1.7. 路径(path)

1. A sequence of vertices P=i1,i2,……ik is an i1 to ik path in the graph of graph G=(V,E) iff the edge(ij,ij+1)is in E for every j, 1 <= j < k.

​ (在图 G=(V，E)中，如果每j的边(ij，ij+1)在E中，1<= j< k，则顶点序列P=i1，i2，…,ik是i1到ik的路径。)

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

1. A Simple path is a path in which all vertices except possibly the first and last , are different.(简单路径 : 路径除了第一个和最后一个顶点中没有出现相同的顶点)
2. A Simple cycle is a simple path with the same start and end vertex.(简单回路:起点和终点相同的时候的简单路径)

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

1. In a undirected graph, if there is a path from vertex v1 to v2, then v1 and v2 are connected.(在无向图中，如果v1到v2之间有一条路径，那么v1和v2是连通的)
2. In a undirected graph ,if two arbitrary vertices are connected, then the graph is a connected graph(在无向图中，如果任意两个顶点是连通的，则该图是连通图)

img

1. 极大连通子图Maximum connected subgraph就是结点个数最多的连通的子图。

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

1. A digraph is strongly connected iff it contains a directed path from i to j and from j to i for every pair of distinct vertices i and j.

   1. (有向图是强连通的，当它包含从 i 到 j 和从 j 到 i 的有向路径时，对于每对不同的顶点 i 和 j)。
   2. 简单来说就是既要过的去，也要回得来

2. The maximum strong connected subgraph (极大强连通子图) of a non-strongly connected graph is called strongly connected conponent (强连通分量).

   1. (一个非强连通图的最大强连通子图(South-South-PosialSuth-Posiple Fug)称为强连通分量).

1.11. 加权图(Network)

1. When weights and costs are assigned to edges, the resulting data object is called weighted graph and weighted digraph.(当权值和代价分配给边时，得到的数据对象称为加权图和加权有向图。)
2. The term network refers to weighted connected graph and weighted connected digraph. (网络是用来代指加权连通图和加权连通有向图)

img

1.12. 生成树(Spanning tree)

1. A spanning tree of a connected graph is its minimum connected subgraph(最小连通子图). An n-vertex spanning tree has n-1 edges. (

   连通图的生成树是其最小连通子图。n顶点生成树有n-1条边。

   )

   • 保持联通的最小边数的图

img

2. ADT Graph and Digraph 无向图和无向图的抽象逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13

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. 图的表示与实现(Representation of graphs and digraphs)

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

3.1. 邻接矩阵(Adjacency Matrix)

img

1. 无向图的邻接矩阵
2. 无向图的每个顶点的度数等于矩阵中每一行的和。

img

1. 有向图的邻接矩阵
   • 出度对行求和
   • 入度对列求和

img

1. 加权图(网络)的邻接矩阵
   • 注意使用的无穷标识没有通路

img
img

1. 当节点数很大，边很少的时候不适用于邻接矩阵。

3.1.1. 邻接矩阵性质

img

1. 无向图的邻接矩阵是对称的。

3.2. 其他需要的结构

1. 一个记录各顶点信息的表
2. 一个当前的边数

3.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
29

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);
} 

3.3.1. 需要实现的方法

1. 构造方法

1
2
3
4
5
6
7
8

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
}

1. 求顶点V的第一个邻接顶点的位置

1
2
3
4
5
6
7
8

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.4. 邻接表实现

1. reduce the storage requirement if the number of edges in the graph is small.当无向图中的边的个数比较少的时候，降低存储需要的空间的量

img

1. Eg.无向图的例子
   • cost是指权重

img

3.4.1. 邻接表的声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//邻接表的声明
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;//出边表头指针
} 

img

3.4.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

//图的类定义
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.4.3. 部分实现的方法

1. 构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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);
    }
}

1. 根据数据值找到下标

1
2
3
4
5
6

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

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

1
2
3
4
5
6
7

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;
}

1. 找到下一个邻居

1
2
3
4
5
6
7
8
9
10
11

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.5. 邻接多重表

1. 在无向图中, 如果边数为m, 则在邻接表表示中需2m个单位来存储. 为了克服这一缺点, 采用邻接多重表, 每条边用一个结点表示.
   • 其中的两个结点号就是边的两个点。
   • data部分只记录first-out
   • path1指向的就是同样始点(vertex1)，顺序终点的结果。
   • path2执行的是以vertex2为始点顺序向下的。
2. Eg.使用正常的邻接表，则右边应该有10个点，但是多种表就是只有5个表
   • 默认情况下边的始点的编号要小于终点的编号大小。

img

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

img

1. 邻接表和邻接多重表之间的区别在于有几个顶点，有几个边。
2. data部分只记录first-in和first-out，也就是第一条出边和第一条入边。

4. 图的遍历和连通性

1. 图的遍历 (Graph Traversal): 从图中某一顶点出发访问图中其余顶点,且使每个顶点仅被访问一次.

img

1. 树的遍历，左子女右兄弟。

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

4.1.1. 算法思想

1. 从图中某个顶点V0出发,访问它,然后选择一个
   V0邻接到的未被访问的一个邻接点V1出发深度优先遍
   历图,当遇到一个所有邻接于它的结点都被访问过了的
   结点U时,回退到前一次刚被访问过的拥有未被访问的
   邻接点W,再从W出发深度遍历,……直到连通图中的所
   有顶点都被访问过为止.

img

1. 递归方法实现 算法中用一个辅助数组visited[]:
   1. 0:未访问
   2. 1:访问过了
   3. 我们假设图为连通图

4.1.2. 算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//利用的是邻接矩阵来表示的图
//主过程:
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^2)

4.2. 广度优先搜索(Breadth search)

4.2.1. 思想

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

img

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

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<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.2. 算法分析

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

4.3. 连通分量

1. 以上讨论的是对一个无向的连通图或一个强连通图的有向图进行遍历，得到一棵深度优先或广度优先生成树.但当无向图(以无向图为例)为非连通图时，从图的某一
   顶点出发进行遍历(深度，广度)只能访问到该顶点所在的最大连通子图(即连通分量)的所有顶点.
2. 下面是利用深度优先搜索求非连通图的连通分量算法 实际上只要加一个循环语句就行了.

1
2
3
4
5
6
7
8
9
10
11
12

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. 生成树不唯一

img

5.1.2. 最小代价生成树

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

5.2. 贪心(Grandy)求解最小代价生成树

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

img

img

1. 两个算法：Prim, Kruskal.
2. 算法思想:贪心算法(逐步求解)

5.2.1. 贪心策略的具体内容

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.2. 最小生成树的类声明

1
2
3
4
5
6
7
8

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

1. 边结构:tail + head + cost

1
2
3
4
5
6
7

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. 把无向图的所有边排序

img

1. 一开始的最小生成树为

img

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

img

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

img

5.3.1. 代码实现

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

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++;//计数已经查找出来的个数
        }
        //最坏的情况时所有的边都被访问一次，比如目标边是最后一条边。
    }
}
// 以下为java代码
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(n2)
   2. 每插入一条边，执行一次 fiterup() 算法：log2e 所以，总的建堆时间为O(elog2e)

2. 构造最小生成树时

   1. e次出堆操作：每一次出堆，执行一次filterdown(), 总时间为O(elog2e)

      • 没有考虑悬挂问题

   2. 2e次find操作：O(elog2n)，树高是log2n

      • 从头开始生成，两个高为1的树，做union，才有高度为2的树
      • 两个高为2的树，做union，才有高度为3的树
      • 树的高度最坏情况下是log2n，当切仅当第一个二叉树

   3. n-1次union操作：O(n)

   4. 所以，总的计算时间为O(elog2e+elog2n+n2+n)

5.4. 物理实现

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

5.5. 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]
   3. 当U≠V，返回上面一个步骤

5.5.1. 例子

img
img

1. 一开始只考虑从1号顶点到其他顶点之间的边。
   • 泛泛而言，考虑u和v之间的边

img
img

5.5.2. 最小生成树不唯一

1. 对于一般的图来讲，最小生成树不唯一。
2. 所以相应的Prime算法和Kruskal算法也会出现多解得 情况。

5.5.3. 算法分析

img

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

5.6. Prim算法优化

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

img

1. 拿u为1364为例，将2拉入u之后，如果1364到5的最小值小于2到5之间的距离，则抛弃25边，否则更新数组。
   img
2. 对于nearvex:记录的结点，lowcost对应记录的是相应边的权重(按照上面的序号)
   • 更新最小边:发生在加入新的结点的时候，需要在nearvex中更新对应位置的最小边。

img

5.6.1. 算法实现

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.6.2. 示例

img

1. 4->5 25<正无穷，更新
   • nearvex更新顶点，lowcost更新权值

img

1. 考虑1->4、2->4等等

img

img

img

img

5.6.3. Prim算法实现

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

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++) {
        float min=MAXINT;
        int v=0;
        for ( int j=1; j< NumVertices; j++)
            if(nearvex[j]!=-1&&lowcost[j]<min) {
                v=j;
                min=lowcost[j];
            } //for j,  选择最小的边

        if(v) {
            e.tail=nearvex[v];
            e.head=v;
            e.cost=lowcost[v];
            T.Insert(e);
            //添加边进入最小生成树中去
            nearvex[v]=-1;
            
            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.6.4. 估计算法复杂度

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

6. 最短路径

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

6.1. 含非负权值的单源最短路径(Dijkstra)

1. 问题

img

6.1.1. 贪心思想

1. 起点V0，首先直接连接，不管是否直接连接。

img

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

1. 接下来，尝试V0-v2通过V1绕会不会比原来的更短(考虑V1-V2直连)，V0-V4从V1绕会不会比原来更短(考虑V2-V3直连)，如果短则更新，此时V0-V3是三者中最小值，所以选择V0-V3。

img

1. 尝试绕行V3，计算直连，更新掉，然后重复

img

1. 红色是已经选择好的，绿色是绕行选择。

img

1. 进一步思考，就是只进行一步，不进行多不步。
2. 总体来讲:不可能走更长的路径，然后回来

img
img

1. 数值更新，路径数组对应位置更新

img

6.1.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
37
38
39
40
41
42

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.3. 算法复杂度分析

img

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

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

2. dist

   1

   [u],dist

   2

   [u],…dist

   n-1

   [u]

   • dist1[u]:是从源点v到终点u的只经过一条边的 的最短路径长度
   • dist1[u]=Edge[v][u]
   • dist2[u]:是从源点v最多经过两条边到达终点u 的最短路径长度；

3. 不允许出现负值回路出现

4. 递推公式:

   1. dist1[u]=Edge[v][u];
   2. distk[u]=min{distk-1 [u],min{distk-1[j]+Edge[j][u]}} j=0,1,2,…,n-1

img

1. 更新的时候都是根据前面结果，遍历计算存储
2. 所有第k步，只受第k-1步的影响

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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;
                    }
}

1. 时间复杂度:O(n3)

6.3. floyed算法

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

img
img
img

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

6.3.1. floyed算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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];
                }
}

1. 算法复杂度:O(n3)
2. 参考:Floyed算法

6.4. Floyed算法参考

1. 最短路径问题

7. 活动网络(图的应用)

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

7.1. AOV网络

img

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.

img

img

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

//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;
        	}
        }
    }
} 

1. java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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. 有向边：

   • 表示活动。 边上的权——表示完成一项活动需要的时间

img
img

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的最长路径长度。是从最后汇点时间长度-两者之间最长路径

img

1. 解释:
   1. 计算到最后汇点的总共最短时间:找到从源点到汇点的最大路径
   2. 最早12，因为之前不能做。
   3. 最晚12，是因为如果这时候不开始，最后完成不了。
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是没有时间余量的关键活动
3. 一开始的例子中
   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
4. 所以l[9]-e[9]=3, 该活动的时间余量为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是关键活动
6. AOE网用邻接表来表示，并且假设顶点序列已按拓扑有序与逆拓扑有序排好。如上例:
   • 先正向推，然后反向推回来。(分别计算最早时间和最晚时间)

img
img

7.2.4. 算法实现

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

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;
    //开始正向拓扑计算
    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];
    //反向计算事件最迟开始时间
    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;
        }
    } 
}

img

8. 2009年统考题(综合应用题)

带权图 ( 权值非负, 表示边连接的两顶点间的距离) 的最短路径 问题是找出从初始顶点到目标顶点之间的一条最短路径. 假设从初始 顶点到目标顶点之间存在路径, 现有一种解决该问题的方法:

1. 设最短路径初始时仅包含初始顶点, 令当前顶点u为初始顶点;
2. 选择离u 最近且尚未在最短路径中的一个顶点v, 加入到最短路径中, 修改当前顶点 u = v ;
3. 重复步骤2), 直到u是目标顶点时为止. 请问上述方法能否求得最短路径? 若该方法可行, 请证明之; 否则, 请举例说明.
4. 不可行，可能取到的是局部最优解