数据结构-图的应用

最小生成树（最小代价树）

对于一个带权连通无向图G=(V,E)，生成树不同，每棵树的权（即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树(Minimum-Spanning-Tree, MST)。

• 最小生成树可能有多个，但边的权值之和总是唯一且最小的

• 最小生成树的边数=顶点数一1。砍掉一条则不连通，增加一条边则会出现回路

• 如果一个连通图本身就是―棵树，则其最小生成树就是它本身

• 只有连通图才有生成树，非连通图只有生成森林

Prim算法（普里姆）

Prim 算法（普里姆):
从某一个顶点开始构建生成树;
每次将代价最小的新顶点纳入生成树，
直到所有顶点都纳入为止。


3+5+1+4+2=15

时间复杂度：O(|V|2次方）
适合用于边稠密图

Kruskal算法（克鲁斯卡尔）

Kruskal算法(克鲁斯卡尔)
每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)
直到所有结点都连通

时间复杂度：O(|E|log|E|)
适合用于边稀疏图

Prim算法的实现思想

更新还没加入的各个顶点的lowCast值

第二轮：

更新还没加入的各个顶点的lowCast值


第3轮：


第4轮：


第5轮：

Kruskal算法的实现思想

初始︰将各条边按权值排序

第1轮:检查第1条边的两个顶点是否连通(是否属于同一个集合)
第2轮︰检查第2条边的两个顶点是否连通(是否属于同一个集合)
第3轮︰检查第3条边的两个顶点是否连通(是否属于同一个集合)
第4轮︰检查第4条边的两个顶点是否连通(是否属于同一个集合)
第5轮︰检查第5条边的两个顶点是否连通(是否属于同一个集合)
…
每轮判断两个顶点是否属于同一集合

最短路径问题

“G港”是个物流集散中心，经常需要往各个城市运东西，怎么运送距离最近？
–单源最短路径问题
各个城市之间也需要互相往来，相互之间怎么走距离最近？
–每对顶点间的最短路径

单源最短路径–BFS算法（无权图）、Dijkstra算法（带权图、无权图）
各顶点间的最短路径–Floyd算法（带权图、无权图）

BFS求无权图的单源最短路径

bool visited[MAX_VERTEX_NUM];//访问标记数组
//广度优先遍历
void BFS(Graph G,int v){//从顶点v出发，广度优先遍历图G
	visit(v);			//访问初始顶点v
    visited[v]=TRUE;	//对v做已访问标记
    Enqueue(Q,v);		//顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);	//顶点v出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            //检测v所有邻接点
            if(!visited[w]){	//w为v的尚未访问的邻接顶点
                visit(w);		//访问顶点w
                visited[w]=TRUE;//对w做已访问标记
                EnQueue(Q,w);	//顶点w入队列
            }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int v){//从顶点v出发，广度优先遍历图G
	//d[i]表示从v到i结点的最短路径
    for(i=0;i<G.vexnum;++i){
        d[i]=∞; //初始化路径长度
        path[i]=-1;//最短路径从哪个顶点过来
    }
    d[u]=0;
    visited[v]=TRUE;	//对v做已访问标记
    Enqueue(Q,v);		//顶点v入队列Q
    while(!isEmpty(Q)){
        DeQueue(Q,v);	//顶点v出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            //检测v所有邻接点
            if(!visited[w]){	//w为v的尚未访问的邻接顶点
                d[w]=d[v]+1；	//路径长度加1
                path[w]=u;		//最短路径应从v到w
                visited[w]=TRUE;//对w做已访问标记
                EnQueue(Q,w);	//顶点w入队列
            }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最短路径问题-Dijkstra算法

Dijkstra算法



检查所有邻接自Vi的顶点，若其final值为false，则更新dist和path信息

检查所有邻接自Vi的顶点，若其final值为false，则更新dist和path信息




V0到V2的最短（带权）路径长度为：dist[2]=9
通过path[ ]可知，V0到V2的最短（带权）路径：V0->V4->V1->V2
Dijkstra算法不适用于有负权值的带权图

最短路径-Floyd算法

Floyd算法：求出每一对顶点之间的最短路径



#0：若允许在V0中转，最短路径是？


#1：若允许在V0、V1中转，最短路径是？


#2：若允许在V0、V1、V2中转，最短路径是？



Floyd算法核心代码

//....准备工作，根据图的信息初始化矩阵A和path
for(int k=0;k<n;k++){		//考虑以Vk作为中转点
	for(int i=0;i<n;i++){	//遍历整个矩阵，i为行号，j为列号
        for(int j=0;j<n;j++){
            if(A[i][j]>A[i][k]+A[k][j]){//以Vk为中转点的路径更短
                A[i][j]=A[i][k]+A[k][j];//更新最短路径长度
                path[i][j]=k;			//中转点
            }、
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

Floyd算法不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径

有向无环图描述表达式

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图

Step4:从底向上逐层检查同层的运算符是否可以合体

拓扑排序

AOV网
AOV网（Activity On Vertex NetWork，用顶点表示活动的网）
用DAG网（有向无环图）表示一个工程。顶点表示活动，有向边表示活动Vi必须先语活动Vj进行

拓扑排序

拓扑排序的实现：
1：从AOV网中选择一个没有前驱（入度为0）的顶点并输出
2：从网中删除该顶点和所有以它为起点的有向边
3：重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止

#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode{  //边表结点
	int adjvex;		//该弧所指向的顶点的位置
    struct ArcNode *nextarc;	//指向下一条弧的指针
}ArcNode;
typedef struct VNode{	//顶点表结点
	VertexType data;	//顶点信息
    ArcNode *firstarc;	//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
    AdjList vertices;	//邻接表
    int vexnum,arcnum;	//图的顶点数和弧数
}Graph;		//Graph是以邻接表存储的图类型
bool TopologicalSort(Graph G){
	InitStack(S);	//初始化栈，存储入度为0的顶点
    for(int i=0;i<G.vexnum;i++)
        if(indegree[i]==0)
            Push(S,i);	//将所有入度为0的顶点进栈
    int count=0;		//计数，记录当前已经输出的顶点数
    while(!isEmpty(S)){	//栈不空，则存在入度为0的顶点
        Pop(S,i);	//栈顶元素出栈
        print[count++]=i;	//输出顶点i
        for(p=G.vertices[i].firstarc;p;p=p->nextarc){
        	//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈s
            v=p->adjvex;
            if(!(--indegree[v]))
                Push(S,v);	//入度为0，则入栈
        }
    }
    if(count<G.vexnum)
        return false;	//排序失败，有向图中有回路
    else 
        return true;	//拓扑排序成功
}
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

逆拓扑排序的实现（DFS算法）

void DFSTraverse(Graph G){	//对图G进行深度优先遍历
	for(v=0;v<G.vexnum;++v)	
        visited[v]=FALSE;	//初始化已访问标记数据
    for(v=0;v<G.vexnum;++v)	//本代码中是从v=0开始遍历
        if(!visited[v])
            DFS(G,v);
}
void DFS(Graph G,int v){//从顶点v出发，深度优先遍历图G
	visited[v]=TRUE;	//设已访问标记
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w))
        if(!visited[w]){	//w为u的尚未访问的邻接顶点
        DFS(G,w);
        }
    print(v);//输出顶点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

关键路径

AOE网
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网（Activity On Edge NetWork）

AOE网具有以下两个性质：
1：只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始
2：只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
另外，有些活动是可以并行进行的。

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动
完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长

求关键路径的步骤

求所有事件的最早发生时间

求所有事件的最迟发生时间

求所有活动的最早发生时间

求所有活动的最迟发生时间

求所有活动的时间余量

关键活动：a2、a5、a7
关键路径：V1->V3->V4->V6
关键活动、关键路径的特性
若关键活动耗时增加，则整个过程的工期将增长
缩短关键活动的时间，可以缩短整个工程的工期
当缩短到一定程度时，关键活动可能会变成非关键活动
可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动 才能达到缩短工期的目的