Abo

数据结构-图

图,让我想起被离散数学图论支配的恐惧,但是数据结构涉及到的属于图的抽象数据结构,简直比离散数学还要致命


art

介绍

  • 前言: 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合
  • 图的定义与术语
  1. 线性表中我们把数据元素叫元素,树中将数据元素叫结点,在图中数据元素,我们则称之为顶点(Vertex)
  2. 线性表中可以没有数据元素,称为空表;树中可以没有结点,称为空树;而在图结构,不允许没有顶点,在定义中,若V是顶点的集合,则强调了顶点集合V有穷非空。
  3. 线性表中,相邻的数据元素之间有线性关系;树结构中,相邻两层的结点具有层次关系;而图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的.
  4. 无向边(Edge),用无序偶对(vi,vj)来表示
  5. 无向图(Undirected graphs)
  6. 有向边,也称为为弧(Arc)
  7. 有向图(Directed graphs),用有序偶<vi,vj>来表示

    连接顶点A到D的有向边就是弧,A是弧尾,D是弧头

  8. 简单图:图中若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图
  9. 无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图
  10. 有向完全图:在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图
  11. 稀疏图与稠密图:有很少条边或弧的图称为稀疏图,反之称为稠密图
  12. 权(Weight):与图的边或弧相关的数叫做权
  13. 网(Network):这种带权的图通常称为网
  14. 子图(Subgraph)
  15. 邻接点(Adjacent)
  16. 依附(incident)
  17. 度(Degree)
  18. 入度(InDegree)ID与出度(OutDegree)OD
  19. 路径(Path)

    路径的长度是路径上边或弧的数目

  20. 回路或环(Cycle)
  21. 简单路径:序列中顶点不重复出现的路径称为简单路径
  22. 简单回路或简单环:除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路
  23. 连通图(Connected Graph):无向图中
  24. 连通分量:无向图中的极大连通子图
  25. 强连通图:有向图中,任意两点都有路径
  26. 强连通分量:有向图中的极大强连通子图
  27. 连通图的生成树:一个连通图的生成树是一个极小的连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边

    如果一个图有n个顶点和小于n-1条边,则是非连通图;如果它多于n-1条边,必定构成一个环

    但是有n-1条边并不一定是生成树

  28. 有向树:如果一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一棵有向树
  29. 生成森林:由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧。

    图的存储结构

  30. 邻接矩阵

图的邻接矩阵存储的结构

1
2
3
4
5
6
7
8
9
10
typedef char VertexType;  /*顶点类型应由用户定义*/
typedef int EdgeType; /*边上的权值类型应全由用户定义*/
#define MAXVEX 100 /*最大顶点数,由用户定义*/
#define INFINITY 65535 /*用65535表示∞*/
typedef struct
{
VertexType vexs[MAXVEX]; /*顶点表*/
EdgeType arc[MAXVEX][MAXVEX]; /*邻接矩阵,可看作边表*/
int numVertexes,numEdges; /*图中当前的顶点和边数*/
}MGraph;

有了这个结构定义,我们构造一个图,其实就是给顶点表和边表输入数据的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*建立无向网图的邻接矩阵表示*/
void CreateMGraph(MGraph *G)
{
int i,j,k,w;
printf("输入顶点数和边数:\n");
scanf("%d,%d",&G->numVertexes,&G->numEdges); /*输入顶点数和边数*/
for(i = 0;i < G->numVertexes;i++) /*读入顶点信息,建立顶点表*/
scanf(&G->vexs[i]);
for(i = 0;i < G->numVertexes;i++)
for(j = 0;j <G->numVertexes;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)上的权*/
G->arc[i][j]=w;
G->arc[j][i]=G->arc[i][j]; /*因为是无向图,矩阵对称*/
}
}

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

  1. 邻接表
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    typedef char VertexType;  /*顶点类型应由用户定义*/
    typedef int EdgeType; /*边上的权值类型应由用户定义*/

    typedef struct EdgeNode /*边表结点*/
    {
    int adjvex; /*邻接点域,存储该顶点对应的下标*/
    EdgeType weight; /*用于存储权值,对于非网图可以不需要*/
    struct EdgeNode *next; /*链域,指向下一个临接点*/
    }EdgeNode;

    typedef struct VertexNode /*顶点表结点*/
    {
    AdjList adjList; /*顶点域,存储顶点信息*/
    int numVertexes,numEdges; /*边表头指针*/
    }GraphAdjList;
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
/*建立无向图的邻接表结构*/
void CreateALGraph(GraphAdjList *G)
{
int i,j,k;
EdgeNode *e;
printf("输入顶点数和边数:\n");
scanf("%d,%d",&G->numVertexes,&G->numEdges); /*输入顶点数和边数*/
for(i = 0;i < G->numVertexes;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); /*输入边上的顶点序号*/
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*/
}
}
/*后边代码用了前面讲到的单链表头插法*/
  1. 边集数组
  2. 十字链表
  3. 邻接多重表

图的遍历

又称为深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef int Boolean;  /*Boolean是布尔类型,其值是TRUE或FALSE*/
Boolean visited[MAX]; /*访问标志的数组*/
/*邻接矩阵的深度优化递归算法*/
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*邻接表的深度优先递归算法*/
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)。显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高

又称为广度优先搜索

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
/*邻接矩阵的广度遍历算法*/
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); /*将找到的此顶点入队列*/
}
}
}
}
}
}
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
/*邻接表的广度遍历算法*/
void BFSTraverse(GraphAdjList GL)
{
int i;
EdgeNode *p;
Queue 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; /*指针指向下一个邻接点*/
}
}
}
}
}

对比图的深度优先遍历与广度优先遍历算法,它们在时间复杂度上是一样的,不同之处仅仅在对顶点访问的顺序不同,可见两者在全图遍历上是没有优劣之分的,只是视不同的情况选择不同的算法。

最小生成树

  1. 普里姆算法(Prim)
    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
    35
    36
    37
    38
    39
    /*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)",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^)

  1. 克鲁斯卡尔算法(Kruskal)
    1
    2
    3
    4
    5
    6
    7
    /*对边集数组Edge结构的定义*/
    typedef struct
    {
    int begin;
    int end;
    int weight;
    }Edge;
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
/*Kruskal算法生成最小生成树*/
void MiniSpanTree_Kruskal(MGraph G) /*生成最小生成树*/
{
int i,n,m;
Edge edges[MAXEDGE]; /*定义边集数组*/
int parent[MAXVEX]; /*定义一数组用来判断边与边是否形成环路*/
/*此处省略将邻接表矩阵G转化为边集数组edges并按权从小到大排序的代码*/
for(i = 0; i <G.numVertexes; i++)
parent[i] = 0; /*初始化数组值为0*/
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",edges[i].begin,edges[i].end,edges[i].weight);
}
}
}

int Find(int *parent,int f) /*查找连线顶点的尾部下标*/
{
while(parent[f]>0)
f = parent[f];
return f;
}

此算法的Find函数由边数e决定,时间复杂度为O(loge),而外面有一个for循环e次,所以克鲁斯卡尔算法的时间复杂度为O(eloge)

对比两个算法,克鲁斯卡尔算法主要是针对边来展开,边数少时效率会非常高,对于稀疏图有很大优势,而普里姆算法对于稠密图,即边数非常多的情况会更好一点。

最短路径

  1. 迪杰斯特拉(Dijkstra)
    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
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #define MAXVEX 9
    #define INFINITY 65535
    typedef int Pathmatrix[MAXVEX]; /*用于存储最短路径下标的数组*/
    typedef int ShortPathTable[MAXVEX]; /*用于存储到各点最短路径的权值和*/
    /*Dijkstra算法,求有向网G的v0顶点到其余顶点v最短路径P[v]及带权长度D[v]*/
    /*P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和*/
    void shortestPath_Dijkstra(MGraph G,int v0,Pathmatirx *p,ShortPathTable *D)
    {
    int v,w,k,min;
    int final[MAXVEX]; /*final[w]=1表示求得顶点V0至Vw的最短路径*/
    for(v=0;v<G.numVertexes;v++) /*初始化数据*/
    {
    final[v] = 0; /*全部顶点初始化为未知最短路径状态*/
    (*D)[v] = G.matirx[v0][v]; /*将与v0点有连线的顶点加上权值*/
    (*P)[v] = 0; /*初始化路径数组为0*/
    }
    (*D)[v0] = 0; /*v0至v0路径为0*/
    final[v0] = 1; /*v0至v0不需要求路径*/
    /*开始主循环,每次求得v0到某个v顶点的最短路径*/
    for(v=1;v<G.numVertexes;w++)
    {
    min=INFINITY; /*当前所知离v0顶点的最近距离*/
    for(w=0;w<G.numVertexes;w++) /*寻找离v0最近的顶点*/
    {
    if(!final[w] && (*D)[w]<min)
    {
    k=w;
    min = (*D)[w]; /*w顶点离v0顶点更近*/
    }
    }
    final[k] = 1; /*将目前找到的最近的顶点置为1*/
    for(w=0;w<G.numVertexes;w++) /*修正当前最短路径及距离*/
    {
    /*如果结果v顶点的路径比现在这条路径的长度短的话*/
    if(!final[w] && (min + G.matirx[k][w] < (*D)[w]))
    { /*说明找到了更短的路径,修改D[w]和P[w]*/
    (*D)[w] = min + G.matirx[k][w]; /**/
    (*P)[w] = k;

    }
    }
    }
    }

我们通过迪杰斯特拉(Dijkstra)算法解决了从某个源点到其余各顶点的最短路径问题。从循环嵌套可以很容易得到此算法的时间复杂度为O(n^2^),如果我们还需要知道其它顶点到其余所有顶点的最短路径,我们则需要再一次循环,此时整个算法的复杂度变成了O(n^3^)

  1. 弗洛伊德算法(Floyd)
    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
    typedef int Pathmatirx[MAXVEX][MAXVEX];
    typedef int ShortPathTable[MAXVEX][MAXVEX];
    /*Floyd算法,求网图G中各顶点v到其余顶点w最短路径P[v][w]及带权长度D[v][w]*/
    void ShortestPath_Floyd(MGraph G,Pathmatirx *P,ShortPathTable *D)
    {
    int v,w,k;
    for(v=0;v<G.numVertexes;++v) /*初始化D与P*/
    {
    for(w=0;w<G.numVertexes;++w)
    {
    (*D)[v][w]=G.matirx[v][w]; /*D[v][w]值即为对应点间的权值*/
    (*P)[v][w]=w; /*初始化P*/
    }
    }
    for(k=0;k<G.numVertexes;++k)
    {
    for(v=0;v<G.numVertexes;++v)
    {
    for(w=0;w<G.numVertexes;++w)
    {
    if((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
    { /*如果经过下标为k顶点路径比原两点间路径更短,将当前两点间权值设为更小的一个*/
    (*D)[v][w]=(*D)[v][k]+(*D)[k][w];
    (*P)[v][w]=(*P)[v][k]; /*路径设置经过下标为k的顶点*/
    }
    }
    }
    }
    }

求最短路径的显示代码可以这么写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(v=0;v<G.numVertexes;++v)
{
for(w=v+1;w<G.numVertexes;w++)
{
printf("v%d-v%d weight: %d",v,w,D[v][w]);
k=P[v][w]; /*获得第一个路径顶点下标*/
printf("path:%d",v); /*打印源点*/
while(k!=w) /*如果路径顶点下标不是终点*/
{
printf("->%d",k); /*打印路径顶点*/
k=P[k][w]; /*获得下一个路径顶点下标*/
}
printf("->%d\n",w); /*打印终点*/
}
printf("\n");
}

  • 拓扑排序

有向无环图时常应用于工程规划中,对于整个工程或系统来说,我们一方面关心的是工程是否顺利进行的问题,通过拓扑排序的方式,我们可以有效地分析除一个有向图是否存在环,如果不存在,那它的拓扑序列是?

在拓扑排序算法中,涉及的结构代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct EdgeNode  /**/
{
int adjvex; /*邻接点域,存储该顶点对应的下标*/
int weight; /*用于存储权值,对于非网图可以不需要*/
struct EdgeNode *next; /*链域,指向下一个邻接点*/
}EdgeNode;

typedef struct VertexNode /*顶点表结点*/
{
int in; /*顶点入度*/
int data; /*顶点域,存储顶点信息*/
EdgeNode *firstedge; /*边表头指针*/
}VertexNode,AdjList[MAXVEX];

typedef struct
{
AdjList adjList;
int numVertexes,numEdges; /*图中当前顶点数和边数*/
}graphAdjList,*GraphAdjList;

在算法中,我们还需要辅助的数据结构——栈,用来存储处理过程中入度为0的顶点,目的是为了避免每个查找时都要去遍历顶点表找有没有入度为0的顶点。

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
/*拓扑排序,若GL无回路,则输出拓扑排序序列并返回OK,若有回路返回ERROR*/
Status TopologicalSort(GraphAdList GL)
{
EdgeNode *e;
int i,k,gettop;
int top=0; /*用于栈指针下标*/
int count=0; /*用于统计输出顶点的个数*/
int *stack; /*建栈存储入度为0的顶点*/
stack=(int*)malloc(GL-numVertexes*sizeof(int));
for(i = 0;i<GL->numVertexes;i++)
if(GL->adjList[in].in == 0)
stack[++top]=i; /*将入度为0的顶点入栈*/
while(top!=0)
{
gettop=stack[top--]; /*出栈*/
printf("%d->",GL->adjList[gettop].data); /*打印此顶点*/
count++; /*统计输出顶点数*/
for(e=GL->adjList[gettop].firstedge;e;e->next)
{/*对此顶点弧表遍历*/
k=e->adjvex;
if(!(--GL->adjList[k].in)) /*将k号顶点邻接点的入度减一*/
stack[++top]=k; /*若为0则入栈,以便于下次循环输出*/
}
}
if(count<GL->numVertexes) /*如果count小于顶点数,说明存在环*/
return ERROR;
else
return OK;
}

分析整个算法,对一个具有n个顶点e条弧的AOV网来说,将入度为0的顶点入栈的时间复杂为O(n),而之后的while循环中,每个顶点进一次栈,出一次栈,入度减1的操作共执行了e次,所以整个算法的时间复杂度为O(n+e)

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网(Activity On Vertex Network)

  • 关键路径

另一方面关心的是整个工程的完成所必须的最短时间问题,利用求关键路径的算法,可以得到最短完成工程的工期以及关键的活动有哪些。

在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称之为AOE网(Activity On Edge Network)

我们把路径上各个活动所持续的时间之和称为路径长度,从源点到汇点3具有最大长度的路径叫关键路径,在关键路径上的活动叫关键活动

  1. 事件的最早发生时间etv(earliest time of vertex)
  2. 事件的最晚发生时间ltv(latest time of vertex)
  3. 活动的最早开工时间ete(earliest time of edge)
  4. 活动的最晚开工时间lte(latest time of edge)
    我们由1和2求得3跟4,然后再根据ete[k]是否等于lte[k]来判断ak是否是关键活动

求etv的过程就是从头到尾找拓扑序列的过程,因此在求关键路径之前,需要先调用一次拓扑序列算法的代码来计算etv和拓扑序列表,为此,我们先在程序开始出声明几个全局变量

1
2
3
int *etv,*ltv; if /*事件最早发生时间和最迟发生时间数组*/
int stack2; /*用于存储拓扑序列的栈*/
int top2; /*用于stack2的指针*/

以下是改进过的拓扑序列算法

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
35
36
37
/*拓扑排序,用于关键路径计算*/
Status TopologicalSort(GraphAdjList GL)
{
EdgeNode *e;
int i,k,gettop;
int top=0; /*用于栈指针下标*/
int count=0; /*用于统计输出顶点的个数*/
int *stack; /*建栈将入度为0的顶点入栈*/
stack=(int *)malloc(GL->numVertexes *sizeof(int));
for(i = 0;i < GL->numVertexes; i++)
if(0 == GL->adjList[i].in)
stack[++top]=i;
top2=0; /初始化为0/
etv=(int*)malloc(GL->numVertexes *sizeof(int)); /事件最早发生时间/
for(i = 0;i < GL->numVertexes; i++)
etv[i]=0; /初始化为0/
stack2 = (int *)malloc(GL->numVertexes*sizeof(int)) /初始化/
while(top!=0)
{
gettop=stack[top--];
count++;
stack2[++top2]=gettop; /*将弹出的顶点序号压入拓扑序列的栈*/

for(e = GL->adjList[gettop].firstedge;e;e = e->next)
{
k=e->adjvex;
if(!(--GL->adjList[k].in))
stack[++top]=k;
if((etv[gettop]+e->weight)>etv[k]) /求各顶点事件最早发生时间值/
etv[k] = etv[gettop]+e->weight;
}
}
if(count < GL->numVertexes)
return ERROR;
else
return OK;
}

关键路径的算法

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
/*求关键路径,GL为有向网,输出GL的各项关键活动*/
void CriticalPath(GraphAdjList GL)
{
EdgeNode *e;
int i,gettop,k,j;
int ete,lte; /*声明活动最早发生时间和最迟发生时间变量*/
TopologicalSort(GL); /*求拓扑序列,计算数组etv和stack2的值*/
ltv=(int*)malloc(GL->numVertexes*sizeof(int)); /*事件最晚发生时间*/
for(i=0;i<GL->numVertexes;i++)
ltv[i]=etv[GL->numVertexes-1]; /*初始化ltv*/
while(top2!=0) /*计算ltv*/
{
gettop=stack2[top--]; /*将拓扑序列出栈,后进先出*/
for(e=GL->adjList[gettop].firstedge;e;e=e->next)
{ /*求各顶点事件的最迟发生时间ltv值*/
k=e->adjvex;
if(ltv[k]-e->weight<ltv[gettop]) /*求各顶点事件最晚发生时间ltv*/
ltv[gettop]=ltv[k]-e->weight;
}
}
for(j=0;j<GL->numVertexes;j++) /*求ete,lte和关键活动*/
{
for(e=GL->adjList[j].firstedge;e;e=e->next)
{
k=e->adjvex;
ete=etv[j]; /*活动最早发生时间*/
lte=ltv[k]-e->weight; /*活动最迟发生时间*/
if(ete == lte) /*两者相等即在关键路径上*/
printf("<v%d,v%d> length: %d,",GL->adjList[j].data,GL->adjList[k].data,e->weight);
}
}
}

整个关键路径的算法,拓扑排序O(n+e),初始化lte为O(n)…根据我们对时间复杂度的定义,所有的常数系数可以忽略,所以最终求得关键路径算法的时间复杂度仍然是O(n+e)