图

返回“数据结构”目录

图的基本概念

图的定义

图(Graph)G由两个集合V和E组成，记为G=(V, E)，其中：V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。

通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。

图是一种非线性的数据结构，图中的结点之间是多对多的关系，每个结点都可能有多个前趋，也可能有多个后继。

有向图与无向图

有向图：若图G中的每条边都是有方向的，则称G为有向图(Digraph)。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。

【例】<vi，vj>表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，<vi，vj>和<vj，vi>是两条不同的有向边。

【例】下面图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为： V(G1)={v1，v2，v3} E(G1)={<v1，v2>，<v2，v1>，<v2，v3>}

G1

无向图：若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。

【例】无序对(vi，vj)和(vj，vi)表示同一条边。

【例】下面图中的G2和G3均是无向图，它们的顶点集和边集分别为： - V(G2)={v1，v2，v3，v4} E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)} - V(G3)={v1，v2，v3，v4，v5，v6，v7} E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}

G2

G3

注意：在以下讨论中，不考虑顶点到其自身的边。即若(v1，v2)或<vl，v2>是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现（重图），即只讨论没有重复边的图（简单图）。

顶点和边的关系

图G的顶点数n和边数e的关系 - 若G是无向图，则0≤e≤n(n-1)/2。恰有n(n-1)/2条边的无向图称无向完全图(Undirected Complete Graph) - 若G是有向图，则0≤e≤n(n-1)。恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。

注意：完全图具有最多的边数。任意一对顶点间均有边相连。

【例】图G2就是具有4个顶点的无向完全图。

无向边和顶点关系：若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接点(Adjacent)，或称vi和vj相邻接；并称(vi,vj)依附或关联(Incident)于顶点vi和vj，或称(vi，vj)与顶点vi和vj相关联。

【例】图G2中： - 与顶点v1相邻接的顶点是v2，v3和v4 - 关联于顶点v2的边是(v1，v2)，(v2，v3)和(v2，v4)

有向边和顶点关系：若<vi，vj>是一条有向边，则称顶点vi邻接到vj，顶点vi邻接于顶点vj；并称边<vi，vj>关联于vi和vj或称<vi，vj>与顶点vi和vj相关联。

【例】在图G1中，关联于顶点v2的弧是<v1，v2>，<v2，v1>和<v2，v3>。

顶点的度

无向图中顶点v的度(Degree)：无向图中顶点v的度(Degree)是关联于该顶点的边的数目，记为D(v)。

【例】图G2中顶点v1的度为3

有向图顶点v的入度(In Degree)：有向图中，以顶点v为终点的边的数目称为v的入度，记为ID(v)。 【例】图G1中顶点v2的人度为l

有向图顶点v的出度(Out Degree)：有向图中，以顶点v为始点的边的数目，称为v的出度，记为OD(v)

【例】图G1中顶点v2的出度为2

有向图顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。

【例】图G1中顶点v2的人度为l，出度为2，则度为3。

无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系： \[e=\frac{1}{2}\sum_{i=1}^nD(v_i)\]

子图

子图: 设G=(V，E)是一个图，若V’是V的子集，E’是E的子集，且E’中的边所关联的顶点均在V’中，则G’=(V’，E’)也是一个图，并称其为G的子图(Subgraph)。

【例】给出有向图Gl的若干子图；给出无向图G2的若干个子图。

缺失图片：subgraph（subgraph.jpg）

路径

无向图的路径:在无向图G中，若存在一个顶点序列vp,vi1，vi2,…，vim，vq，使得(vp，vi1)，(vi1，vi2)，…，(vim，vq)均属于E(G)，则称顶点vp到vq存在一条路径(Path)。

回路或环：从vp到vq的一条路径，若vp=vq，则这条路径称为回路。

有向图的路径:在有向图G中，路径也是有向的，它由E(G)中的有向边<vp，vi1>，<vi1，vi2>，…，<vim，vq>组成。

路径长度:路径长度定义为该路径上边的数目。

简单路径:若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称此路径为一条简单路径。

【例】在图G2中顶点序列vl，v2，v3，v4是一条从顶点v1到顶点v4的长度为3的简单路径

【例】在图G2中，顶点序列v1，v2，v4，v1，v3是一条从顶点v1到顶点v3的长度为4的路径，但不是简单路径；

简单回路或简单环(Cycle):起点和终点相同(vp=vq)的简单路径称为简单回路或简单环(Cycle)。

【例】图G2中，顶点序列v1，v2，v4，v1是一个长度为3的简单环

【例】有向图G1中，顶点序列v1，v2，v1是一长度为2的有向简单环。

有根图和图的根:在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。

顶点间的连通性:在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。

连通图和连通分量

连通图:若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图(Con-nected Graph)。

【例】图G2，和G3是连通图。

连通分量:无向图G的极大连通子图称为G的连通分量(Connected Component)。

注意：① 任何连通图的连通分量只有一个，即是其自身 ② 非连通的无向图有多个连通分量。

【例】下图中的G4是非连通图，它有两个连通分量H1和H2。

强连通图:有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。

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

注意：① 强连通图只有一个强连通分量，即是其自身。② 非强连通的有向图有多个强连分量。

【例】图G1不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，如右图所示。

网络

网络(Network):若将图的每条边都赋上一个权，则称这种带权图为网络(Network)。

注意：权是表示两个顶点之间的距离、耗费等具有某种意义的数。

【例】下图就是一个网络的例子。

练习

给定图7.28，求每个结点的入度、出度，强连通分量。

图的存储结构

以下假定顶点序号从0开始，即图G的顶点集的一般形式是V(G)={v0，vi，…，Vn-1}。

图的邻接矩阵表示法

在图的邻接矩阵表示法中： - 用邻接矩阵表示顶点间的相邻关系 - 用一个顺序表来存储顶点信息

图的邻接矩阵(Adacency Matrix)：设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：\[A[i,j] = \left\{ \begin{array}{ll} 1 & \textrm{if (vi,vj) or $<vi,vj>$ exists} \\ 0 & \textrm{if (vi,vj) or $<vi,vj>$ not exists} \end{array} \right. \]

网络的邻接矩阵: 若G是网络，则邻接矩阵可定义为：\[A[i,j] = \left\{ \begin{array}{ll} wij & \textrm{if (vi,vj) or $<vi,vj>$ exists} \\ 0 or \infty & \textrm{if (vi,vj) or $<vi,vj>$ not exists} \end{array} \right. \]。其中：wij表示边上的权值；∞表示一个计算机允许的、大于所有边上权值的数。

【例】下面带权图的两种邻接矩阵分别为A3和A4。

net

图的邻接矩阵存储结构实现

#define MaxVertexNum l00 //最大顶点数，应由用户定义
typedef int VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
typedef struct{
      VextexType vextex[MaxVertexNum]; //顶点表
      EdgeType edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表
      int n, e; //图中当前的顶点数和边数
}MGragh;

注意： - 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点表及顶点数等均可省略）。 - 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeType可定义为值为0和1的枚举类型。 - 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。 - 邻接矩阵表示法的空间复杂度S(n)=O(n2)。

创建无向网络的算法

void CreateMGraph(MGraph *G) {
      int i, j, k, w;
      scanf("%d%d", &G->n, &G->e); //输入顶点数和边数
      for(i=0; i<G->n; i++) //读人顶点信息，建立顶点表
          scanf("%d", &G->vexs[i]);
      for(i=0; i<G->n; i++)
          for(j=0; j<G->n; j++)
              G->edges[i][j]=0; //邻接矩阵初始化
      for(k=0; k<G->e; k++){  //读入e条边，建立邻接矩阵
          scanf("%d%d%d", &i, &j, &w); //输入边(vi,vj)上的权w
          G->edges[i][j]=w;
          G->edges[j][i]=w;
      }
}

该算法的执行时间是O(n+n2+e)，由于e<n2，算法的时间复杂度是0(n2)。

邻接表

图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表(Adjacency List)。

邻接表的边结点结构

    ┌────┬───┐
    │adjvex │next │
    └────┴───┘

邻接表中每个表结点均有两个域:邻接点域adjvex：存放与vi相邻接的顶点vj的序号j；链域next：将邻接表的所有表结点链在一起。

注意：若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域。

头结点结构

    ┌────┬─────┐
    │vertex │firstedge│
    └────┴─────┘

顶点vi邻接表的头结点包含两个域：顶点域vertex：存放顶点vi的信息；指针域firstedge：vi的邻接表的头指针。

注意： - 为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。 - 有时希望增加对图的顶点数及边数等属性的描述，可将邻接表和这些属性放在一起来描述图的存储结构。

无向图的邻接表：对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。

n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。

【例】对于无向图G5，其邻接表表示如下面所示，其中顶点v0的边表上三个表结点中的顶点序号分别为1、2和3，它们分别表示关联于v0的三条边(v0，v1)，(v0，v2)和(v0，v3)。

有向图的邻接表：对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。

n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。

【例】有向图G6的邻接表表示如下面(a)图所示，其中顶点v1的邻接表上两个表结点中的顶点序号分别为0和4，它们分别表示从v1射出的两条边(简称为v1的出边)：<v1，v0>和<v1，v4>。

有向图的逆邻接表：在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。

n个顶点e条边的有向图，它的逆邻接表表示中有n个顶点表结点和e个边表结点。

【例】G6的逆邻表如上面(b)图所示，其中v0的人边表上两个表结点1和3分别表示射人v0的两条边(简称为v0的入边)：<v1，v0>和<v3，v0>。

邻接表的实现

typedef struct node{//边表结点
   int adjvex; //邻接点域
   struct node *next; //链域
   int weight; //若要表示边上的权，则应增加一个数据域
}EdgeNode;

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

typedef struct{
   VertexNode vertex[MaxVertexNum]; //邻接表
   int n, e; 图中当前顶点数和边数
}ALGraph; //对于简单的应用，无须定义此类型，可直接使用AdjList类型。

建立无向图的邻接表算法

void CreateALGraPh(ALGrahp *G) {
   int i, j, k;
   EdgeNode *s;
   scanf("%d%d", &G->n, &G->e); //读人顶点数和边数
   for(i=0; i<G->n; i++){
        scanf("%d", &G->vertex[i].data); //读入顶点信息
        G->adjlist[i].firstedge=NULL;//边表置为空表
   }
   for(k=0; k<G->e; k++){
         scanf("%d%d", &i, &j); 读入边(vi，vj)的顶点对序号
         s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点
         s->adjvex=j; //邻接点序号为j
         s->next=G->adjlist[i].firstedge;
         G->adjlist[i].firstedge=s; //将新结点*s插入顶点vi的边表头部
         s=(EdgeNode *)malloc(sizeof(EdgeNode));
         s->adjvex=i; //邻接点序号为i
         s->next=G->adjlist[j].firstedge;
         G->adjlistk[j].firstedge=s; //将新结点*s插入顶点vj的边表头部
    }
}

该算法的时间复杂度是O(n+e)。

注意： - 建立有向图的邻接表更简单，每当读人一个顶点对序号<i,j>时，仅需生成一个邻接序号为j的边表结点，将其插入到vj的出边表头部即可。 - 建立网络的邻接表时，需在边表的每个结点中增加一个存储边上权的数据域。

十字链表

typedef struct node{//边表结点
   int from; //弧尾
   int to;   //弧头
   struct node *right; //链域
   struct node *down;
   int weight; //若要表示边上的权，则应增加一个数据域
}EdgeNode;

typedef struct vnode{ //顶点表结点
   VertexType data; //顶点域
   EdgeNode *first_in;
   EdgeNode *first_out;
}VertexNode;

typedef struct{
   VertexNode vertex[MaxVertexNum]; //邻接表
   int n, e; //图中当前顶点数和边数
}ALGraph; //对于简单的应用，无须定义此类型，可直接使用AdjList类型。

比较

邻接矩阵和邻接表是图的两种最常用的存储结构，它们各有所长。下面从及执行某些常用操作的时间这两方面来作一比较。

邻接矩阵 邻接链表
存储表示 惟一 不惟一，各边表结点的链接次序取决于建立邻接表的算法和边的输入次序
空间复杂度 O(n2)稠密图，考虑邻接表中要附加链域，应取邻接矩阵表示法为宜 O(n+e)。稀疏图用邻接表表示比用邻接矩阵表示节省存储空间
求顶点的度 无向图：第i行(或第i列)上非零元素的个数即为顶点Vi的度。有向图：第i行上非零元素的个数是顶点Vi的出度，第i列上非零元素的个数是顶点Vi的入度，顶点Vi的度即是二者之和。 无向图：顶点vi的度则是第i个边表中的结点个数。有向图：邻接表表示中，第I个边表(即出边表)上的结点个数是顶点Vi的出度，求Vi的入度较困难，需遍历各顶点的边表。若有向图采用逆邻接表表示，则与邻接表表示相反，求Vi的入度容易，而求顶点的出度较难。在有向图中求顶点的度。采用邻接矩阵表示比邻接表表示更方便
判定(Vi，Vj)或<Vi，vj>是否是图的一条边 判定矩阵中的第i行第j列上的那个元素是否为零 在邻接表表示中，需扫描第i个边表，最坏情况下要耗费O(n)时间
求边的数目 必须检测整个矩阵，所耗费的时间是O(n2) 与e的大小无关 只要对每个边表的结点个数计数即可求得e，所耗费的时间，是O(e+n)。当e≤n2时，采用邻接表表示更节省空间。

图的算法

深度优先遍历

图的遍历概念

1、图的遍历

和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。 深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。

注意：以下假定遍历过程中访问顶点的操作是简单地输出顶点。

2、布尔向量visited[0．．n-1]的设置

图中任一顶点都可能和其它顶点相邻接。在访问了某顶点之后，又可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一布尔向量visited[0．．n-1]，其初值为假，一旦访问了顶点Vi之后，便将visited[i]置为真。

深度优先遍历(Depth-First Traversal)

1．图的深度优先遍历的递归定义

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，则深度优先遍历可定义如下：首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

2、深度优先搜索的过程

设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x 之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。

3、深度优先遍历的递归算法

邻接表表示的深度优先搜索算法

typedef enum{FALSE，TRUE} Boolean; //FALSE为0，TRUE为1
Boolean visited[MaxVertexNum]; //访问标志向量是全局量

//以vi为出发点对邻接表表示的图G进行深度优先搜索
void DFS(ALGraph *G，int i){
    EdgeNode *p;
    printf("visit vertex:%c", G->adjlist[i].vertex);
    visited[i]=TRUE;
    for(p = G->adjlist[i].firstedge; p!=NULL; p=p->next){
      if (!visited[p->adjvex])
        DFS(G, p->adjvex);
    }
}//DFS

邻接矩阵表示的深度优先搜索算法

//以vi为出发点对邻接矩阵表示的图G进行DFS搜索，设邻接矩阵是0,l矩阵
void DFSM(MGraph *G, int i) {
    int j;
    printf("visit vertex:%c", G->vexs[i]);
    visited[i] = TRUE;
    for(j = 0; j < G->n; j++)
        if(G->edges[i][j]==1 && !visited[j])
            DFSM(G，j);
}

深度优先遍历算法

//深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同
void DFSTraverse(ALGraph *G) {
    int i;
    for(i=0;i<G->n;i++)
        visited[i]=FALSE; //标志向量初始化
    for(i=0;i<G->n;i++)
        if(!visited[i]) //vi未访问过
            DFS(G,i); //以vi为源点开始DFS搜索
}

注意：遍历操作不会修改图G的内容，故上述算法中可将G定义为ALGraph或MGraph类型的参数，而不一定要定义为ALGraph和MGraph的指针类型。但基于效率上的考虑，选择指针类型的参数为宜。

深度优先遍历序列

对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或简称为DFS序列。

一个图的DFS序列不一定惟一：当从某顶点x出发搜索时，若x的邻接点有多个尚未访问过，则我们可任选一个访问之。

【例】对连通图G7用邻接矩阵表示时，以v0为初始出发点的 DFS遍历过程如下图(a)所示，具体算法的执行过程。DFS序列是v0，v1，v2，v5，v4，v6，v3，v7

dfs

算法分析

对于具有n个顶点和e条边的无向图或有向图，遍历算法DFSTraverse对图中每顶点至多调用一次DFS或DFSM。从DFSTraverse中调用DFS(或DFSM)及DFS(或DFSM)内部递归调用自己的总次数为n。

当访问某顶点vi时，DFS(或DFSM)的时间主要耗费在从该顶点出发搜索它的所有邻接点上。用邻接矩阵表示图时，其搜索时间为O(n)；用邻接表表示图时，需搜索第i个边表上的所有结点。因此，对所有n个顶点访问，在邻接矩阵上共需检查n2个矩阵元素，在邻接表上需将边表中所有O(e)个结点检查一遍。

所以，DFSTraverse的时间复杂度为O(n2) （调用DFSM）或0(n+e)（调用DFS）。

非递归实现

void DFS(ALGraph *g, int i) {
    EdgeNode *p;
    Stack s;
    init_stack(&s);
    push(&s, i);
    while(!empty(&s)) {
        i = pop(&s);
        if(!visited[i]) {
            printf("visit vertex:%c", g->adjlist[i].vertex);
            visited[i]=TRUE;
        }
        for(p = g->adjlist[i].firstedge; p!=NULL; p=p->next){
            if (!visited[p->adjvex])
                push(&s, p->adjvex);
        }
    }
}

广度优先遍历

// 以vk为源点对用邻接表表示的图G进行广度优先搜索
void BFS(ALGraph*G, int k) {
    Queue Q;
    InitQueue(&Q);
    printf("visit vertex: %e", G->adjlist[k].vertex);
    visited[k]=TRUE;
    EnQueue(&Q, k);                 //vk已访问，将其人队。（实际上是将其序号人队）
    while(!QueueEmpty(&Q)){         //队非空则执行
        int i = DeQueue(&Q);              //相当于vi出队
        EdgeNode *p = G->adjlist[i].firstedge;  //取vi的边表头指针
        while(p){                   //依次搜索vi的邻接点vj(令p->adjvex=j)
            if(!visited[p->adivex]){ //若vj未访问过
              printf("visitvertex: %c", C->adjlistlp->adjvex].vertex); //访问vj
              visited[p->adjvex]=TRUE;
              EnQueue(&Q, p->adjvex); //访问过的vj人队
            }
            p=p->next; //找vi的下一邻接点
        }
    }
}
void BFSM(MGraph *G, int k)
{
   Queue Q;
   InitQueue(&Q);
   printf("visit vertex：%c", G->vexs[k]); //访问源点vk
   visited[k]=TRUE;
   EnQueue(&Q, k);
   while(!QueueEmpty(&Q)){
      int i=DeQueue(&Q), j;
      for(j=0; j<G->n; j++) {                         //依次搜索vi的邻接点vj
          if(G->edges[i][j]==1&&!visited[j]){          //vi未访问
              printf("visit vertex：%c", G->vexs[j]); //访问vi
              visited[j]=TRUE;
              EnQueue(&Q, j); //访问过的vi人队
          }
      }
   }
}

最小生成树

自由树就是一个无回路的连通图（没有确定根）(在自由树中选定一顶点做根，则成为一棵通常的树)。

从根开始，为每个顶点(在树中通常称作结点)的孩子规定从左到右的次序，则它就成为一棵有序树。

如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树(SpanningTree)。

生成树是连通图的包含图中的所有顶点的极小连通子图。

图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。

最小生成树：对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作:\[W(T)=\sum_{(u,v)\in TE}w(u,v)\]。这里:TE表示T的边集，w(u，v)表示边(u，v)的权。

权最小的生成树称为G的最小生成树(Minimum SpanningTree)。最小生成树可简记为MST。

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

mst

普里姆(Prim)算法：T=(U，TE)是存放MST的集合。①T的初值是({r}，￠)，即最小生成树初始时只有一个红点r，没有红边。②T经过n-1次如下步骤操作，最后得到一棵含n个顶点，n-1条边的最小生成树。 1. 选择紫边集中一条轻边并扩充进T 1. 将轻边连接的蓝点改红点 1. 将轻边改红边 1. 修改紫边集

该算法的时间复杂度为O(n2)

克鲁斯卡尔(Kruskal)算法:①T的初始状态:只有n个顶点而无边的森林T=(V，￠ )②按边长递增的顺序选择E中的n-1安全边(u，v)并加入T，生成MST

注意：安全边指两个端点分别是森林T里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树。因为每一次添加到T中的边均是当前权值最小的安全边，MST性质也能保证最终的T是一棵最小生成树。

该算法的时间复杂度为O(eloge)。

最短路径

单源最短路径问题 (Single-Source Shortest-PathsProblem)：已知有向带权图(简称有向网)G=(V，E)，找出从某个源点s∈V到V中其余各顶点的最短路径。

迪杰斯特拉(Dijkstra)算法：由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法。

  1. 把图中所有顶点分成两组，第一组包括已确定最短路径的顶点，记为集合S；第二组包括尚未确定最短路径的顶点，记为V-S。
  2. 初始化：S集合包含起点s，V-S包含其余所有节点
  3. 在V-S中选择一个确定最短距离的点来扩充S。
  4. 当V-S中仅剩下最短距离为∞的点，或者所有V-S中的顶点已扩充到S中时，s到所有顶点的最短路径就求出来了，否则重复前一步。
  5. 设置一个向量D[0．．n-1]，对于每个v∈ V-S，用D[v]记录从源点s到达v且除v外中间不经过任何V-S中的点(若有中间点，则必为S中的点)的“最短”路径长度（简称估计距离）
  6. 若k是V-S集中估计距离最小的顶点，则k的估计距离就是最短距离
  7. 初始时，每个v ∈ V-S的D[v]值应为边<s, v>的权。
  8. 将k扩充到S集后，剩余V-S集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离：
  9. 对于任意的j ∈ V-S ，若k加入S后使D[j]变小，则必定是由于存在一条从s到j且包含k的更短路径：P=<s，…，k，j>。且D [j]减小的新路径P只可能是由于路径<s，…，k>和边<k，j>组成。所以，当D[k]+<k, j>小于D[j]时，应该用D[k]+<k, j>的长度来修改D[j]的值。
void dijkstra(MatrixGraph *g, int s, int distance[], int path[]) {
    int flag[MAX];
    int i;
    for(i = 0; i < g->n; i++) {
        flag[i] = 0;
        distance = g->edge[s][i];
        path[i] = s;
    }
    flag[s] = 1;
    distance[s] = 0;
    path[s] = -1;
    for(i = 0; i < g->n-1; i++) {
        int min = MAX_INT, min_index = -1, k;
        for(k = 0; k < g->n; k++) {
            if(flag[k]==0 && distance[k] < min ) {
                min = distance[k];
                min_index = k;
            }
        }
        if(min_index == -1) break;
        flag[min_index] = 1;
        for(k = 0; k < g->n; k++) {
            if(flag==0 && distance[min_index] + g->edge[min_index][k] < distance[k]) {
                distance[k] = distance[min_index] + g->edge[min_index][k];
                path[k] = min_index;
            }
        }
    }
}

所有顶点对间最短路径问题

Floyd算法

void floyd(MatrixGraph *g, int distance[MAX][MAX]) {
   int i, j, k;
   for(i = 0; i < g->n; i++) {
      for(j = 0; j < g->n; j++) {
         distance[i][j] = g->edge[i][j];
      }
   }
   for(k = 0; k < g->n; k++) {
      for(i = 0; i < g->n; i++) {
         for(j= 0; j < g->n; j++) {
             if(distance[i][j] > distance[i][k] + distance[k][j])
                distance[i][j] = distance[i][k] + distance[k][j];
         }
      }
   }
}

拓扑排序

拓扑排序Topological Sort：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。

这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。

  • 若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。
  • 若图中存在有向环，则不可能使顶点满足拓扑次序。
  • 一个DAG的拓扑序列通常表示某种方案切实可行。 　【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。
  • 一个DAG可能有多个拓扑序列。 　【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。
  • 当有向图中存在有向环时，拓扑序列不存在 【例】下面(a)图中的有向环重排后如(b)所示，有向边<v3，vl>和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。

无前趋的顶点优先的拓扑排序方法：该方法的每一步总是输出当前无前趋(即人度为零)的顶点，其抽象算法可描述为：

    NonPreFirstTopSort(G){//优先输出无前趋的顶点
      while(G中有人度为0的顶点)do{
       从G中选择一个人度为0的顶点v且输出之；
       从G中删去v及其所有出边；
       }
      if(输出的顶点数目<|V(G)|)
        //若此条件不成立，则表示所有顶点均已输出，排序成功。
        Error("G中存在有向环，排序失败！")；
     }
  • 无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的入度，可保存各顶点当前的入度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点：在开始排序前，扫描对应的存储空间，将入度为零的顶点均入栈(队)。以后每次选人度为零的顶点时，只需做出栈(队)操作即可。
int TopSort(AdjList *g, int sort[]) {
   int i;
   int indegree[MAX];
   EdgeNode *e;
   stack s;
   int count = 0;

   for(i = 0; i < g->n; i++) {
      indegree[i] = 0;
   }
   for(i = 0; i < g->n; i++) {
      e = g->vertex[i].firstedge;
      while(e!=NULL) {
          indegree[i]++;
          e=e->next;
      }
   }
   for(i = 0; i < g->n; i++)
      if(indegree[i] == 0)
          push(&s, i);


   while(!empty(&s)) {
      i = pop(&s);
      sort[count++] = i;;
      e = g->vertex[i].firstedge;
      while(e != 0) {
         indegree[e->adjvex]--;
         if(indegree[e->adjvex] == 0)
             push(&s, e->adjvex);
         e = e->next;
      }
   }
   return count;
}

关键路径