24/11/2008 13:10:00
关键路径算法
// 假定采用邻接表法
int CriPath(const Graph &G)
{
// 正向拓扑排序,计算 ve
// 计算各顶点的入度
int *indegree = new int[G.vexnum];
for (int i=0; i<G.vexnum; i++) indegree[i] = 0;
// 遍历整个邻接表,计算入度值
for (int i=0; i<G.vexnum; i++)
{
for (ArcNode *p = G.vexes[i].firstarc; p!=NULL; p=p->nextarc)
{
indegree[p->adj]++;
}
}
// 记录入度为 0 的点
stack<int> S, T;
for (int i=0; i<G.vexnum; i++) if (indegree[i]==0) S.push(i);
// 逆扑排序,计算 ve