本次课内容

现代科技领域中，图的应用非常广泛 ，如电路分析、通信工程、网络理论、人工智能、形式语言、系统工程、控制论和管理工程等都广泛应用了图的理论。图的理论几乎在所有工程技术中都有应用。例如，电路计算辅助设计（CAD）中，首先必须将电网转换成图形，然后才能进行电路分析。下面将介绍：

• 图的基本概念
• 图的存储方式
• 图的遍历
• 生成树的概念

图的基本概念

图的定义和术语

图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为 \(G=(V,E)\)

其中：V(G)是顶点的非空有限集, E(G)是边的有限集合，边是顶点的无序对或有序对

有向图——有向图G是由两个集合V(G)和E(G)组成的

其中：V(G)是顶点的非空有限集,E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v,w是顶点，v为弧尾，w为弧头

无向图——无向图G是由两个集合V(G)和E(G)组成的

其中：V(G)是顶点的非空有限集,E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且 \(（v,w)=(w,v)\)

图的例子

例:

图G1中： \[V(G1)={1,2,3,4,5,6}\] \[E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>}\]

例:

图G2中： \[V(G2)={1,2,3,4,5,6,7}\] \[E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}\]

完全图

如果边\((u,v)\)或\(<u,v>\)是允许的，这样的边称为自回路。两顶点间允许有多条相同边的图，称为多重图。本章的图不允许自回路和多重图。

有向完全图——在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有 \(n(n-1)\) 条边。

无向完全图——在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有 \(n(n-1)/2\) 条边。

权与网

权——与图的边或弧相关的数据信息叫权

网——带权的图叫网

子图——如果图G(V,E)和图G’(V’,E’),满足： \[V'\subseteq V\] \[E’\subseteq E\]

则称G’为G的子图

顶点的度

若\((u,v)\)是无向图的一条边，则称顶点\(u\)和\(v\)相连接，并称边\((u,v)\)与顶点\(u\)和\(v\)相关联。若\(<u,v>\)是有向图的一条边，则称顶点\(u\)邻接到顶点\(v\),顶点\(v\)邻接自顶点\(u\)，并称\(<u,v>\)与顶点\(u\)和\(v\)相关联。

无向图中，顶点的度为与每个顶点相连的边数

有向图中，顶点的度分成入度与出度

入度：以该顶点为头的弧的数目

出度：以该顶点为尾的弧的数目

路径与回路

路径——路径是顶点的序列 \(V={Vi1,Vi2,……Vin}\) ，满足 \((V_{i j-1},V_{i j})\in E\) 或 \(<V_{i j-1},V_{i j}\in E,(1<j\leq n)\)

路径长度——沿路径边的数目或沿路径各边权值之和

简单路径——序列中顶点不重复出现的路径叫简单路径

回路——称顶点序列中存在 \(v_p=v_q(p≠q)\) 的路径为回路或环。

简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路

连通图

连通——从顶点V到顶点W有一条路径，则说V和W是连通的。

连通图——图中任意两个顶点都是连通的，则该图叫连通图，否则叫做非连通图。

连通分量——无向图G中的极大连通子图称为G的连通分量。或非连通图的每一个连通部分叫连通分量。

强连通图——有向图中，如果若任意一对顶点\(V_i\)和\(V_j\)间存在一条从\(V_i\)到\(V_j\)的路径和一条从\(V_j\)到\(V_i\)的路径，则称G是强连通图。

强连通分量——有向图G中的极大强连通子图称为G的强连通分量。

连通图示例

生成树与生成森林

生成树——所谓连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图。它必定包含且仅包含G的n-1 条边。图8.4(b)G”示出了图8.1中G1 的一棵生成树。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。

生成森林——在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。

图的基本操作

图的ADT

CreatGraph（G）输入图G的顶点和边，建立图G的存储。
DestroyGraph（G）释放图G占用的存储空间。
GetVex（G，v）在图G中找到顶点v，并返回顶点v的相关信息。
PutVex（G，v，value）在图G中找到顶点v，并将value值赋给顶点v。
InsertVex（G，v）在图G中增添新顶点v。
DeleteVex（G，v）在图G中，删除顶点v以及所有和顶点v相关联的边或弧。
InsertArc（G，v，w）在图G中增添一条从顶点v到顶点w的边或弧。
DeleteArc（G，v，w）在图G中删除一条从顶点v到顶点w的边或弧。
DFSTraverse（G，v）在图G中，从顶点v出发深度优先遍历图G。
BFSTraverse（G，v）在图G中，从顶点v出发广度优先遍历图G。
LocateVex（G，u）在图G中找到顶点u，返回该顶点在图中位置。
FirstAdjVex（G，v）在图G中，返回v的第一个邻接点。若顶点在G中没有邻接顶点，则返回“空”。
NextAdjVex（G，v，w）在图G中，返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”

图的存储结构

图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包括两部分，即图中顶点的信息以及描述顶点之间的关系─边或者弧的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。

下面介绍几种常用的图的存储结构。

邻接矩阵存储方法

邻接矩阵——表示顶点间相联关系的矩阵

定义：设 \(G=(V,E)\) 是有 \(n\geq 1\) 个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵

邻接矩阵存储方法的特点

特点：

无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为 \(n(n+1)/2\)

有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为 \(n^{2}\)

无向图中顶点 \(V_i\) 的度 \(TD(V_i)\) 是邻接矩阵A中第i行元素之和

有向图中，

顶点 \(V_i\) 的出度是A中第i行元素之和

顶点 \(V_i\) 的入度是A中第i列元素之和

网络的邻接矩阵可定义为：

邻接矩阵的例子

邻接矩阵的结构体

用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：

  #define MaxVertexNum 100      /*最大顶点数设为100*/
  typedef char VertexType;           /*顶点类型设为字符型*/
  typedef int EdgeType;             /*边的权值设为整型*/
  typedef struct {
      VertexType vexs[MaxVertexNum];    /*顶点表*/
      EdgeType edges[MaxVertexNum][MaxVertexNum];  /*邻接矩阵，即边表*/               
                                                               
      int n,e;                        /*顶点数和边数*/
  } MGraph;    /*MGragh是以邻接矩阵存储的图类型*/ 

邻接矩阵创建矩阵

建立一个有向图的邻接矩阵存储的算法：

void CreateMGraph(MGraph *G) {
    int i,j,k;
    printf("请输入顶点数和边数(输入格式为:顶点数,边数):\n");
    scanf("%d,%d",&(G->n),&(G->e));          /*输入顶点数和边数*/
    printf("请输入顶点信息(输入格式为:顶点号<CR>):\n");
    for (i=0;i<G->n;i++) 
        scanf("\n%c",&(G->vexs[i]));         /*输入顶点信息，建立顶点表*/
    for (i=0;i<G->n;i++)
        for (j=0;j<G->n;j++)  
            G->edges[i][j]=0;          /*初始化邻接矩阵*/
    printf("请输入每条边对应的两个顶点的序号(输入格式为:i,j<CR>):\n");
    for (k=0;k<G->e;k++){
        scanf("\n%d,%d",&i,&j);       /*输入e条边，建立邻接矩阵*/
        G->edges[i][j]=1; 
        /*若在此加入G->edges[j][i]=1;，则为无向图的邻接矩阵存储建立*/
    }
} /*CreateMGraph*/ 

邻接表

邻接表(Adjacency List)是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。在邻接表表示中有两种结点结构，如图8.9所示。

邻接表图示

邻接表的实现

邻接表表示的形式描述如下：

＃define MaxVertexNum 100          /*最大顶点数为100*/

typedef struct node{               /*边表结点*/
    int adjvex;                   /*邻接点域*/
    struct node  * next;         /*指向下一个邻接点的指针域*/
                                    /*若要表示边上信息，则应增加一个数据域info*/
} EdgeNode;        

typedef char VertexType;           /*顶点用字符表示*/

typedef struct vnode{              /*顶点表结点*/
    VertexType vertex;          /*顶点域*/
    EdgeNode  * firstedge;      /*边表头指针*/
} VertexNode;       

typedef VertexNode AdjList[MaxVertexNum];  /*AdjList是邻接表类型*/

typedef struct{  
    AdjList adjlist;                /*邻接表*/
    int n,e;                     /*顶点数和边数*/
} ALGraph;               /*ALGraph是以邻接表方式存储的图类型*/

建立邻接表的算法

建立一个有向图的邻接表存储的算法：

void CreateALGraph(ALGraph *G) {
    int i,j,k;
    EdgeNode * s;
    printf("请输入顶点数和边数(输入格式为:顶点数,边数)：\n");
    scanf("%d,%d",&(G->n),&(G->e));    /*读入顶点数和边数*/
    printf("请输入顶点信息(输入格式为:顶点号<CR>)：\n");
    for (i=0;i<G->n;i++) { /*建立有n个顶点的顶点表*/
        scanf("\n%c",&(G->adjlist[i].vertex));  /*读入顶点信息*/
        G->adjlist[i].firstedge=NULL;      /*顶点的边表头指针设为空*/
    }
    printf("请输入边的信息(输入格式为:i,j<CR>)：\n");
    for (k=0;k<G->e;k++) { /*建立边表*/
        scanf("\n%d,%d",&i,&j);            /*读入边<Vi,Vj>的顶点对应序号*/
        s=(EdgeNode*)malloc(sizeof(EdgeNode));  /*生成新边表结点s*/
        s->adjvex=j;                      /* 邻接点序号为j */
        s->next=G->adjlist[i].firstedge;  /*将新边表结点s插入到顶点Vi的边表头部*/
        G->adjlist[i].firstedge=s; 
    }
}   /*CreateALGraph*/ 

邻接表的特点

特点

无向图中顶点Vi的度为第i个单链表中的结点数

有向图中

顶点\(V_i\)的出度为第i个单链表中的结点个数

顶点\(V_i\)的入度为整个单链表中邻接点域值是i的结点个数

逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表

图的遍历

图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：

①在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。

②在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。

③在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。

④在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。

深度优先遍历

图的遍历通常有深度优先搜索和广度优先搜索两种方式。

深度优先遍历(DFS)

方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。

深度优先遍历图示

深度优先遍历图示二

深度优先遍历算法

深度优先遍历的递归算法：

void DFS(Graph G,int v ) {
    /*从第v个顶点出发递归地深度优先遍历图G*/
    visited[v]=TRUE;
    VisitFunc(v);            /*访问第v个顶点*/
    for(w=FirstAdjVex(G,v);w; w=NextAdjVex(G,v,w))
        if (!visited[w]) 
            DFS(G,w); /*对v的尚未访问的邻接顶点w递归调用DFS*/             
}

邻接表存储图的深度优先遍历

深度优先遍历以邻接表存储的图的算法:

int visited[MaxVertexNum];     /*定义为全局变量*/
void DFSTraverseAL(ALGraph *G) {
    int i;
    for (i=0;i<G->n;i++)
        visited[i] = FALSE; /*标志向量初始化*/
    for (i=0;i<G->n;i++)
        if (!visited[i]) 
            DFSAL(G,i); /*vi未访问过，从vi开始DFS搜索*/
}  /*DFSTraveseAL*/
  

联通分量的DFS遍历

void DFSAL(ALGraph *G,int i) {
    /*以Vi为出发点对邻接表存储的图G进行DFS搜索*/
    EdgeNode *p;
    printf("visit vertex:V%c\n",G->adjlist[i].vertex); /*访问顶点Vi*/
    visited[i]=TRUE;             /*标记Vi已访问*/
    p=G->adjlist[i].firstedge;       /*取Vi边表的头指针*/
    while(p) { /*依次搜索Vi的邻接点Vj，j=p->adjva*/
        if (!visited[p->adjvex]) 
            DFSAL(G,p->adjvex); /*若Vj尚未访问，则以Vj为出发点向纵深搜索*/               
        p = p->next;          /*找Vi的下一个邻接点*/
    }
}/*DFSAL*/

DFS示例

DFS示例续

广度优先遍历(BFS)

方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。

BFS图示

BFS图示续

BFS算法实现

广度优先遍历图的非递归算法：

void  BFSTraverse(MGraph G, Status(*Visit)(int v)) {
    /*按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited*/
    c_SeQueue  *Q;  
    VertexType u,v,w;
    for (u=0; u<G.n; ++u)     
        visited[u]=FALSE;
    Q = Init_SeQueue();  /*置空的循环队列Q*/
    for (u=0; u<G.n; ++u)
        if (!visited[u]) { /*u尚未访问*/
            visited[u]=TRUE; 
            Visit(u);  /*访问u*/
            In_SeQueue (Q,u);           /*u入队列*/
            while (!Empty_SeQueue(Q)) { 
                Out_SeQueue (Q,&v);      /*队头元素出队并置为v*/
                for(w=FirstAdjVex(G,v); w; w=NextAdjVex(G,v,w))
                    if (!visited[w]) {   /*v的尚未访问的邻接顶点w*/
                        visited[w]=TRUE; Visit(w);   /*访问w*/
                        In_SeQueue (Q,w);  /*w入队列Q*/
                   }
            }   
        }
}/*BFSTraverse*/

图的BFS算法

对以邻接矩阵为存储结构的整个图G进行广度优先遍历的算法:

void BFSTraverseM(MGraph *G) {
     /*广度优先遍历以邻接矩阵存储的图G，顶点类型设为整数型*/
     int i;
     for (i=0;i<G->n;i++)
          visited[i]=FALSE;              /*标志向量初始化*/
     for (i=0;i<G->n;i++)
         if (!visited[i]) 
            BFSM(G,i);    /* Vi未访问过，从Vi开始BFS搜索*/
} /*BFSTraverseM*/

连通分量的BFS算法

void BFSM(MGraph *G,int k) {
    /*以Vi为出发点，对邻接矩阵存储的图G进行BFS搜索*/
    int i,j;
    c_SeQueue  *Q;
    Q=Init_SeQueue();           /*置空的循环队列Q*/
    printf("visit vertex:V%2d\n",G->vexs[k]);   /*访问原点Vk*/
    visited[k]=TRUE;
    In_SeQueue (Q,k);                      /*原点Vk入队列*/
    while (!Empty_SeQueue (Q)) {
        Out_SeQueue(Q,&i);                 /*Vi出队列*/
        for (j=0;j<G->n;j++)                   /*依次搜索Vi的邻接点Vj*/
            if (G->edges[i][j]==1 && !visited[j]) {       /*若Vj未访问*/
                printf("visit vertex:V%2d\n",G->vexs[j]); /*访问Vj */
                visited[j]=TRUE;
                In_SeQueue (Q,j);                    /*访问过的Vj入队列*/
            }
    }
}/*BFSM*/ 

BFS流程图

BFS示例

BFS示例续一

BFS示例续二

图的连通性

判定一个图的连通性是图的一个应用问题，我们可以利用图的遍历算法来求解这一问题。本节将重点讨论无向图的连通性以及由遍历图得到其生成树或生成森林等几个有关图的连通性的问题。

无向图的连通性

在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。

生成树和生成森林

生成树

在图论中，常常将树定义为一个无回路连通图。

定义：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树

由于n个顶点的连通图至少有n-1条边，而所包含n-1条边及n个顶点的连通图都是无回路的树，所以生成树是连通图的极小连通子图。所谓极小是指边数最少，若在生成树中去掉任何一条边，都会使之变为非连通图，若在生成树上任意添加一条边，就必定出现回路。

对图进行遍历时经过的边和图的所有顶点所构成的子图即为该图的生成树。

由深度优先搜索得到的生成树称为深度优先生成树，简称DFS生成树。

由广度优先搜索得到的生成树称为广度优先生成树，简称BFS生成树。

生成树特点

一个图可以有许多棵不同的生成树，所有生成树具有以下共同特点：

• 生成树的顶点个数与图的顶点个数相同
• 生成树是图的极小连通子图
• 一个有n个顶点的连通图的生成树有n-1条边
• 生成树中任意两个顶点间的路径是唯一的
• 在生成树中再加一条边必然形成回路
• 含n个顶点n-1条边的图不一定是生成树

生成树图示

深度优先生成森林算法

建立无向图的深度优先生成森林算法：

void DFSForest(MGraph G, CSTree *T) {
    /*假设以孩子兄弟链表作生成森林的存储结构（参考6.3.2节），无向图G
      以邻接矩阵形式存储*/
    int v; CSTree p,q;
    (*T)=NULL;
    for (v=0;v<G.n;++v) 
        visited[v]=FALSE;  /*标志向量初始化*/
    for(v=0;v<G.n;++v)
        if (!visited[v]) { /*顶点v为新的生成树的根结点*/
            p=(CSTree)malloc(sizeof(CSNode));       /*分配根结点*/
            p->data=G.vexs[v];
            p->firstchild = NULL;
            p->nextsibling= NULL;
            if (!(*T)) 
                (*T)=p;                    /*T是第一棵生成树的根*/
            else  
                q->nextsibling=p;     /*前一棵的根的兄弟是其它生成树的根*/
            q = p;                            /*q指示当前生成树的根*/
            DFSTree(G,v,&p);                 /*建立以p为根的生成树*/
        }
}

深度优先生成树算法

void  DFSTree(MGraph G,int v ,CSTree *T) {
    /*从第v个顶点出发深度优先遍历图G，建立以*T为根的生成树*/
    int w,first; CSTree p,q;
    visited[v]=TRUE;
    first=TRUE;
    for(w=FirstAdjVex(G,v);  w>=0;  w=NextAdjVex(G,v,w))
        if(!visited[w]) {
            p=(CSTree)malloc(sizeof(CSNode);       /*分配孩子结点*/
            p->data=G.vexs[v];
            p->firstchild = NULL;
            p->nextsibling= NULL;
            if (first) { /*w是v的第一个未被访问的邻接顶点，作为根的左孩子结点*/
                (*T)->firstchild=p;
                first=FALSE; }
            else
                q->nextsibling=p; /*w是v的其它未被访问的邻接顶点，作为上一邻接顶点的右兄弟*/                             
            q=p;
            DFSTree(G,w,&q);  /*从第w个顶点出发深度优先遍历图G，建立生成子树*q*/
        }
} 

深度优先生成树算法细节

其中：

int FirstAdjVex(MGraph G,int v) { 
    for(int j=0;j<G.vexnum;j++)
        if(G.edges[v][j])
            return j; 
    return -1;
}

int NextAdjVex(MGraph G,int v,int w) { 
    for(int j=w+1;j<G.vexnum;j++)
        if(G.edges[v][j])
            return j; 
    return -1;
}

最小生成树

问题提出:要在n个城市间建立通信联络网, 用“顶点”表示城市,用边的“权”表示城市间建立通信线路所需花费代价, 希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小。

问题分析:

• n个城市间，最多可设置 \(n(n-1)/2\) 条线路
• n个城市间建立通信网，只需n-1条线路

问题转化为：如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小

最小生成树性质

设 \(G=(V，E)\) 是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U (即u∈U)里、另一个端点不在U(即v∈V-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u,v)。

可利用最小生成树性质来构造最小生成树。本节介绍两种方法：

构造最小生成树方法-Prim算法

普里姆(Prim)算法

假设G＝（V，E）为一网图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。设置两个新的集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为U＝{u1}（假设构造最小生成树时，从顶点u1出发），集合T的初值为T＝{ }。Prim算法的思想是，从所有u∈U，v∈V－U的边中，选取具有最小权值的边（u，v），将顶点v加入集合U中，将边（u，v）加入集合T中，如此不断重复，直到U＝V时，最小生成树构造完毕，这时集合T中包含了最小生成树的所有边。

Prim算法描述

Prim算法可用下述过程描述，其中用 \(w_{uv}\) 表示顶点 u 与顶点 v 边上的权值。

（1）U＝{u1},T={};

（2）while (U≠V)

{(u，v)＝min{wuv| u∈U，v∈V－U }；

T＝T＋{(u，v)}；

U＝U＋{v}；}

（3）结束。

Prim算法示意图

Prim算法过程

Prim算法证明思路

设用prim算法得出的边分别为\(e_1\)，\(e_2\)...\(e_n\)，依次加入的点为\(p_1\)，\(p_2\)...\(p_n\)：

若不存在最小生成树包含\(e_1\)，那么把\(e_1\)加入任意一颗最小生成树，必然成环，并且在环上可以找到一条不小于\(e_1\)的边，（因为成环了，所以环上的点必然至少链接了两条边，而\(e_1\)是\(p_1\)所链接的最小的边）删掉此边，得到一颗更优的生成树或者得到了一颗包含\(e_1\)的最小生成树，矛盾。

若包含\(e_1\)的最小生成树都不包含\(e_2\)，那么把\(e_2\)加入其中一颗包含\(e_1\)的最小生成树中，也会成环，并且在环中也能找到不小于\(e_2\)的边（因为成环了，所以顶点1顶点2所形成的集合必然包含至少三条边，而\(e_2\)是当中第二小的），同上也会产生矛盾。

以此类推，可以证明prim算法得到的是最小生成树。

Prim算法实现

Prim算法：

void Prim（int gm[ ][MAXNODE]，int n，int closevertex[ ]）{
    /*用Prim方法建立有n个顶点的邻接矩阵存储结构的网图gm
     的最小生成树从序号为0的顶点出发；建立的最小生成树
     存于数组closevertex中*/
    int lowcost[100],mincost;
    int i,j,k;
    for (i=1;i<n;i++) { /*初始化*/
        lowcost[i]=gm[0][i];
        closevertex[i]=0;
    }
    lowcost[0]=0;        /*从序号为0的顶点出发生成最小生成树*/
    closevertex[0]=0;
    for (i=1;i<n;i++) { /*寻找当前最小权值的边的顶点*/
        mincost=MAXCOST;     /*MAXCOST为一个极大的常量值*/ 
        j=1; k=1;
        while (j<n) { 
            if (lowcost[j]<mincost && lowcost[j]!=0) {
                mincost=lowcost[j];
                k=j; 
            }
            j++;
        }
        printf(“顶点的序号＝%d边的权值＝%d\n”,k,mincost);
        lowcost[k]=0;
        for (j=1;j<n;j++)    /*修改其它顶点的边的权值和最小生成树顶点序号*/
            if (gm[k][j]<lowcost[j]) { 
                lowcost[j]=gm[k][j];
                closevertex[j]=k; 
            }
    }
} 
void main() {
    int b[4][MAXNODE]={{MAXCOST,10,8,MAXCOST},
                        {10,MAXCOST,15,5},
                        {8,15,MAXCOST,30},
                        {MAXCOST,5,30,MAXCOST}};
    int a[MAXNODE];
    Prim(b,4,a);
    printf("\n求得最小生成树的边是:\n");
    for(int i=1;i<4;i++)
        printf("(%d, %d) \n",i,a[i]);
}

构造最小生成树方法-Kruskal

克鲁斯卡尔(Kruskal)算法

算法思想：

设连通网 \(N=(V,\{E\})\)

令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{})，每个顶点自成一个连通分量

在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；

否则，舍去此边，选取下一条代价最小的边

依此类推，直至T中所有顶点都在同一连通分量上为止

Kruskal算法图示

Kruskal算法证明思路

设\(T\)为Kruskal算法构造出的生成树，\(U\)是\(G\)的最小生成树，如果\(T\)与\(U\)不相等，我们就需要证明\(T\)和\(U\)的构造代价相同。

不妨设\(k\)条边存在于\(T\)中，却不在\(U\)中，我们做\(k\)次变换，每次变换中，把\(T\)中的一条边\(e\)加入\(U\)，同时删除\(U\)中的一条边\(f\)，最后使\(T\)和\(U\)的边集相同。\(e\)、\(f\)按如下规则选取：

• \(e\)是在\(T\)中却不在\(U\)中的边的最小的一条边；
• \(e\)加入\(U\)后，肯定构成唯一的一个环路，令\(f\)是这个环路中的一条边，但不在\(T\)中。\(f\)一定存在，因为\(T\)中没有环路。

我们假设\(e\)权值小于\(f\)，这样变换后\(U\)的代价一定小于变换前的代价，而这和\(U\)是最小生成树矛盾，因此\(e\)权值不小于\(f\)。再假设\(e\)权值大于\(f\)，由Kruskal算法知，\(f\)在\(e\)之前从\(E\)中取出，但被舍弃了，一定是由于和权值小于等于\(f\)的边构成了环路。但是\(T\)中权值小于等于\(f\)（小于\(e\)）的边一定存在于\(U\)中，而\(f\)在\(U\)中却没有和它们构成环路，又推出矛盾。所以\(e\)权值等于\(f\)。

这样，每次变换后\(U\)的代价都不变，所以\(k\)次变换后，\(U\)和\(T\)的边集相同，且代价相同，这样就证明了\(T\)也是最小生成树。

Kruskal算法结构体

设置一个结构数组edges存储网中所有的边，边的结构类型包括构成的顶点信息和边权值，定义如下：

#define MAXEDGE  <图中的最大边数>
typedef struct {
    elemtype v1;
    elemtype v2;
    int cost;
} EdgeType;

EdgeType edges[MAXEDGE];

在结构数组edges中，每个分量edges[i]代表网中的一条边，其中edges[i].v1和edges[i].v2表示该边的两个顶点，edges[i].cost表示这条边的权值。为了方便选取当前权值最小的边，事先把数组edges中的各元素按照其cost域值由小到大的顺序排列。

Kruskal算法实现思路

对于有n个顶点的网，设置一个数组father[n]，其初值为father[i] = -1（i＝0，1，…，n－1），表示各个顶点在不同的连通分量上，然后，依次取出edges数组中的每条边的两个顶点，查找它们所属的连通分量，假设\(v_{f1}\)和\(v_{f2}\)为两顶点所在的树的根结点在father数组中的序号，若\(v_{f1}\)不等于\(v_{f2}\)，表明这条边的两个顶点不属于同一分量，则将这条边作为最小生成树的边输出，并合并它们所属的两个连通分量。

Kruskal算法实现

void Kruskal（EdgeType edges[ ]，int n）{
    /*用Kruskal方法构造有n个顶点的图edges的最小生成树*/
    int father[MAXEDGE];
    int i,j,vf1,vf2;
    for (i=0;i<n;i++) 
        father[i]=-1;
    i=0;j=0;
    while(i<MAXEDGE && j<n-1) {
        vf1 = Find(father,edges[i].v1);
        vf2 = Find(father,edges[i].v2);
        if (vf1!=vf2) { 
            father[vf2]=vf1;
            j++;
            printf(“%3d%3d\n”,edges[i].v1,edges[i].v2);
        }
        i++;
    }   
} 

int Find（int father[ ]，int v）{
    /*寻找顶点v所在树的根结点*/
    int t;
    t=v;
    while(father[t]>=0)
        t = father[t];
    return(t);
}

最短路径问题

问题提出

用带权的有向图表示一个交通运输网，图中：

顶点——表示城市

边——表示城市间的交通联系

权——表示此线路的长度或沿此线路运输所花的时间或费用等

问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径

从某个源点到其余各顶点的最短路径

迪杰斯特拉(Dijkstra)算法思想

算法思路：按路径长度递增次序产生最短路径算法，把V分成两组：

（1）S：已求出最短路径的顶点的集合

（2）V-S=T：尚未确定最短路径的顶点集合

将T中顶点按最短路径递增的次序加入到S中，保证：

• 从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度
• 每个顶点对应一个距离值

S中顶点：从V0到此顶点的最短路径长度

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

依据：可以证明\(V_0\)到T中顶点\(V_k\)的最短路径，或是从\(V_0\)到\(V_k\)的直接路径的权值；或是从\(V_0\)经S中顶点到\(V_k\)的路径权值之和。（反证法可证）

迪杰斯特拉(Dijkstra)算法实现要点

(1)设置两个顶点的集合T和S;

集合S存放已找到最短路径的顶点

集合T(=V-S)存放当前还未找到最短路径的顶点

(2)初始状态时,S只包含源点\(v_0\) ;

(3)从T中选取某个顶点\(v_i\)(要求\(v_i\)到\(v_0\)的路径长度最短)加入到S中;

(4)S中每加入一个顶点\(v_i\),都要修改顶点\(v_0\)到T中剩余顶点的最短路径长度值:它们的值为原来值与新值的较小者,新值是\(v_0\)到\(v_i\)的最短路径长度加上\(v_i\)到该顶点的路径长度。

(5)不断重复(3)和(4),直到S包含全部顶点。

Dijkstra图示

弗洛伊德(Floyd)算法

如何求每一对顶点之间的最短路径?

方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次—— T(n)=O(n³)

方法二：弗洛伊德(Floyd)算法，该算法的思想是逐个顶点试探法，求最短路径步骤为：

• 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值，否则为无穷大
• 逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值
• 所有顶点试探完毕，算法结束

只有五行的算法：

void floyd() {
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

弗洛伊德(Floyd)算法图示一

弗洛伊德(Floyd)算法图示二

弗洛伊德(Floyd)算法图示三

弗洛伊德(Floyd)算法的本质一

Floyd算法的本质是一种动态规划（Dynamic Programming）算法

动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度。

在动态规划算法中，处于首要位置、且也是核心理念之一的就是状态的定义。在这里，把d[k][i][j]定义成：

只能使用第1号到第k号顶点作为中间媒介时，点i到点j之间的最短路径长度。

图共有n个顶点，标号从1开始到n。因此，在这里，k可以认为是动态规划算法在进行时的一种层次，或者称为“松弛操作”。

• d[1][i][j]表示 只使用1号点作为中间媒介时，点i到点j之间的最短路径长度；
• d[2][i][j]表示使用1号点到2号点中的所有点作为中间媒介时，点i到点j之间的最短路径长度；
• d[n][i][j]表示 使用1号到n号点时，点i到点j之间的最短路径长度。

弗洛伊德(Floyd)算法的本质二

有了状态的定义之后，就可以根据动态规划思想来构建动态转移方程。动态转移的基本思想可以认为是建立起某一状态和之前状态的一种转移表示。

按照前面的定义，d[k][i][j]是一种使用1号到k号点的状态，可以想办法把这个状态通过动态转移，使用1号到(k-1)号的状态获得。

对于d[k][i][j]（即使用1号到k号点中的所有点作为中间媒介时，i和j之间的最短路径），可以分为两种情况：

• i到j的最短路不经过k；
• i到j的最短路经过了k。

不经过点k的最短路情况下，d[k][i][j]=d[k-1][i][j]。经过点k的最短路情况下，d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]。

因此，综合上述两种情况，便可以得到Floyd算法的动态转移方程

\[d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])\]

关键路径

问题提出

把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始

例 设一个工程有11项活动，9个事件

事件 V1——表示整个工程开始

事件V9——表示整个工程结束

问题：

（1）完成整项工程至少需要多少时间？

（2）哪些活动是影响工程进度的关键？

拓扑排序

拓扑排序是求解网络问题的主要算法之一。管理技术，如计划评审技术和关键路径都用到这一算法

相关定义

AOE网(Activity On Edge)——也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间

路径长度——路径上各活动持续时间之和

关键路径——路径长度最长的路径叫~

Ve(k)——表示事件Vk的最早发生时间

Vl(k)——表示事件Vk的最迟发生时间

e(i)——表示活动ai的最早开始时间

l(i)——表示活动ai的最迟开始时间

l(i)-e(i)——表示完成活动ai的时间余量

关键活动——关键路径上的活动叫关键活动，即l(i)=e(i)的活动

拓扑排序的概念

一个拓扑序列是AOV网络中各顶点的线性序列，这使得对图中任意两个顶点\(i\)和\(j\)，若在网络中\(i\)是\(j\)的前驱节点，则在线性序列中\(i\)先于\(j\)。

拓扑排序是求一个AOV网中各活动的一个拓扑序列的运算，它可用于测试AOV网络的可行性。

拓扑排序的步骤可描述如下：

第一步：在图中选择一个入度为零的顶点，并输出之；

第二步：在图中删除该定点及其所有出边（以该顶点为尾的有向边）；

第三步：重复第一步和第二步，直到所有顶点都已列出，或者直到剩下的图中再也没有入度为零的顶点为止，后者表示图中包含有向回路。

拓扑排序的要点

注意，从图中删除一个顶点及其所有出边，会产生新的入度为零的顶点，必须用一个堆栈或队列来保存这些待处理的无前驱顶点。事实上，这些入度为零的顶点的输出次序就拓扑排序而言是无关紧要的。

从上面的讨论可知，拓扑排序算法包括两个基本操作：

（1）判断一个顶点的入度是否为零；

（2）删除一个顶点的所有出边。

如果我们对每个顶点的直接前驱予以计数，使用一个数组\(InDgree\)保存每个顶点的入度，即\(InDgree[i]\)为顶点\(i\)的入度，则基本操作（1）很容易实现。而基础操作（2）在使用邻接表表示时，一般会比邻接矩阵更有效。在邻接矩阵的情况下，必须处理与该顶点有关的整行元素（\(n\)个），而邻接表只需处理在邻接矩阵中非零的那些顶点。

最早发生时间

事件的最早发生时间

ve[k]是指从源点\(v_0\)到顶点\(v_k\)的最大路径长度所代表的时间。这个时间决定了所有从顶点\(v_k\)发出的有向边所代表的活动能够开工的最早时间。根据AOE网的性质，只有进入\(v_k\)的所有活动 \(< v_j,v_k>\) 都结束时，\(v_k\)代表的事件才能发生；而活动 \(< v_j, v_k>\) 的最早结束时间为ve[j]+dut(< vj, vk>)。所以计算\(v_k\)发生的最早时间的方法如下：

最迟发生时间

事件的最迟发生时间

vl[k]是指在不推迟整个工期的前提下，事件vk允许的最晚发生时间。设有向边 \(< v_k，v_j>\) 代表从\(v_k\)出发的活动，为了不拖延整个工期,vk发生的最迟时间必须保证不推迟从事件\(v_k\)出发的所有活动< vk，vj>的终点vj的最迟时间vl[j]。

vl[k]的计算方法如下：

活动的最早和最晚开始时间

活动ai的最早开始时间e[i]

若活动ai是由弧表示，根据AOE网的性质，只有事件vk发生了，活动ai才能开始。也就是说，活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有： \[e[i]=ve[k]\]

活动ai的最晚开始时间l[i]

活动ai的最晚开始时间是指，在不推迟整个工程完成时间的前提下，必须开始的最晚时间。若由弧表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，应该有：

\[l[i]=vl[j]-dut(<vk,vj>)\]

判断关键活动

根据每个活动的最早开始时间e[i]和最晚开始时间l[i]就可判定该活动是否为关键活动，也就是那些l[i]=e[i]的活动就是关键活动，而那些l[i]>e[i]的活动则不是关键活动，l[i]-e[i]的值为活动的时间余量。关键活动确定之后，关键活动所在的路径就是关键路径。

判断关键活动图示

求关键路径的算法步骤

由上述方法得到求关键路径的算法步骤为：

（1）输入e条弧,建立AOE-网的存储结构；

（2）从源点v0出发，令ve[0]＝0，按拓扑有序求其余各顶点的最早发生时间vei。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤（3）。

（3）从汇点vn出发，令vl[n-1]=ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vli；

（4）根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间1（s）。若某条弧满足条件e(s)=l(s),则为关键活动。

求关键路径图示