数据结构，数据结构与算法
应用背景
学生选修课程问题
顶点——表示课程
有向弧——表示先决条件，若课程i是课程j的先决条件，则图中有弧（i,j）
学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业——拓扑排序
拓扑序列是有向无环图中各顶点构成的有序序列。该序列满足如下条件：如果图中一顶点vi到另一顶点vj存在一条路径，那么vj在此图的拓扑排序序列中位于vi之后。
有向无环图(DAG)和 AOV网
有向无环图”（Directed Acyclic Graph，简称DAG
AOV网 (Activity On Vertex network): 一个“可行的” AOV 网络必须是DAG。否则图中有回路，从而就不能确定回路中的活动究竟哪个先实施。
顶点表示活动，
弧表示活动间的优先关系，
注意：
AOV网中的弧表示活动之间存在某种制约关系：若
void ToplogicalSort ( Graph G, int TopNum[ ] )
{
int Counter; /* 拓扑序号，用以标识每个顶点输出的次序*/
int v, w;
int *InDegree = (int *)malloc( G.n * sizeof(int) );
GetInDegree(G, InDegree); /* 计算图G中各顶点的入度 */
for( Counter = 0; Counter < G.n; Counter++ ) {
v = FindNewVertexOfDegreeZero( );
/* 查找入度为0的顶点，若找到，则返回顶点在顶点数组的下标。若找不到入度为0的顶点，返回-1 */
if ( v == -1 ) {
printf( “图存在环路”);
break;
}
TopNum[v] = Counter;
for( G中关于v 的每个邻接点w )
Indegree[w]--; /* 与顶点v相连的各顶点的入度减1 */
}
}
void ToplogicalSort ( GraphAdjList GL, int * TopNum )
{
Queue queue; EdgeNode *p; int Counter = 0; int v, w;
//int *InDegree = (int *)malloc( G.n * sizeof(int) );
// GetInDegree(G, InDegree); /* 计算图G中各顶点的入度 */
queue = InitQueue( GL->numVertexes ); /* 创建空队列 */
for( v = 0; v <GL->numVertexes; v++ )
if( GL->adjList[v].in==0 ) EnQueue( &queue, v );
while( ! QueueEmpty(queue) ) {
v = DeQueue( &queue);
TopNum[v] = ++Counter; /* 赋顶点拓扑排序序号 */
for( p=GL->adjList[v].firstedge;p!=NULL;p=p->next)
if( --GL->adjList[p->adjvex].in == 0 )
EnQueue( &queue, p->adjvex );
}
if( Counter != GL->numVertexes )
printf( "图存在环路\n" );
DisposeQueue(&queue); /* 释放队列空间*/
//free(InDegree);
}
关键路径
与AOV网相对应的是AOE(Activity On Edge) ，是边表示活动的有向无环图。
顶点表示事件(Event)，每个事件表示在它之前的活动已完成，在它之后的活动可以开始；
弧表示活动，弧上的权值表示相应活动所需的时间或费用AOV网与AOE网
拓扑排序主要是为解决一个工程能否顺利进行的问题。
关键路径是解决工程完成需要的最短时间问题。
AOV网与AOE网的区别：
AOV网，顶点表示活动，边描述活动之间的制约关系
AOE网，边上的权值表示活动持续的时间，
建立在活动之间制约关系没有矛盾的基础上，
讨论完成整个工程至少需要多少时间；或者为缩短完成工程所需时间，应当加快哪些活动等问题。
路径长度—路径上各活动持续时间之和
关键路径—从源点到汇点具有最大路径长度的路径
关键活动—关键路径上的活动。关键活动是影响整个工程的关键，延迟就会影响整个工期的活动。
最早发生时间—设v0是起点，从v0到vi的最长路径长度称为事件vi的最早发生时间，即是以vi为尾的所有活动的最早发生时间。
求AOE中关键路径和关键活动
⑴ 算法思想
① 利用拓扑排序求出AOE网的一个拓扑序列；
② 从拓扑排序的序列的第一个顶点(源点)开始，按拓扑顺序依次计算每个事件的最早发生时间ve(i) ；
从拓扑排序的序列的最后一个顶点(汇点)开始，按逆拓扑顺序依次计算每个事件的最晚发生时间vl(i) ；
求出各活动的最早发生时间e(i)和最晚发生时间l(e),同时求出ai的时间余量，时间余量=0的那些活动就是关键活动。
最短路径
用带权的有向图表示一个交通运输网，图中：
顶点：城市
边：城市间的交通联系
权：此线路的长度或沿此线路运输所花的时间或费用等
问题：
两地之间是否有通路?
在有多条通路的情况下，哪条最短?
将一条路径的起始顶点称为源点，最后一个顶点称为终点。
单源点最短路径
对于给定的有向图G=(V，E)及单个源点V0，求V0到G的其余各顶点的最短路径。
针对单源点的最短路径问题，Dijkstra提出了一种按路径长度递增次序产生最短路径的算法，即迪杰斯特拉(Dijkstra)算法。
求最短路径步骤
初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值
若存在 V0,Vi，为V0,Vi弧上的权值
若不存在 V0, Vi，为
从T中选取一个其距离值为最小的顶点W，加入S
对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值
重复上述步骤，直到S中包含所有顶点，即S=V为止
算法实现
图用带权邻接矩阵存储
数组dist[ ]存放当前找到的从源点V0到每个终点的最短路径长度（这些路径中间只经过集合S中的顶点），其初态为图中直接路径权值
数组pre[ ]表示从V0到各终点的最短路径上，此顶点的前一顶点的序号；若从V0到某终点无路径，则用0作为其前一顶点的序号