(18)--第5章 图-拓扑排序+关键路径.ppt

第6章图;有向无环图及其应用;何谓“拓扑排序”？;例如：对于下列有向图;B;教学计划的制定;拓扑排序算法思想;C1;拓扑排序算法描述;CountInDegree(G,indegree);

//对各顶点求入度

InitStack(S);

for(i=0;iG.vexnum;++i)

if(!indegree[i])Push(S,i);

//入度为零的顶点入栈;count=0;//对输出顶点计数

while(!EmptyStack(S)){

Pop(S,v);++count;printf(v);

for(w=FirstAdj(v);w;w=NextAdj(G,v,w)){

--indegree(w);//弧头顶点的入度减一

if(!indegree[w])Push(S,w);

//新产生的入度为零的顶点入栈

}

}

if(countG.vexnum)printf(“图中有回路”);对如图所示的图进行拓扑排序，可以得到不同的拓扑序列个数是。;关键路径;;关键路径：路径长度最长的路径

（路径长度是指路径上各活动持续时间之和，不是路径上弧的数目）

;2、如何求关键活动？;a;a;a;a;假设第i条弧为j,k

则对第i项活动言

e(i)=ve(j)；

;;;假设第i条弧为j,k

则对第i项活动言

“活动(弧)”的最迟开始时间l(i)

l(i)=vl(k)–dut(j,k)；;;;六度空间理论分析与实现;【算法步骤】

①完成系列初始化工作：设变量Visit_Num用来记录路径长度不超过7的顶点个数，初值为0；Start为指定的一个起始顶点，置visited[Start]的值为true，即将Start标记为六度顶点的始点；辅助队列Q初始化为空，然后将Start进队。

②当队列Q非空，且循环次数小于7时，循环执行以下操作（统计路径长度不超过7的顶点个数）：

队头顶点u出队；

?依次检查u的所有邻接点w，如果visited[w]的值为false，则将w标记为六度顶点；

?路径长度不超过7的顶点个数Visit_Num加1；

?将w进队。

③退出循环时输出从顶点Start出发，到其他顶点长度不超过7的路径的百分比。;【算法描述】

voidSixDegree_BFS(GraphG,intStart)

{//通过广度优先搜索方法遍历G来验证六度空间理论，Start为指定的一个起点

Visit_Num=0; //记录路径长度不超过7的顶点个数

visited[Start]=true;//置顶点Start访问标志数组相应分量值为true

InitQueue(Q);//辅助队列Q初始化，置空

EnQueue(Q,Start);//Start进队

for(len=1;len=7!QueueEmpty(Q);len++)//统???路径长度不超过7的顶点个数

{

DeQueue(Q,u);//队头顶点u出队

for(w=FirstAdjVex(G,u);w=0;w=NextAdjVex(G,u,w))

//依次检查u的所有邻接点w，FirstAdjVex(G,u)表示u的第一个邻接点

//NextAdjVex(G,u,w)表示u相对于w的下一个邻接点，w≥0表示存在邻接点

if(!visited[w]) //w为u的尚未访问的邻接顶点

{

visited[w]=true; //将w标记为六度顶点

Visit_Num++; //路径长度不超过7的顶点个数加1

EnQueue(Q,w); //w进队

}//if

}//结束至多7次for循环

cout100*Visit_Num/G.vexnum;

//输出从顶点Start出发，到其他顶点长度不超过7的路径的百分比

}

?