关键路径

[c++]代码库

#include<stdio.h>
int main(){
	int i, j, p=0;
	char graph[10][10]={{0,1,0,0,0,0,0,0,0,0},
						{0,0,1,0,0,0,0,0,0,0},
						{0,0,0,0,1,1,0,0,0,0},
						{0,0,0,0,0,1,0,0,0,0},
						{0,0,0,0,0,0,1,0,0,0},
						{0,0,0,0,0,0,0,1,0,0},
						{0,0,0,0,0,0,0,0,1,0},
						{0,0,0,0,0,0,0,0,1,0},
						{0,0,0,0,0,0,0,0,0,1},
						{0,0,0,0,0,0,0,0,0,0}};
	int judge[10]={0};//辅助数组
	int path[10];//路径数组
	int flag=1;
	while(flag != 0)
	{	
		flag = 0;
		for(j=0;j<10;j++)
		{
			//如果没有找过，
			if(judge[j]!=-1)
			{
				judge[j]=0;
				for(i=0;i<10;i++)
				{
					//将j列的所有元素之和赋给judge[j]
					judge[j]=judge[j]+graph[i][j];
				}
			} 
		}
		for(i=0;i<10;i++)
		{
			//如够judge[i]，也就是该列元素之和为0
			//则该节点为根节点，并存放到path[]数组中，p后移
			if(judge[i]==0)
			{
				path[p]=i;
				p++;
				//将列中有1的元素置为0；
				for(int q=0;q<10;q++)
					graph[i][q]=0;
				judge[i]=-1;//是否已经找过
			}
		}
	    
		for(i=0;i<10;i++)
		{
			//如果没有找过，将flag赋值为1，重新查找
			if(judge[i]!=-1)
			{
				flag = 1;
			}
		}
		
	}
	printf("p关键路径为：");
	for(i=0;i<10;i++)
	{
		printf("%4d",path[i]);

	}
	printf("\n");
	return 0;
}