数据结构

谁借莪１个温暖的怀抱￠ 2022-05-14 01:37 158阅读 0赞

提示：以下内容不适合零基础人员，仅供笔者复习之用。

# 一、图的相关定义 #

**        图**是由顶点的有穷非空集合和顶点之间边的集合组成， 通常表示为: G（V，E）， 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

*  线性结构中，元素仅有**线性关系**，每个元素只有一个直接前驱和直接后继；
 *  树形结构中，数据元素（结点）之间有着明显的**层次关系**，每层上的元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关；
 *  图形结构中，数据元素（顶点）之间具有**任意关系**，图中任意两个数据元素之间都可能相关。

无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对(Vi，Vj) 来表示。如下左图，G= (V1,\{E1\})，其中顶点集合V1=\{A，B，C，D\}; 边集合E1=\{ (A,B) ，（B,C），(C,D)， (D,A) ,  (A,C) \} 。

有向边：若从顶点Vi 到Vj的边有方向，则称这条边为有向边，也称为**弧**。用有序偶〈Vi,Vj>来表示， Vi称为弧尾， Vj称为弧头。 如果图中任意两个顶点之间的边都是有向边，则称该图为**有向图。** 连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，<A,  D>表示弧，注意不能写成<D， A>。如下右图，G= (V2,\{E2\})，其中顶点集合V2=\{A，B，C，D\}; 弧集合E2=\{<A，D>，<B，A>，<C，A>，<B，C>\}。

![20170613150633087][]

在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为**简单图**。目前讨论的都是简单图。在无向图中，如果任意两个顶点之间都存在边，则称该图为**无向完全图**。含有n个顶点的无向完全图有**n\*(n-1)/2**条边。在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为**有向完全图**。含有n个顶点的有向完全图有**n\* (n-1)** 条边。

有很少条边或弧的图称为**稀疏图**，反之称为**稠密图**，这里的概念是相对而言的。

有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做**权**。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为**网**。如下图就是一张带权的图，即标识中国四大城市的直线距离的网，此图中的权就是两地的距离。

![20170613163334984][]

假设有两个图G= (V，\{E\})和G'= (V'，\{E'\})，如果V'是V的子集，且E'是E的子集，则称G'为G的**子图**。如下图带底纹的图均为左侧无向图与有向图的子图。

![20170613163743381][]

对于无向图G= (V,\{E\})， 如果边(v,v')属于E， 则称顶点v和v‘互为**邻接点**，即v和v'相邻接、边(v,v')依附于顶点v和v'，或者说(v,v')与顶点v和v'**相关联**。 顶点v的**度**是和v相关联的边的数目，记为TD(v)。如上图左侧上方的无向图，顶点A与B 互为邻接点，边(A，B) 依附于顶点A 与B 上，顶点A 的度为3。而此图的边数是5，各个顶点度的和=3+2+3+2=10，推敲后发现，边数其实就是各顶点度数和的一半，多出的一半是因为重复两次计数。

对于有向图G= (V,\{E\})，如果弧<v,v'>属于E，则称顶点v邻接到顶点v'，顶点v'邻接自顶点v的弧<v,v'>和顶点v， v'相关联。以顶点v为头的弧的数自称为v的**入度** ，记为ID (v); 以v为尾的弧的数目称为v的**出度**，记为OD (v); 顶点v的**度为TD(v)  =ID(v)  +OD (v)**。上图 左侧下方的有向图，顶点A的入度是2 (从B到A的弧，从C到A的弧)，出度是1 (从A到D的弧)，所以顶点A 的度为2+1=3。此有向图的弧有4 条，而各顶点的出度和=1+2+1+0=4，各顶点的入度和=2+0+1+1=4。  
        从顶点v 到顶点v'的**路径**是一个顶点序列。**路径的长度**是路径上的边或弧的数目。有向图的路径也是有向的。第一个顶点到最后一个顶点相同的路径称为**回路**或**环**。 序列中顶点不重复出现的路径称为**简单路径**。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为**简单回路**或简单环。如下图，左侧的环因第一个顶点和最后一个顶点都是B，且C、 D、 A没有重复出现，因此是一个简单环。 而右侧的环，由于顶点C的重复，它就不是简单环。

![20170614151722367][]

在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。 如果对于图中任意两个顶点vi、vj ∈E， vi，和vj都是连通的，则称G是**连通图**。 下图的图1，它的顶点A到顶点B、 C、 D都是连通的，但显然顶点A与顶点E或F就无路径，因此不能算是连通图。而图2，顶点A、 B、 C、D相互都是连通的，所以它本身是连通图。

![20170614152214061][]![20170614152701170][]

无向图中的极大连通子图称为**连通分量**。注意连通分量的概念，它强调:

*  要是子图；

*  子图要是连通的；

*  连通子图含有极大顶点数；

*  具有极大顶点数的连通子图包含依附于这些顶点的**所有**边。

上图中，图1是一个无向非连通图。 但是有两个连通分量，即图2和图3。而图4，尽管是图1的子图，但是它却不满足连通子图的极大顶点数(图2满足)。 因此它不是图1的无向图的连通分量。

所谓的一个**连通图的生成树**是一个极小的连通子图， 它含有图中全部的n 个顶点，但只有足以构成一棵树的**n-1**条边。比如下图的图1是一普通图，但显然它不是生成树，当去掉两条构成环的边后，比如图2 或图3，就满足n个顶点n-1条边且连通的定义了， 它们都是一棵生成树。从这里也可知道，如果一个图有n 个顶点和小子n-1条边，则是非连通图，如果多于n-1 边条，必定构成一个环， 因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图2 和图3，随便加哪两顶点的边都将构成环。 不过有n-1条边并不一定是生成树，比如图4。

![20170614155025697][]

如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵**有向树**。对有向树的理解比较容易，所谓入度为0其实就相当于树中的根结点， 其余顶点入度为1就是说树的非根结点的双亲只有一个。一个有向图的**生成森林**由若干棵有向树组成， 含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。 如下图的图1 是一棵有向图。去掉一些弧后，它可以分解为两棵有向树，如图2和图3，这两棵就是图1有向图的生成森林。

![20170614155419620][]

# 二、图的抽象数据类型 #

![20170614164139043][]

# 三、图的存储结构 #

##     3.1 邻接矩阵 ##

**图的邻接矩阵存储方式是用两个数组来表示图**。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。设图G有n个顶点，则邻接矩阵是一个nxn的方阵，定义为:

![20170614165242433][]

如下无向图，

![20170614165336401][]

如下有向图，

![20170614165606887][]

我们知道，每条边上带有权的图叫做网，如果要将这些权值保存下来，可以采用权值代替矩阵中的0、1，权值不存在的元素之间用∞表示，如下图，左图是一个有向网图，右图就是它的邻接矩阵。

![20170614170222374][]

邻接矩阵结构：

>     #define OK 1 
>           #define ERROR 0 
>           #define TRUE 1 
>           #define FALSE 0 
>           #define MAXVEX 100 /* 最大顶点数，应由用户定义 */ 
>           #define INFINITY 65535 
>           
>           typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 
>           typedef char VertexType; /* 顶点类型应由用户定义 */ 
>           typedef int EdgeType; /* 边上的权值类型应由用户定义 */ 
>           typedef struct 
>           { 
>           VertexType vexs[MAXVEX]; /* 顶点表 */ 
>           EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵，可看作边表 */ 
>           int numNodes, numEdges; /* 图中当前的顶点数和边数 */ 
>           }MGraph;

有了这个结构定义，我们构造一个图，其实就是给顶点表和边表输入数据的过程。我们来看看无向网图的创建代码。

>     /* 建立无向网图的邻接矩阵表示 */ 
>           void CreateMGraph(MGraph *G) 
>           { 
>           int i,j,k,w; 
>           printf( "输入顶点数和边数:\n"); 
>           scanf( "%d,%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */ 
>           for(i = 0;i <G->numNodes;i++) /* 读入顶点信息,建立顶点表 */ 
>           scanf(&G->vexs[i]); 
>           for(i = 0;i <G->numNodes;i++) 
>           for(j = 0;j <G->numNodes;j++) 
>           G->arc[i][j]=INFINITY; /* 邻接矩阵初始化 */ 
>           for(k = 0;k <G->numEdges;k++) /* 读入numEdges条边，建立邻接矩阵 */ 
>           { 
>           printf( "输入边(vi,vj)上的下标i，下标j和权w:\n"); 
>           scanf( "%d,%d,%d",&i,&j,&w); /* 输入边(vi,vj)上的权w */ 
>           G->arc[i][j]=w; 
>           G->arc[j][i]= G->arc[i][j]; /* 因为是无向图，矩阵对称 */ 
>           } 
>           }

从代码中也可以得到，n 个顶点和e 条边的无向网图的创建，时间复杂度为**O(n+n^2+e)** ， 其中对邻接矩阵的初始化耗费了**O(n^2)**的时间。

##     3.2 邻接表 ##

对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的，特别是稀疏有向图。所以可以考虑用链表来按需存储。**数组与链表相结合的存储方法称为邻接表**。处理办法：

1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。  
        2. 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi 的**边表**，有向图则称为顶点vi作为弧尾的**出边表**。

如图是一个无向图的连接表结构，有向图则类似。

![20170614172659980][]

对于带权值的网图，可以在边表结点定义中再增加一个weight 的数据域，存储权值信息即可，如下图所示。

![20170614173044341][]

邻接表结点定义：

>     typedef char VertexType; /* 顶点类型应由用户定义 */ 
>           typedef int EdgeType; /* 边上的权值类型应由用户定义 */ 
>           
>           typedef struct EdgeNode /* 边表结点 */ 
>           { 
>           int adjvex; /* 邻接点域,存储该顶点对应的下标 */ 
>           EdgeType info; /* 用于存储权值,对于非网图可以不需要 */ 
>           struct EdgeNode *next; /* 链域,指向下一个邻接点 */ 
>           }EdgeNode; 
>           
>           typedef struct VertexNode /* 顶点表结点 */ 
>           { 
>           VertexType data; /* 顶点域,存储顶点信息 */ 
>           EdgeNode *firstedge; /* 边表头指针 */ 
>           }VertexNode, AdjList[MAXVEX]; 
>           
>           typedef struct 
>           { 
>           AdjList adjList; 
>           int numNodes,numEdges; /* 图中当前顶点数和边数 */ 
>           }GraphAdjList;

无向图的邻接表创建代码如下：

>     * 建立图的邻接表结构 */ 
>           void CreateALGraph(GraphAdjList *G) 
>           { 
>           int i,j,k; 
>           EdgeNode *e; 
>           printf( "输入顶点数和边数:\n"); 
>           scanf( "%d,%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */ 
>           for(i = 0;i < G->numNodes;i++) /* 读入顶点信息,建立顶点表 */ 
>           { 
>           scanf(&G->adjList[i].data); /* 输入顶点信息 */ 
>           G->adjList[i].firstedge= NULL; /* 将边表置为空表 */ 
>           } 
>           
>           
>           for(k = 0;k < G->numEdges;k++) /* 建立边表 */ 
>           { 
>           printf( "输入边(vi,vj)上的顶点序号:\n"); 
>           scanf( "%d,%d",&i,&j); /* 输入边(vi,vj)上的顶点序号 */ 
>           e=(EdgeNode *) malloc( sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */ 
>           e->adjvex=j; /* 邻接序号为j */ 
>           e->next=G->adjList[i].firstedge; /* 将e的指针指向当前顶点上指向的结点 */ 
>           G->adjList[i].firstedge=e; /* 将当前顶点的指针指向e */ 
>           
>           e=(EdgeNode *) malloc( sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */ 
>           e->adjvex=i; /* 邻接序号为i */ 
>           e->next=G->adjList[j].firstedge; /* 将e的指针指向当前顶点上指向的结点 */ 
>           G->adjList[j].firstedge=e; /* 将当前顶点的指针指向e */ 
>           } 
>           }

以上采用头插法插入。由于对于无向图，一条边对应都是两个顶点，所以在循环中，一次就针对i 和j 分别进行了插入。本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。

# 四、图的遍历 #

从图中某一顶点出发访遍图中其余顶点，且使**每一个顶点仅被访问一次**，这一过程就叫做图的遍历。

**  深度优先遍历**（DFS）：它从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v 有路径相通的顶点都被访问到。

![20170626094304258][]

如果使用邻接矩阵，代码如下：

>     Boolean visited[MAXVEX]; /* 访问标志的数组 */ 
>           
>           /* 邻接矩阵的深度优先递归算法 */ 
>           void DFS(MGraph G, int i) 
>           { 
>           int j; 
>           visited[i] = TRUE; 
>           printf( "%c ", G.vexs[i]); /* 打印顶点，也可以其它操作 */ 
>           for(j = 0; j < G.numVertexes; j++) 
>           if(G.arc[i][j] == 1 && !visited[j]) 
>           DFS(G, j); /* 对为访问的邻接顶点递归调用 */ 
>           } 
>           
>           /* 邻接矩阵的深度遍历操作 */ 
>           void DFSTraverse(MGraph G) 
>           { 
>           int i; 
>           for(i = 0; i < G.numVertexes; i++) 
>           visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */ 
>           for(i = 0; i < G.numVertexes; i++) 
>           if(!visited[i]) /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */ 
>           DFS(G, i); 
>           }

如果使用邻接表结构，其DFSTraverse 函数的代码是几乎相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下：

>     Boolean visited[MAXSIZE]; /* 访问标志的数组 */ 
>           
>           /* 邻接表的深度优先递归算法 */ 
>           void DFS(GraphAdjList GL, int i) 
>           { 
>           EdgeNode *p; 
>           visited[i] = TRUE; 
>           printf( "%c ",GL->adjList[i].data); /* 打印顶点,也可以其它操作 */ 
>           p = GL->adjList[i].firstedge; 
>           while(p) 
>           { 
>           if(!visited[p->adjvex]) 
>           DFS(GL, p->adjvex); /* 对为访问的邻接顶点递归调用 */ 
>           p = p->next; 
>           } 
>           } 
>           
>           /* 邻接表的深度遍历操作 */ 
>           void DFSTraverse(GraphAdjList GL) 
>           { 
>           int i; 
>           for(i = 0; i < GL->numVertexes; i++) 
>           visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */ 
>           for(i = 0; i < GL->numVertexes; i++) 
>           if(!visited[i]) /* 对未访问过的顶点调用DFS,若是连通图,只会执行一次 */ 
>           DFS(GL, i); 
>           }

对比两个不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的邻接点需要访问矩阵中的所有元素，因此都需要O(n^2)的时间。 而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然**对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高**。

**广度****优先遍历**（BFS）：如果说图的深度优先遍历类似树的前序遍历， 那么图的广度优先遍历就类似于树的层序遍历了。

![20170626104825629][]

以下是邻接矩阵结构的广度优先遍历算法：

>     /* 邻接矩阵的广度遍历算法 */ 
>           void BFSTraverse(MGraph G) 
>           { 
>           int i, j; 
>           Queue Q; 
>           for(i = 0; i < G.numVertexes; i++) 
>           visited[i] = FALSE; 
>           InitQueue(&Q); /* 初始化一辅助用的队列 */ 
>           for(i = 0; i < G.numVertexes; i++) /* 对每一个顶点做循环 */ 
>           { 
>           if (!visited[i]) /* 若是未访问过就处理 */ 
>           { 
>           visited[i]=TRUE; /* 设置当前顶点访问过 */ 
>           printf( "%c ", G.vexs[i]); /* 打印顶点，也可以其它操作 */ 
>           EnQueue(&Q,i); /* 将此顶点入队列 */ 
>           while(!QueueEmpty(Q)) /* 若当前队列不为空 */ 
>           { 
>           DeQueue(&Q,&i); /* 将队对元素出队列，赋值给i */ 
>           for(j= 0;j<G.numVertexes;j++) 
>           { 
>           /* 判断其它顶点若与当前顶点存在边且未访问过 */ 
>           if(G.arc[i][j] == 1 && !visited[j]) 
>           { 
>           visited[j]=TRUE; /* 将找到的此顶点标记为已访问 */ 
>           printf( "%c ", G.vexs[j]); /* 打印顶点 */ 
>           EnQueue(&Q,j); /* 将找到的此顶点入队列 */ 
>           } 
>           } 
>           } 
>           } 
>           } 
>           }

对于邻接表的广度优先遍历，代码与邻接矩阵差异不大，代码如下。

>     /* 邻接表的广度遍历算法 */ 
>           void BFSTraverse(GraphAdjList GL) 
>           { 
>           int i; 
>           EdgeNode *p; 
>           Queue Q; 
>           for(i = 0; i < GL->numVertexes; i++) 
>           visited[i] = FALSE; 
>           InitQueue(&Q); 
>           for(i = 0; i < GL->numVertexes; i++) 
>           { 
>           if (!visited[i]) 
>           { 
>           visited[i]=TRUE; 
>           printf( "%c ",GL->adjList[i].data); /* 打印顶点,也可以其它操作 */ 
>           EnQueue(&Q,i); 
>           while(!QueueEmpty(Q)) 
>           { 
>           DeQueue(&Q,&i); 
>           p = GL->adjList[i].firstedge; /* 找到当前顶点的边表链表头指针 */ 
>           while(p) 
>           { 
>           if(!visited[p->adjvex]) /* 若此顶点未被访问 */ 
>           { 
>           visited[p->adjvex]=TRUE; 
>           printf( "%c ",GL->adjList[p->adjvex].data); 
>           EnQueue(&Q,p->adjvex); /* 将此顶点入队列 */ 
>           } 
>           p = p->next; /* 指针指向下一个邻接点 */ 
>           } 
>           } 
>           } 
>           } 
>           }

对比图的深度优先遍历与广度优先遍历算法，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点访问的顺序不同。不过如果图顶点和边非常多，不能在短时间内遍历完成，遍历的目的是为了寻找合适的顶点，那么选择哪种遍历就要仔细斟酌了。深度优先更适合目标比较明确，以找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

# 五、图的应用 #

##     5.1 最小生成树 ##

如下图是个带权值的网结构图。要用最小的成本将所有元素连接起来，即n个顶点，用n-1条边把连通图连接起来，并且使得权值的和最小。定义：把**构造连通网的最小代价生成树称为最小生成树**。这里介绍两种经典算法。

![20170627154736285][]

5.1.1 普利姆（Prim）算法

定义：假设N= (P，\{E\}) 是连通网，TE 是N 上最小生成树中边的集合。算法从U=\{u0\}(u0∈V)，  TE=\{ \}开始。重复执行下述操作：在所有u∈U，v∈V-U的边(u，v)∈E 中找一条代价最小的边(u0，v0) 并入集合TE，同时v0并入U，直至U=V为止。 此时TE中必有n-1条边，则T= (V,\{TE\}) 为N的最小生成树。

核心代码：（先将图构造成一个邻接矩阵G）

>     /* Prim算法生成最小生成树 */ 
>           void MiniSpanTree_Prim(MGraph G) 
>           { 
>           int min, i, j, k; 
>           int adjvex[MAXVEX]; /* 保存相关顶点下标 */ 
>           int lowcost[MAXVEX]; /* 保存相关顶点间边的权值 */ 
>           lowcost[ 0] = 0; /* 初始化第一个权值为0，即v0加入生成树 */ 
>           /* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */ 
>           adjvex[ 0] = 0; /* 初始化第一个顶点下标为0 */ 
>           for(i = 1; i < G.numVertexes; i++) /* 循环除下标为0外的全部顶点 */ 
>           { 
>           lowcost[i] = G.arc[ 0][i]; /* 将v0顶点与之有边的权值存入数组 */ 
>           adjvex[i] = 0; /* 初始化都为v0的下标 */ 
>           } 
>           for(i = 1; i < G.numVertexes; i++) 
>           { 
>           min = INFINITY; /* 初始化最小权值为∞， */ 
>           /* 通常设置为不可能的大数字如32767、65535等 */ 
>           j = 1;k = 0; 
>           while(j < G.numVertexes) /* 循环全部顶点 */ 
>           { 
>           if(lowcost[j]!= 0 && lowcost[j] < min) /* 如果权值不为0且权值小于min */ 
>           { 
>           min = lowcost[j]; /* 则让当前权值成为最小值 */ 
>           k = j; /* 将当前最小值的下标存入k */ 
>           } 
>           j++; 
>           } 
>           printf( "(%d, %d)\n", adjvex[k], k); /* 打印当前顶点边中权值最小的边 */ 
>           lowcost[k] = 0; /* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */ 
>           for(j = 1; j < G.numVertexes; j++) /* 循环所有顶点 */ 
>           { 
>           if(lowcost[j]!= 0 && G.arc[k][j] < lowcost[j]) 
>           { /* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */ 
>           lowcost[j] = G.arc[k][j]; /* 将较小的权值存入lowcost相应位置 */ 
>           adjvex[j] = k; /* 将下标为k的顶点存入adjvex */ 
>           } 
>           } 
>           } 
>           }

由算法代码中的循环嵌套可得知此算法的时间复杂度为**O(n^2)**。 由此得出的上述依次顺序加入的带权值边为：（0-1）、（0-5）、（1-8）、（8-2）、（1-6）、（6-7）、（7-4）、（7-3）。

5.1.2 克鲁斯卡尔（Kruskal）算法

![20170627154809088][]

普里姆(Prim) 算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的。事实上，可以直接以边为目标去构建，因为权值是在边上，直接去找最小权值的边来构建生成树也是很自然的想法， 只不过构建时要考虑是否会形成环路而已。此时我们就用到图的存储结构中的**边集数组**结构。我们可以通过将Prim算法中的邻接矩阵转化为上图右边的边集数组，并对它们按权值大小排序。

定义：假设N= (V，\{E\})是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=\{V，\{ \}\}，图中每个顶点自成一个连通分量。在E 中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。

>     typedef struct 
>           { 
>           int begin; 
>           int end; 
>           int weight; 
>           }Edge; /* 对边集数组Edge结构的定义 */ 
>           
>           /* 生成最小生成树 */ 
>           void MiniSpanTree_Kruskal(MGraph G) 
>           { 
>           int i, j, n, m; 
>           int k = 0; 
>           int parent[MAXVEX]; /* 定义一数组用来判断边与边是否形成环路 */ 
>           
>           Edge edges[MAXEDGE]; /* 定义边集数组,edge的结构为begin,end,weight,均为整型 */ 
>           
>           /* 用来构建边集数组并排序********************* */ 
>           for ( i = 0; i < G.numVertexes -1; i++) 
>           { 
>           for (j = i + 1; j < G.numVertexes; j++) 
>           { 
>           if (G.arc[i][j]<INFINITY) 
>           { 
>           edges[k].begin = i; 
>           edges[k].end = j; 
>           edges[k].weight = G.arc[i][j]; 
>           k++; 
>           } 
>           } 
>           } 
>           sort(edges, &G); 
>           /* ******************************************* */ 
>           
>           
>           for (i = 0; i < G.numVertexes; i++) 
>           parent[i] = 0; /* 初始化数组值为0 */ 
>           
>           printf( "打印最小生成树：\n"); 
>           for (i = 0; i < G.numEdges; i++) /* 循环每一条边 */ 
>           { 
>           n = Find(parent,edges[i].begin); 
>           m = Find(parent,edges[i].end); 
>           if (n != m) /* 假如n与m不等，说明此边没有与现有的生成树形成环路 */ 
>           { 
>           parent[n] = m; /* 将此边的结尾顶点放入下标为起点的parent中。 */ 
>           /* 表示此顶点已经在生成树集合中 */ 
>           printf( "(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight); 
>           } 
>           } 
>           }

此算法的Find函数由边数e决定，时间复杂度为O(loge)，而外面有一个for循环e次。 所以克鲁斯卡尔算法的时间复杂度为O(eloge)。对比两个算法，**克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势； 而普里姆算法对于稠密图，即边数非常多的情况会更好一些**。

相比之下，普里姆算法像是走一步看一步的思维方式，逐步生成最小生成树。而克鲁斯卡尔算法则更有全局意识，直接从图中最短权值的边入手，找寻最后的答案。

##     5.2 最短路径 ##

对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。关于最短路径主要有两种算法，迪杰斯特拉(**Dijkstra**) 算法和弗洛伊德(**Floyd**) 算法。

Dijkstra算法将间隔一个（或多个）顶点的远距离路径问题转化为一步步求出它们之间顶点的最短路径问题，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到某个源点到任一顶点的最短路径和路径长度，所以，**Dijkstra算法解决了从某个源点到其余各顶点的最短路径问题**。实现过程需要双重嵌套，**时间复杂度为O(n^2)，**需要指出的是，求源点到某一特定终点的最短路径和求源点到其他所有顶点的最短路径一样复杂。当然，在此基础上，如果想要知道任意顶点到其余所有顶点的最短路径，简单的办法就是，对每个顶点当做源点运行一次Dijkstra算法，等于在双重循环基础上再来一次循环，此时，时间复杂度就变为**O(n^3)**了。

Floyd算法则是采用动态规划算法求解问题。基本思想是：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。所以，**Floyd算法解决了所有顶点到所有顶点的最短路径问题**。相比之下，**Floyd算法的时间复杂度为O(n^3)，空间复杂度是O(n^2)**，算法优点是，可以算出任意两点间的最短路径，代码编写也较简单。缺点是，时间复杂度比较高，不太适合大量数据的计算。值得注意的是，Floyd算法需要借助两个邻接矩阵分别记录顶点间的权值和顶点间的路径，对矩阵的遍历及修改较为频繁，因此，比较适合稠密图的计算。

关于这两种算法不做其他详细介绍，有需要的读者参考其他文章。

##     5.3 拓扑排序    ##

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。AOV网中的弧表示活动之间存在的某种制约关系，且不能存在回路。 设G=(V，E)是一个具有n个顶点的有向图， V中的顶点序列v1，v2，……， vn, 满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。 则称这样的顶点序列为一个**拓扑序列**。所谓**拓扑排序**，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环(回路)的AOV网；如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是AOV网。

拓扑排序的基本思路是: 从AOV网中选择一个入度为0 的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。整个**算法的时间复杂度为O(n+e)**。

[20170613150633087]: /images/20220514/1f7c427085484b3b932f1bdf0d6d5a1b.png
[20170613163334984]: /images/20220514/e028cfdd54034e479b7b63271bfb93c6.png
[20170613163743381]: /images/20220514/1b98b32368c14e6fa1212d2634d25d1c.png
[20170614151722367]: /images/20220514/b580734cbaba4df1acb0bb728d190938.png
[20170614152214061]: https://img-blog.csdn.net/20170614152214061
[20170614152701170]: /images/20220514/e214a4bc73644f35b90841e610349001.png
[20170614155025697]: /images/20220514/9b1dde15368c4d52bc1355217043ee92.png
[20170614155419620]: /images/20220514/897a4f717e9344b2826b6cd625b764a9.png
[20170614164139043]: /images/20220514/9660d7e10b5049bfb9bc988f35089bed.png
[20170614165242433]: /images/20220514/a2f055142bac4bdbb2e56f577e05426f.png
[20170614165336401]: /images/20220514/ffec1f5edd2741e58d7df27ed6d62cb1.png
[20170614165606887]: /images/20220514/1e98f7dbae424ae69fafead566723239.png
[20170614170222374]: /images/20220514/0126d404e8ad47b9ac8d605ea2d0102a.png
[20170614172659980]: /images/20220514/f52e25446c974a589b6c0d3c9f5d63da.png
[20170614173044341]: /images/20220514/df0f69905dcf44fdbad7e6ef2ded92ee.png
[20170626094304258]: /images/20220514/b5d7323c618d47ae9f0ce7591786c140.png
[20170626104825629]: /images/20220514/ba64eebd09e140a5b10cac68e7c732a9.png
[20170627154736285]: /images/20220514/2564487be91943f1b6b44d479b50397a.png
[20170627154809088]: /images/20220514/c587fc580c0643b6b98f542cc32ea654.png