最小生成树
概念
定义：在加权连通图的所有生成树中，各边权值之和最小的生成树。
注意：（1）是无向连通图（2）最小生成树可能不唯一，但其权值之和是唯一的。
求解最小生成树的常用算法是Prim算法和Kruskal算法，都是属于贪心算法，都利用了最小生成树的MST性质。
Prim算法和Kruskal算法时间复杂度分别是O(n2)和O(eloge)
Prim算法
Prim算法是一种基于顶点的贪心算法，从起始顶点出发，每次迭代选择当前可用的最小权值边，然后把边上依附的其他顶点加入最小生成树。
Prin算法又称为“加点法”，比较适合稠密图。
算法描述如下：
G=(V,E)是一个加权连通图，T=(U,TE)是G的一颗最小生成树。
（1）最小生成树T的初始状态为U={u0},TE={}，此时图中只有一个起始顶点，边集为空。
（2）在所有u∈U，v∈V-U边中找到一条代价最小的边(u,v)，把边(u,v)并入生成树的边集TE中，同时v并入 生成树的顶点集U中。
（3）重复步骤二，直至U=V。此时TE中必有n-1条边，T=（U,TE）为G的最小生成树。
基于邻接表的Prim算法：
template <class VertexType, class EdgeType>
void adjList<VertexType, EdgeType>::prim(EdgeType noEdge) const{
struct Dist{
int adjVex; //最小代价边衣服的顶点编号
EdgeType lowCost; //最小代价
}*D=new Dist[verNum];
edgeNode *p; //p 用于遍历边
EdgeType minCost; //minCost 用于保存最小的代价
int u, i, j,count=0; //u 是当前顶点，i、j 是循环中的计数器，count 是计数器，用于记录生成树的边数。
for(i=0; i<verNum; ++i){
visited[i]=false;
D[i].lowCost=noEdge;
}
u=0; //初始化u
visited[u]=true;
for(i=1;i<verNum;++i){ //选中一个点u加入D中
for(p=verList[u].firstEdge;p!=NULL;p=p->next) //更新u关联的顶点的D值
if(!visited[p->to] && D[p->to].lowCost > p->weight){
D[p->to].lowCost=p->weight; //更新lowCost
D[p->to].adjVex=u; //更新adjVex
}
minCost=noEdge;
for(j=0;j<verNum;++j) //在V-U中找lowCost最小顶点u
if(D[j].lowCost<minCost){
minCost=D[j].lowCost;
u=j;
}
TE[count].vex1=D[u].adjVex;
TE[count].vex2=u; //保存最小生成树的一条边
TE[count++].weight=D[u].lowCost;
D[u].lowCost=noEdge; //顶点u已经=并入D中
visited[u]=true;
}
delete [] D;
}
基于邻接矩阵的Prim算法
template <class VertexType, class EdgeType>
void adjMatrix<VertexType, EdgeType>::prim(EdgeType noEdge) const{
struct Dist{
int adjVex; //最小代价边衣服的顶点编号
EdgeType lowCost; //最小代价
}*D=new Dist[verNum];
EdgeType minCost;
int u, i, j,count=0;
for(i=0; i<verNum; ++i){
visited[i]=false;
D[i].lowCost=noEdge;
}
u=0; //初始化u
visited[u]=true;
for(i=1;i<verNum;++i){ //选中一个点u加入D中
for(j=0;j<verNum;j++) //更新u关联的顶点的D值
if(!visited[j] && edges[u][j]!=noEdge){
if(edges[u][j]<D[j].lowCost){
D[j].lowCost=edges[u][j]; //更新lowCost
D[j].adjVex=u; //更新adjVex
}
}
minCost=noEdge;
for(j=0;j<verNum;++j) //在V-U中找lowCost最小顶点u
if(D[j].lowCost<minCost){
minCost=D[j].lowCost;
u=j;
}
TE[count].vex1=D[u].adjVex;
TE[count].vex2=u; //保存最小生成树的一条边
TE[count++].weight=D[u].lowCost;
D[u].lowCost=noEdge; //顶点u已经=并入D中
visited[u]=true;
}
delete [] D;
}
Kruskal算法
Kruskal算法是一种基于边的贪心算法，初始时生成树包含所有顶点，边集为空，每次迭代选择当前可用的最小权值边，且该边加入生成树的边集中不会产生环，直到所有顶点都能连通。
Kruskal算法又称为"加边法"，比较适合稀疏图。
算法描述如下：
G=(V,E)是一个加权连通图，T=(U,TE)是G的一颗最小生成树。
（1）最小生成树T的初始状态为U=V，TE={}，此时T中有图G中的所有顶点，边集为空，所以每个顶点字自成一个连通分量。
（2）在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入TE中，否则舍去此边而选择下一条代价最小边。
（3）重复步骤二，直到T中所有顶点都在同一连通分量上。
基于邻接表的Kruskal算法：
template <class VertexType, class EdgeType>
void adjList<VertexType, EdgeType>::kruskal const{
int count=0;
mstEdge e;
edgeNode *p;
unionFindSet S(verNum); //并查集S
priorityQueue<mstEdge> Q; //优先级队列Q
for(int i=0; i<verNum;++i){ //用图中的边生成优先级队列
for(p=verList[i].firstEdge;p!=NULL;p=p->next)
if(i<p->to){ //防止重复入队
e.vex1=i;
e.vex2=p->to;
e.weight=p->weight;
Q.enQueue(e); //边e入队
}
}
while(count<verNum-1){ //选出verNum-1条边
e=Q.deQueue(); //从优先级队列中出队一条边
int u=S.find(e.vex1); //查找顶点vex1所属子集
int v=S.find(e.vex2); //查找顶点vex2所属子集
if(u!=v){ //边上的两个顶点不属于同一连通分量
S.merge(u,v); //合并u、v所属子集（连通分量）
TE[count++]=e; //保存最小生成树中的一条边
}
}
}
基于邻接矩阵的Kruskal算法：
template <class VertexType, class EdgeType>
void adjList<VertexType, EdgeType>::kruskal const{
int count=0;
mstEdge e;
edgeNode *p;
unionFindSet S(verNum);
priorityQueue<mstEdge> Q;
for(int i=0; i<verNum;++i){ //用图中的边生成优先级队列
for(int j=i+1;j<verNum;j++) //从j=i+1开始，防止重复入队
if(edges[i][j]!=noEdges){
e.vex1=i;
e.vex2=j;
e.weight=edges[i][j];
Q.enQueue(e);
}
}
while(count<verNum-1){ //选出verNum-1条边
e=Q.deQueue(); //从优先级队列中出队一条边
int u=S.find(e.vex1);
int v=S.find(e.vex2);
if(u!=v){
S.merge(u,v);
TE[count++]=e;
}
}
}
有向无环图及其应用
拓扑排序
概念
AOV网络：在有向图中，用顶点表示活动或任务或任务间的优先关系。
拓扑序列：在有向无环图中，若存在顶点Vi到Vj的路径，那么在序列中顶点Vi排在顶点Vj的前面。
拓扑排序：将有向无环图的顶点按照它们之间的优先关系拍成一个拓扑序列的操作
拓扑排序可以解决先决条件问题
步骤：
（1）在有向图中任选一个入度为0的顶点并输出它。
（2）删除该顶点及该顶点的所有出边，将其邻接点的入度减1.
重复上述步骤，最后有两种可能的情况
（1）当输出了有向图的全部顶点时，排序成功。
（2）当图中还有顶点没有输出，则排序失败，说明图中含有环。
算法思想：
关键是如何找到入度为0的顶点，以及如何删除该顶点的所有出边。
（1）计算每个顶点的入度，存入inDegree数组中，然后遍历inDegree数组，将所有入度为0的顶点入队。
（2）若队列非空，从队首出队一个入度为0的顶点并输出它，将以该顶点为尾的所有邻接点的入度减1，若此时某个邻接点的入度为0，则将其入队。
（3）重复步骤二。
基于邻接表的拓扑排序算法：
template <class VertexType, class EdgeType>
bool adjList<VertexType, EdgeType>::topSort()const{
queue<int> q;
edgeNode *p;
int i,curNode,count=0;
int *intDegree = new int[verNum];
for(i=0;i<verNum;i++)
inDegree[i]=0;
for(i=0;i<verNum;i++){ //遍历边表，求顶点入度
for(p=verList[i].firstEdge;p!=p->next)
++inDegree[p->to];
}
for(i=0;i<verNum;i++)
if(inDegree[i]==0)
q.push(i); //入度为0的顶点入队列
while(!q.empty()){
curNode=q.front();
q.pop(); //出队一个入度为0的顶点
cout<<verList[curNode].vertex<<' '; //输出该顶点
topOrder[count]=curNode; //保存拓扑序列，用于求关键路径
count++;
for(p=verList[curNode].firstEdge;p!=NULL;p=p->next)
if(--inDegree[p->to]==0) //邻接点入度减1
q.push(p->to); //入度为0的顶点入队列
}
cout<<endl;
if(count==verNum) //输出全部顶点，拓扑排序成功
return true;
return false; //该有向图有环，拓扑排序失败
}
基于邻接矩阵的拓扑排序算法：
template <class VertexType, class EdgeType>
bool adjList<VertexType, EdgeType>::topSort()const{
queue<int> Q;
int i,j,curNode,count=0;
int *intDegree = new int[verNum];
for(i=0;i<verNum;i++)
inDegree[i]=0;
for(i=0;i<verNum;i++){ //遍历邻接矩阵，求顶点入度
for(j=0;j<verNum;j++)
if(edges[i][j]!=noEdge)
++inDegree[i]=0;
}
for(i=0;i<verNum;i++)
if(inDegree[i]==0)
Q.push(i); //入度为0的顶点入队列
while(!Q.empty()){
curNode=Q.front();
Q.pop(); //出队一个入度为0的顶点
cout<<vertexs[curNode]<<' '; //输出该顶点
count++; //计数器+1
for(j=0;j<verNum;++j){
if(edges[curNode][j]!=noEdge) //邻接点入度减1
if(--deDegree[j]==0)
Q.push(j); //入度为0的顶点入队列
}
}
cout<<endl;
if(count==verNum) //输出全部顶点，拓扑排序成功
return true;
return false; //该有向图有环，拓扑排序失败
}
最短路径
单源点最短路径
在一个带权有向图G=(V,E)中，每条边上的权值都是非负实数，给定顶点s∈V充当源点，计算从源点到其他各顶点的最短路径。
Dijkstra(迪杰斯特拉算法)是一种按路径长度递增的次序产生到各顶点最短路径的贪心算法。
步骤如下：
（1）初始化D、pre和visited数组，D[i]置为无穷大∞，pre[i]置为-1,visited[i]置为false.源点到自身的距离D[0]置为0，源点的前驱pre[0]置为0.
（2）从尚未确定最短路径长度的集合V-S中取出一个最短路径长度最小的顶点Vk，将Vk加入集合中，置visited[k]为ture.
（3）修改数组D中由源点s经过Vk可达的最短路径长度。若加进Vk作为中间顶点，使得源点s到Vi∈V-S的最短路径长度变短，则修改D[i]和pre[i]，即当D[i]>D[j]+weight(vk+vi)时，置D[i]=D[j]+weight(vk+vi)，pre[i]=k。
（4）重复步骤二三，直到V=S。数组D记录了从源点s到图中其他顶点的最短路径长度。
Dijkstra算法的时间复杂度O(n2)
基于邻接表的Dijkstra算法
求从源点start到其他顶点的最短路径
template <class VertexType, class EdgeType>
bool adjList<VertexType, EdgeType>::dijkstra(int start, EdgeType noEdge) const{
if (start < 0 || start > (this->verNum - 1) ) //源点下标越界
return false;
EdgeType* D = new EdgeType[this->verNum]; //记录到各顶点的最短路径的长度
int* pre = new int[this->verNum]; //
edgeNode* p;
EdgeType min;
int i;
int j;
int k;
for (i = 0;i < this->verNum;++i) {
this->visited[i] = false;
D[i] = noEdge;
pre[i] = -1;
}
D[start] = 0;
pre[start] = start;
min = D[start];
k = start;
for (i = 1;i < this->verNum;++i) {
this->visited[k] = true;
for (p = verList[k].firstEdge;p != NULL;p = p->next) {
if (!this->visited[p->to] && D[p->to] > (min + p->weight)) {
D[p->to] = min + p->weight;
pre[p->to] = k;
}
}
min = noEdge;
k = start;
for (j = 0;j < this->verNum;++j) {
if (!this->visited[j] && (D[j] < min)) {
k = j;
min = D[k];
}
}
if (k != start) {
printDijPath(start,k,pre);
cout << " : " << D[k] << endl;
}
}
delete []D;
delete []pre;
return true;
}
输出从源点from到to的最短路径上的顶点序列
template <class VertexType, class EdgeType>
void adjList<VertexType, EdgeType>::printDijPath(int from, int to, int pre[]) const{
if (from == to) {
cout << verList[from].vertex;
return;
}
printDijPath(from,pre[to],pre);
cout << "->" << verList[to].vertex ;
}
每对顶点之间的最短路径
Floyd算法步骤如下：
（1）初始化D矩阵和pre矩阵，若Vi到Vj没有弧，则D[i][j]=∞，pre[i][j]=-1 ; 若i=j,则 D[i][j]=0, pre[i][j]=i；若Vi到Vj存在弧，则 D[i][j]=weight(Vi,Vj) ，pre[i][j]=i.
（2）对于每一个顶点Vk，若 D[i][k]+D[k][j]<D[i][j] 成立,表明从Vi到Vk再到Vj的路径比原来Vi到Vj的路径短，则置D[i][j]=D[i][k]+D[k][j]，pre[i][j]=pre[k][j]
（3）将图中的n个顶点依次加入每对顶点之间进行探测，也就是对矩阵D和矩阵pre进行n次更新，最终矩阵D中记录的便是每对顶点之间的最短路径的长度。
基于邻接矩阵的Floyd算法
template <class VertexType, class EdgeType>
void adjMartrix<class VertexType, class EdgeType>::floyd() const{
EdgeType **D=new EdgeType*[verNum];
int **pre=new EdgeType*[verNum];
int i,j,k;
for(i=0;i<verNum;++i){
D[i]=new EdgeType[verNum];
pre[i]=new int[verNum];
for(j=0;j<verNum;++j){
D[i][j]=(i==j)?0:edges[i][j];
pre[i][j]=(edges[i][j]=noEdge)?-1:i;
}
}
for(k=0;k<verNum;++k)
for(i=0;i<verNum;++i)
for(j=0;j<verNum;j++)
if(D[i][j]!=noEdge && D[k][j]!=noEdges && D[i][k]+D[k][j]<D[i][j]){
D[i][j]=D[i][k]+D[k][j];
pre[i][j]=pre[k][j];
}
printFloyd(D,pre);
for(i=0;i<verNum;++i){
delete []D[i];
delete []pre[i];
}
delete []D;
delete []pre;
}
输出各顶点之间的最短路径
template <class VertexType, class EdgeType>
void adjMatrix<VertexType, EdgeType>::printFloyd(EdgeType **D, int **pre) const{
int i, j, k;
cout<<"shortest path:\n";
for(i=0;i<verNum;i++){
for(j=0;j<verNum;++j)
cout<<D[i][j]<<'\t';
cout<<endl;
}
cout<<"precurosr of vertex:\n";
for(i=0;i<verNum;++i){
for(j=0;j<verNum;++j)
cout<<pre[i][j]<<'\t';
cout<<endl;
}
}
习题：
1.判断一个有向图是否由环，除拓扑排序方法外，还可以用（）
A.深度优先遍历
B.广度优先遍历
C.求最短路径
D.求关键路径
选A。
