您的位置：程序门 -> 专题开发/技术/项目 -> 数据结构与算法

跪求关键路径的问题

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

跪求关键路径的问题

发表于：2007-01-24 21:14:05 楼主

在数据结构的图中,怎么在aol网络图中求得关键路径啊?
模糊的记得原来学的时候说过，从前面点推最大的,从后边退最小的,实在是没明白,各位帮忙啊,被一道题难住了!

发表于：2007-01-24 22:41:051楼得分:0

在数据结构的图中,怎么在aol网络图中求得关键路径啊?
模糊的记得原来学的时候说过，从前面点推最大的,从后边退最小的,实在是没明白,各位帮忙啊,被一道题难住了!

---------------------书上有的。1：先找个入度为0的节点，去掉和这个节点连接所有边。重复1就行了。

发表于：2007-01-25 23:21:522楼得分:0

找e（i)==l（i)的路径.

发表于：2007-01-26 20:43:043楼得分:0

3楼谢谢,我看书上也是这么说,找它两相等的,可怎么找啊???
给一个图,怎么找到那相等的点啊?
原来记得是什么从前往后推找最大的,从后往前找最小的.那从后往前最小的是什么意思啊?

发表于：2007-01-26 22:51:224楼得分:0

#include <stdio.h>
#include "stack.h "
#include "graph.h "

/*求各顶点的入度*/
void findid（const graph *g, int *id)
{
int i;
arcnode *p;
for（i=0;i <=g-> vernum-1;i++)
id[i] = 0;
for（i=0;i <=g-> vernum-1;i++)
{
p = g-> vertex[i].firstin;
while（p)
{
id[i]++;
p = p-> headlink;
}
}
}/*findid*/

/*g为有向网，t为返回的逆拓扑排序的栈，数组ve存放每个顶点的最早发生时间*/
int topoorder（const graph *g, stack t, int *ve)
{
int count, i, j, k;
arcnode *p;
int indegree[max_vertex_num]; //各顶点入度
stack s; //求拓扑排序的栈
initstack（&s);

findid（g, indegree);
for（i=0;i <=g-> vernum-1;i++) /*入度为0的顶点入栈*/
if（!indegree[i])
push（s, i);

for（i=0;i <=g-> vernum-1;i++) /*初始化最早发生时间*/
ve[i] = 0;

count = 0;
while（!isempty（s))
{
j = pop（s);
push（t, j);
count++;
p = g-> vertex[j].firstout;
while（p)
{
k = p-> headvex;
if（--indegree[k]==0)
push（s, k); /*若顶点入度减为0，则入栈*/
ve[k] = （ve[j]+p-> weight > ve[k])? （ve[j] + p-> weight): ve[k];
p = p-> taillink;
}
}

if（count <g-> vernum) /*图中有圈*/
return 0;
else
return 1;
}/*topoorder*/

/*关键路径算法*/
int criticalpath（graph *g)
{
int i, j, k, dut, ei, li, tag;
int ve[max_vertex_num]; //每个顶点的最早发生时间
int vl[max_vertex_num]; //每个顶点的最晚发生时间
arcnode *p;
stack t;
initstack（&t);

if（!topoorder（g, t, ve)) /*图中有圈，无关键路径*/
return 0;

for（i=0;i <=g-> vernum-1;i++) /*将各顶点事件的最迟发生时间初始化为汇点的最迟发生时间*/
vl[i] = ve[g-> vernum-1];

while（!isempty（t))
{
j = pop（t);
p = g-> vertex[j].firstout;
while（p)
{
k = p-> headvex;
dut = p-> weight;
if（vl[k]-dut <vl[j])
vl[j] = vl[k] - dut;
p = p-> taillink;
}
}

for（j=0;j <=g-> vernum-1;j++)
{
p= g-> vertex[j].firstout;
while（p)
{
k = p-> headvex;
dut = p-> weight;
ei = ve[j];
li =vl[k] -dut;
tag = （ei==li)? '* ': ' '; /*标记并输出关键活动*/
printf（ "%c-> %c: %d %d %d %c\n ", g-> vertex[j].data, g- > vertex[k].data,
dut, ei, li, tag);
p = p-> taillink;
}
}

return 1;
}/*criticalpath*/

发表于：2007-01-26 22:54:595楼得分:0

补充：图用十字链表表示，如下:

#define max_vertex_num 20 //最大顶点个数

typedef struct arcnode /*弧结点定义*/
{
int weight; //弧的权值
int tailvex; //弧尾顶点在图中的位置
int headvex; //弧头顶点在图中的位置
arcnode *taillink; //taillink指向与该弧具有同一弧尾的下一条弧
arcnode *headlink; //headlink指向与该弧具有同一弧头的下一条弧
}arcnode;

typedef struct vertexnode /*顶点结点定义*/
{
int data;
arcnode *firstin; //firstin指向第一条以该顶点为弧头的弧
arcnode *firstout; //firstout指向第一条以该顶点为弧尾的弧
}vertexnode;

typedef struct
{
vertexnode vertex[max_vertex_num];
int vernum; //图中顶点个数
int arcnum; //图中弧的条数
}graph;

发表于：2007-01-26 23:22:236楼得分:0

最早开始时间e（i)--从前往后遍历
最迟开始时间l（i)--从后往前按最长路径逐个减（如果要是邻接表存储,需要建立逆邻接表)

其他资讯