图的应用 专程为面试总结的
图的深度优先遍历(像前序遍历)-使用栈
图的广度优先遍历（像层次遍历）-使用队列
图的应用
拓扑排序
由偏序定义得到拓扑有序的操作便是拓扑排序。建立模型是AOV网。
拓 扑 排 序
一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
课程代号 课程名称 先修课程
C1 高等数学 无
C2 程序设计基础 无
C3 离散数学 C1,C2
C4 数据结构 C3,C5
C5 算法语言 C2
C6 编译技术 C4,C5
C7 操作系统 C4,C9
C8 普通物理 C1
C9 计算机原理 C8
图3-4 课程表
例如，假定一个计算机专业的学生必须完成图3-4所列出的全部课程。在这里，课程代表活动，学习一门课程就表示进行一项活动，学习每门课程的先决条件是学完它的全部先修课程。如学习《数据结构》课程就必须安排在学完它的两门先修课程《离散数学》和《算法语言》之后。学习《高等数学》课程则可以随时安排，因为它是基础课程，没有先修课。若用AOV网来表示这种课程安排的先后关系，则如图3-5所示。图中的每个顶点代表一门课程，每条有向边代表起点对应的课程是终点对应课程的先修课。图中的每个顶点代表一从图中可以清楚地看出各课程之间的先修和后续的关系。如课程C5的先修课为C2，后续课程为C4和C6。
|
|
|
|
|
|
图3-5 AOV网 图3-6 三个顶点的回路
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。如图3-6是一个具有三个顶点的回路，由<A,B>边可得B活动必须在A活动之后，由<B,C>边可得C活动必须在B活动之后，所以推出C活动必然在A活动之后，但由<C,A>边可得C活动必须在A活动之前，从而出现矛盾，使每一项活动都无法进行。这种情况若在程序中出现，则称为死锁或死循环，是应该必须避免的。
在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。例如，下面的三个序列都是图3-5的拓扑序列，当然还可以写出许多。
(1) C1,C8,C9,C2,C3,C5,C4,C7,C6
(2) C2,C1,C3,C5,C4,C6,C8,C9,C7
(3) C1,C2,C3,C8,C9,C5,C4,C6,C7
由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
(2) 从网中删除此顶点及所有出边。
循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。
下面以图3-7(a)为例，来说明拓扑排序算法的执行过程。
|
|
|
|
|
|
图3-7 拓扑排序的图形说明
(1) 在(a)图中v0和v1的入度都为0，不妨选择v0并输出之，接着删去顶点v0及出边<0,2>，得到的结果如(b)图所示。
(2) 在(b)图中只有一个入度为0的顶点v1，输出v1，接着删去v1和它的三条出边<1,2>,<1,3>和<1,4>，得到的结果如(c)图所示。
(3) 在(c)图中v2和v4的入度都为0，不妨选择v2并输出之，接着删去v2及两条出边<2,3>和<2,5>，得到的结果如(d)图所示。
(4) 在(d)图上依次输出顶点v3,v4和v5，并在每个顶点输出后删除该顶点及出边，操作都很简单，不再赘述。
为了利用C++语言在计算机上实现拓扑排序算法，AOV网采用邻接表表示较方便。如对于图3-8(a)，对应的邻接表如图3-8所示。
|
|
|
|
|
|
图3-8 图3-7(a)的链接表
在拓扑排序算法中，需要设置一个包含n个元素的一维整型数组，假定用d表示，用它来保存AOV网中每个顶点的入度值。如对于图3-8(a)，得到数组d的初始值为
0 1 2 3 4 5
|
0 |
0 |
2 |
2 |
1 |
3 |
在进行拓扑排序中，为了把所有入度为0的顶点都保存起来，而且又便于插入、删除以及节省存储，最好的方法是把它们链接成一个栈。另外，当一个顶点vi的入度为0时，数组d中下标为i的元素d[i]的值为0，正好可利用该元素作为链栈中的一个结点使用，保存下一个入度为0的顶点的序号，这样就可以把所有入度为0的顶点通过数组d中的对应元素静态链接成一个栈。在这个链栈中，栈顶指针top指向第一个入度为0的顶点所对应的数组d中的元素，该元素的值则指向第二个入度为0的顶点所对应的数组d中的元素，依此类推，最后一个入度为0顶点所对应的数组d中的元素保存着-1，表示为栈底。
例如，根据图3-8所示的邻接表，建立的入度为0的初始栈的过程为：
(1) 开始置链栈为空，即给链栈指针top赋初值为-1：
top=-1;
(2) 将入度为0的元素d[0]进栈，即：
d[0]=top; top=0;
此时top指向d[0]元素，表示顶点v0的入度为0，而d[0]的值为-1，表明为栈底。
(3) 将入度为0的元素d[1]进栈，即:
d[1]=top; top=1;
此时top指向d[1]元素，表示顶点v1的入度为0，而d[1]的值为0，表明下一个入度为0的元素为d[0]，即对应下一个入度为0的顶点为v0，d[0]的值为-1，所以此栈当前有两个元素d[1]和d[0]。
(4) 因d[2]至d[5]的值均不为0，即对应的v2到v5的入度均不为0，所以它们均不进栈，至此，初始栈建立完毕，得到的数组d为：
0 1 2 3 4 5
|
-1 |
0 |
2 |
2 |
1 |
3 |
top
将入度为0的顶点利用上述链栈链接起来后，拓扑算法中循环执行的第(1)步“选择一个入度为0的顶点并输出之”，可通过输出栈顶指针top所代表的顶点序号来实现；第(2)步“从AOV网中删除刚输出的顶点（假定为vj，其中j等于top的值）及所有出边”，可通过首先作退栈处理，使top指向下一个入度为0的元素，然后遍历vj的邻接点表，分别把所有邻接点的入度减1，若减1后的入度为0则令该元素进栈来实现。此外，该循环的终止条件“直到不存在入度为0的顶点为止”，可通过判断栈空来实现。
对于图3-7(a)，当删除由top值所代表的顶点v1及所有出边后，数组d变为：
0 1 2 3 4 5
|
-1 |
|
1 |
1 |
0 |
3 |
top
当依次删除top所表示的每个顶点及所有出边后，数组d的变化分别如图3-9(a)至(d)所示：
0 1 2 3 4 5
|
-1 |
|
1 |
1 |
|
2 |
top
(a) 删除顶点v4及所有出边
0 1 2 3 4 5
|
|
|
-1 |
1 |
|
2 |
top
(b) 删除顶点v0及所有出边
0 1 2 3 4 5
|
|
|
|
-1 |
|
1 |
top
(c) 删除顶点v2及所有出边
0 1 2 3 4 5
|
|
|
|
|
|
-1 |
top
(d) 删除顶点v3及所有出边
图3-9 数组d变化示意图
当删除顶点v5及所有出边后，top的值为1，表示栈空，至此算法执行结束，得到的拓扑序列为：1,4,0,2,3,5。
根据以上分析，给出拓扑排序算法的具体描述为：
void Toposort(adjlist GL, int n)
//对用邻接表GL表示的有向图进行拓扑排序
{
int i,j,k,top,m=0; //m用来统计拓扑序列中的顶点数
edgenode *p;
//定义存储图中每个顶点入度的一维整型数组d
int* d=new int[n];
//初始化数组d中的每个元素值为0
for(i=0; i<n; i++)
d[i]=0;
//利用数组d中的对应元素统计出每个顶点的入度
for(i=0; i<n; i++) {
p=GL[i];
while(p!=NULL) {
j=p->adjvex;
d[j]++;
p=p->next;
}
}
//初始化用于链接入度为0的元素的栈的栈顶指针top为-1
top=-1;
//建立初始化栈
for(i=0; i<n; i++)
if(d[i]==0) {
d[i]=top;
top=i;
}
//每循环一次删除一个顶点及所有出边
while(top!=-1)
{
j=top; //j的值为一个入度为0的顶点序号
top=d[top]; //删除栈顶元素
cout<<j<<' '; //输出一个顶点
m++; //输出的顶点个数加1
p=GL[j]; //p指向vj邻接点表的第一个结点
while(p!=NULL)
{
k=p->adjvex; //vk是vj的一个邻接点
d[k]--; //vk的入度减1
if(d[k]==0) { //把入度为0的元素进栈
d[k]=top;
top=k;
}
p=p->next; //p指向vj邻接点表的下一个结点
}
}
cout<<endl;
if(m<n)
//当输出的顶点数小于图中的顶点数时，输出有回路信息
cout<<"The network has a cycle!"<<endl;
}
拓扑排序实际上是对邻接表表示的图G进行遍历的过程，每次访问一个入度为0的顶点。若图G中没有回路，则需要扫描邻接表中的所有边结点，再加上在算法开始时，为建立入度数组d需要访问表头向量中的每个域和其单链表中的每个结点，所以此算法的时间复杂性为O(n+e)。
/*
* 拓扑排序（采用邻接矩阵存储）
*/
#include<stdio.h>
#define MAX_VERTEX_NUM 20
//图的定义
typedef struct
{
int vertexNum;
char vertex[MAX_VERTEX_NUM];
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
}Graph,*PGraph;
//构造有向图
void createdGraph(PGraph g)
{
int i,j;
g->vertexNum=6;
for(i=0;i<g->vertexNum;i++)
g->vertex[i]='A'+i;
for(i=0;i<g->vertexNum;i++)
for(j=0;j<g->vertexNum;j++)
g->arc[i][j]=0;
g->arc[0][1]=1;
g->arc[0][2]=1;
g->arc[0][3]=1;
g->arc[1][4]=1;
g->arc[2][1]=1;
g->arc[2][4]=1;
g->arc[4][3]=1;
g->arc[4][5]=1;
}
//拓扑排序
void TopologicalSort(PGraph g)
{
int i,j,k=0,m;
char vertex[MAX_VERTEX_NUM];
while(k < g->vertexNum){
//1.找没有入度的顶点,存入数组vertex中
for(i=0;i<g->vertexNum;i++){
for(j=0;j<g->vertexNum;j++){
if(g->arc[j][i]!=0)
break;
}
if(j==g->vertexNum){
//检查g->vertex[i]是否已经遍历
for(m=0;m<k;m++)
if(vertex[m]==g->vertex[i])
break;
if(m==k){
vertex[k++]=g->vertex[i];
break;
}
}
}
//2.没有入度为0的顶点
if(i==g->vertexNum){
printf("存在回路!\n");
return ;
}
//3.删除这个顶点的出度
for(j=0;j<g->vertexNum;j++)
g->arc[i][j]=0;
}
//输出排序后的结果
printf("拓扑排序结果：\n");
for(i=0;i<k;i++)
printf("%-3c",vertex[i]);
printf("\n");
}
void main()
{
Graph graph;
createdGraph(&graph);
TopologicalSort(&graph);
}
最小生成树
无向连通图的所有生成树中有一棵边的权值总和最小的生成树
/*
* 普里姆算法和克鲁斯卡尔算法求最小生成树
* 采用邻接矩阵存储
*
*/
#include<stdio.h>
#define MAX_VERTEX_NUM 20
//图的定义
typedef struct
{
int vertexNum;
int edgeNum;
char vertex[MAX_VERTEX_NUM];
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
}Graph,*PGraph;
//辅助数组元素
typedef struct
{
int from;
int to;
int weight;
int flag;
}ArrayNode;
//构造无向网
void createdGraph(PGraph g)
{
int i,j;
g->vertexNum=6;
g->edgeNum=10;
for(i=0;i<g->vertexNum;i++)
g->vertex[i]='A'+i;
for(i=0;i<g->vertexNum;i++)
for(j=0;j<g->vertexNum;j++)
g->arc[i][j]=0;
g->arc[0][1]=6;
g->arc[0][2]=1;
g->arc[0][3]=5;
g->arc[1][0]=6;
g->arc[1][2]=5;
g->arc[1][4]=3;
g->arc[2][0]=1;
g->arc[2][1]=5;
g->arc[2][3]=5;
g->arc[2][4]=6;
g->arc[2][5]=4;
g->arc[3][0]=5;
g->arc[3][2]=5;
g->arc[3][5]=2;
g->arc[4][1]=3;
g->arc[4][2]=6;
g->arc[4][5]=6;
g->arc[5][2]=4;
g->arc[5][3]=2;
g->arc[5][4]=6;
}
//初始化最小生成树
void initTree(PGraph tree)
{
int i,j;
tree->vertexNum=6;
tree->edgeNum=5;
for(i=0;i<tree->vertexNum;i++)
tree->vertex[i]='0';
for(i=0;i<tree->vertexNum;i++)
for(j=0;j<tree->vertexNum;j++)
tree->arc[i][j]=0;
}
//普里姆算法求最小生成树
void prim(PGraph g,PGraph tree)
{
int i,j,k;
int index; //指向权值最小的边
ArrayNode edgeArray[MAX_VERTEX_NUM*2]; //辅助数组
int length=0; //数组长度
int n=1; //统计数组已加入多少个顶点
//初始状态把第一个顶点加入树中
tree->vertex[0]='A';
printf("%-3c",tree->vertex[0]);
i=0;
while(1){
//寻找与顶点i相接且这条边的另一个顶点不在树中的边,存入edgeArray数组中
for(j=0;j<g->vertexNum;j++){
if(g->arc[i][j] > 0){
//判断这条边的另一个顶点在不在树中
for(k=0;k<tree->vertexNum;k++){
if(tree->vertex[k] == g->vertex[j])
break;
}
if(k == tree->vertexNum){
edgeArray[length].from=i;
edgeArray[length].to=j;
edgeArray[length].weight=g->arc[i][j];
edgeArray[length].flag=0;
length++;
}
}
}
//从数组中选择权值最小的边
index=-1;
for(j=0;j<length;j++){
if(index == -1 && edgeArray[j].flag == 0)
index=j;
if(edgeArray[j].flag==0 && edgeArray[j].weight < edgeArray[index].weight)
index=j;
}
//在树中加入一个顶点，且把这条权值最小的边加入树中
tree->vertex[edgeArray[index].to]='A'+edgeArray[index].to;
edgeArray[index].flag=1;
tree->arc[edgeArray[index].from][edgeArray[index].to]=edgeArray[index].weight;
tree->arc[edgeArray[index].to][edgeArray[index].from]=edgeArray[index].weight;
//当这个顶点加入树中时，与这个顶点相邻的边不可加入树中
for(k=0;k<length;k++){
if(edgeArray[k].to == edgeArray[index].to)
edgeArray[k].flag=1;
}
i=edgeArray[index].to;
printf("%-3c",tree->vertex[i]);
n++;
//当有g->vertexNum个顶点时，最小生成树构造完成
if(n==g->vertexNum)
break;
}
}
//判断两个顶点是否连通（广度优先搜索）
int connected(PGraph tree,int from,int to)
{
int i,j,k;
int vertex[MAX_VERTEX_NUM];//看成队列
int front,rear;
if(from==to)
return 1;
front=rear=0;
//把第一个顶点存入数组
vertex[rear++]=from;
//遍历tree
while(front<=rear){
i=vertex[front];
for(j=0;j<tree->vertexNum;j++)
if(tree->arc[i][j]>0){
if(j==to)
return 1;
//判断此顶点是否在队列中
for(k=0;k<rear;k++)
if(vertex[k] == j)
break;
if(k==rear)
vertex[rear++]=j;
}
front++;
}
return 0;
}
//克鲁斯卡尔算法求最小生成树
void kruskal(PGraph g,PGraph tree)
{
ArrayNode edgeArray[MAX_VERTEX_NUM]; //辅助数组
int length=0;
int i,j,k,index,n;
//顶点先加入树中
for(i=0;i<tree->vertexNum;i++)
tree->vertex[i]=i+'A';
//1.把所有的边有序(从小到大)的插入edgeArray数组中
for(i=0;i<g->vertexNum;i++)
for(j=0;j<g->vertexNum;j++){
if(i<j && g->arc[i][j]>0){
//寻找插入的位置index
for(k=0;k<length;k++){
if(edgeArray[k].weight > g->arc[i][j])
break;
}
index=k;
//移位
for(k=length;k>index;k--)
edgeArray[k]=edgeArray[k-1];
//插入
length++;
edgeArray[index].flag=0;
edgeArray[index].from=i;
edgeArray[index].to=j;
edgeArray[index].weight=g->arc[i][j];
}
}
//2.从小到大取出n-1条边构造最小生成树
n=0;
while(n < g->vertexNum-1){
//从小到大取一条符合要求的边
for(k=0;k<length;k++)
if(edgeArray[k].flag==0 && connected(tree,edgeArray[k].from,edgeArray[k].to)==0){
break;
}
//把这条边加入树中
tree->arc[edgeArray[k].from][edgeArray[k].to]=edgeArray[k].weight;
tree->arc[edgeArray[k].to][edgeArray[k].from]=edgeArray[k].weight;
edgeArray[k].flag=1;
printf("%-3d",edgeArray[k].weight);
n++;
}
}
void main()
{
Graph graph;
Graph tree;
createdGraph(&graph);
initTree(&tree);
printf("普里姆算法树中顶点加入的顺序:\n");
prim(&graph,&tree);
printf("\n");
initTree(&tree);
printf("克鲁斯卡尔算法树中边加入的顺序:\n");
kruskal(&graph,&tree);
printf("\n");
}
关键路径
在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度，路径长度最长的路径叫做关键路径(Critical Path)。【tips:完成基本任务的同时尽可能多的完成任务】
AOE网即边表示活动的网络。通常，可用AOE网来估算工程计划的完成时间。
如下面的AOE网包括11项活动，9个事件，每个事件都有所需的完成时间。我们现在解决的是这样的问题：（1）完成整项工程至少需要多少时间（最短时间）；（2）哪些活动是影响工程进度的关键（关键活动）。
用e(i)表示活动最早开始时间，l(i)表示活动的最迟开始时间，则l(i)-e(i)为完成该活动的时间余量。对于本例列表如下：
|
活动 |
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
a10 |
a11 |
|
e(i) |
0 |
0 |
0 |
6 |
4 |
5 |
7 |
7 |
7 |
16 |
14 |
|
l(i) |
0 |
2 |
3 |
6 |
6 |
8 |
7 |
7 |
10 |
16 |
14 |
|
l(i)-e(i) |
0 |
2 |
3 |
0 |
2 |
3 |
0 |
0 |
3 |
0 |
0 |
下面是示例AOE网的关键路径：
源程序清单：
#include<stdio.h>
#include<iostream>
using namespace std;
#define n 9 //顶点数
#define ed 11 //边数
#define maxsize 20 //边的最大可能条数
typedef char vextype;
typedef struct node1
{
int adjvex; //邻接点域（下标）
int dut; //权值
struct node1 *next; //链域
}edgenode1; //边表结点
typedef struct
{
vextype vertex; //顶点信息
int id; //入度
edgenode1 *link; //边表头指针
}vexnode1;//顶点表结点
void creatgraph(vexnode1 dig[]);//建立AOE网的邻接表
void criticalpath(vexnode1 dig[]);//dig是AOE网的带权邻接表
void main()
{
printf(" ——AOE网的关键路径——\n");
vexnode1 dig[n];
creatgraph(dig);
printf("【输出AOE网的邻接表】\n");
int i;
edgenode1 *s;
for(i=0;i<n;i++)
{
printf("|%c %d |",dig[i].vertex,dig[i].id);
s=dig[i].link;
while(s)
{
printf("——> %d %d",s->adjvex+1,s->dut);
s=s->next;
}
printf("\n");
}
printf("【输出关键活动】\n");
printf("每行分别为开始事件、结束事件、最早开始时间、最迟开始时间和完成活动的时间余量\n");
criticalpath(dig);
}
void creatgraph(vexnode1 dig[])//建立AOE网的邻接表
{
printf("【输入AOE网的顶点（顶点信息和入度，用空格隔开）】\n");
int i;
for(i=0;i<n;i++)
{
printf("第%d个顶点的信息和入度：",i+1);
cin>>dig[i].vertex>>dig[i].id;
dig[i].link=NULL;
}
printf("【输入AOE网的边（始点、终点和权，用空格隔开）】\n");
edgenode1 *s;
int a,b;//记录边的始点和终点
for(i=0;i<ed;i++)
{
s=(edgenode1 *)malloc(sizeof(edgenode1));
printf("第%d条边的始点、终点和权：",i+1);
cin>>a>>b>>s->dut;
s->adjvex=b-1;
s->next=dig[a-1].link;
dig[a-1].link=s;
}
}
void criticalpath(vexnode1 dig[])//dig是AOE网的带权邻接表
{
int i,j,k,m;
int front=-1,rear=-1; //顺序队列的首位指针置初值-1
int tport[n],vl[n],ve[n];
int l[maxsize],e[maxsize];
edgenode1 *p;
for(i=0;i<n;i++)
ve[i]=0; //各时间v(i+1)的最早发生时间均置初值零
for(i=0;i<n;i++)//扫描顶点表，将入度为零的顶点入队
if(dig[i].id==0)
tport[++rear]=i;
m=0; //计数器初始化
while(front!=rear) //队非空
{
front++;
j=tport[front]; //v(j+1)出队，即删去v(j+1)
m++; //对出队的顶点个数计数
p=dig[j].link; //p指向v(j+1)为起点的出边表中表结点的下标
while(p) //删去所有以v(j+1)为起点的出边
{
k=p->adjvex;//k是边(v(j+1),v(k+1))终点v(k+1)的下标
dig[k].id--; //v(k+1)入度减1
if(ve[j]+p->dut>ve[k])
ve[k]=ve[j]+p->dut; //修改ve[k]
if(dig[k].id==0)
tport[++rear]=k; //新的入度为零的顶点v(k+1)入队
p=p->next; //找v(j+1)的下一条边
}
}
if(m<n) //网中有回路，终止算法
{
printf("AOE网有回路\n");
return;
}
for(i=0;i<n;i++)//为各事件v(i+1)的最迟发生时间vl[i]置初值
vl[i]=ve[n-1];
for(i=n-2;i>=0;i--)//按拓扑序列的逆序取顶点
{
j=tport[i];
p=dig[j].link; //取v(j+1)的出边表上第一个表结点
while(p)
{
k=p->adjvex; //k为(v(j+1),v(k+1))的终点v(k+1)的下标
if((vl[k]-p->dut)<vl[j])
vl[j]=vl[k]-p->dut; //修改vl[j]
p=p->next; //找v(j+1)的下一条边
}
}
i=0;//边计数器置初值
for(j=0;j<n;j++) //扫描顶点表，依次取顶点v(j+1)
{
p=dig[j].link;
while(p) //扫描顶点的v(j+1)的出边表
{//计算各边(v(j+1),v(k+1))所代表的活动a(i+1)的e[i]和l[i]
k=p->adjvex;
e[++i]=ve[j];
l[i]=vl[k]-p->dut;
printf("%c\t%c\t%d\t%d\t%d\t",//输出活动a(i+1)的有关信息
dig[j].vertex,dig[k].vertex,e[i],l[i],l[i]-e[i]);
if(l[i]==e[i])//关键活动
printf("关键活动");
printf("\n");
p=p->next;
}
}
}
运行结果：
最短路径
最短路径问题是图研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
/*
* 最短路径，迪杰斯特拉算法和弗洛伊德算法（采用邻接矩阵存储）
*
*/
#include<stdio.h>
#define MAX_VERTEX_NUM 20
#define INFINITE 10000 //当做无穷大
//图的定义
typedef struct
{
int vertexNum;
char vertex[MAX_VERTEX_NUM];
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
}Graph,*PGraph;
//辅助数组中的元素定义
typedef struct
{
int distance;
int path[MAX_VERTEX_NUM];
}ArrayNode;
//构造有向网
void createdGraph(PGraph g)
{
int i,j;
g->vertexNum=6;
for(i=0;i<g->vertexNum;i++)
g->vertex[i]='A'+i;
for(i=0;i<g->vertexNum;i++)
for(j=0;j<g->vertexNum;j++)
g->arc[i][j]=0;
g->arc[0][2]=10;
g->arc[0][4]=30;
g->arc[0][5]=100;
g->arc[1][2]=5;
g->arc[2][3]=50;
g->arc[3][5]=10;
g->arc[4][3]=20;
g->arc[4][5]=60;
}
//迪杰斯特拉算法
void Dijkstra(PGraph g,int from,int to)
{
int i,j,index=-1;
int n=1;//记录已经求出的两个点之间的最短距离的个数
ArrayNode shortestPath[MAX_VERTEX_NUM];
int flag[MAX_VERTEX_NUM]={0};//标记，为1表示到这个顶点的最短距离已求出
//1.求from到各个顶点的直接距离，即初始化shortestPath数组
for(i=0;i<g->vertexNum;i++){
if(from==i){
shortestPath[i].distance=0;
shortestPath[i].path[0]=i;
flag[from]=1;
}
else if(g->arc[from][i]>0){
shortestPath[i].path[0]=from;
shortestPath[i].path[1]=i;
shortestPath[i].distance=g->arc[from][i];
}else
shortestPath[i].distance=INFINITE;
}
//2.每次求一个最短路径
while(n<g->vertexNum){
//选择shortestPath中距离最小的，求出from到这个顶点的最短路径
index=-1;
for(i=0;i<g->vertexNum;i++){
if(i==from)
continue;
if(flag[i]==0 && index==-1 && shortestPath[i].distance!=INFINITE)
index=i;
if(flag[i]==0 && index!=-1 && shortestPath[i].distance<shortestPath[index].distance)
index=i;
}
flag[index]=1;
//修改到各个顶点的最短路径
for(i=0;i<g->vertexNum;i++){
if(i==from)
continue;
if(g->arc[index][i]>0 && g->arc[index][i]+shortestPath[index].distance<shortestPath[i].distance){
shortestPath[i].distance=g->arc[index][i]+shortestPath[index].distance;
//修改路径
j=0;
while(1){
shortestPath[i].path[j]=shortestPath[index].path[j];
if(shortestPath[index].path[j]==index)
break;
j++;
}
shortestPath[i].path[j+1]=i;
}
}
n++;
}
//输出from到to的最短路径及长度
if(shortestPath[to].distance==INFINITE){
printf("%c到%c没有路径\n",from+'A',to+'A');
return;
}
printf("%c到%c的最短路径长度是：%d\n",from+'A',to+'A',shortestPath[to].distance);
printf("经过的顶点： ");
i=0;
while(1){
printf("%-3c",shortestPath[to].path[i]+'A');
if(shortestPath[to].path[i]==to)
break;
i++;
}
printf("\n");
}
//弗洛伊德算法
void Floyd(PGraph g,int from,int to)
{
int i,j,k;
int shortestPath[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//存储最短路径的数组
//初始化shortestPath
for(i=0;i<g->vertexNum;i++)
for(j=0;j<g->vertexNum;j++){
if(i==j){
shortestPath[i][j]=0;
continue;
}
if(g->arc[i][j]>0)
shortestPath[i][j]=g->arc[i][j];
else
shortestPath[i][j]=INFINITE;
}
//将各个顶点顺次加入，并修改最短路径
for(k=0;k<g->vertexNum;k++){
//在i，j之间加入k
for(i=0;i<g->vertexNum;i++){
for(j=0;j<g->vertexNum;j++){
if(shortestPath[i][k]+shortestPath[k][j]<shortestPath[i][j])
shortestPath[i][j]=shortestPath[i][k]+shortestPath[k][j];
}
}
}
//输出最短路径
if(shortestPath[from][to]==INFINITE){
printf("%c到%c没有路径\n",from+'A',to+'A');
return;
}
printf("%c到%c的最短路径长度是：%d\n",from+'A',to+'A',shortestPath[from][to]);
printf("\n");
}
void main()
{
Graph graph;
char from,to;
createdGraph(&graph);
printf("请输入起点终点(如AF，中间不要有空格)\n");
scanf("%c%c",&from,&to);
printf("\n迪杰斯特拉算法:\n");
Dijkstra(&graph,from-'A',to-'A');
printf("\n弗洛伊德算法:\n");
Floyd(&graph,from-'A',to-'A');
}