lab_13.cpp

图的遍历

#include<iostream>
#include<fstream>
using namespace std;

void criticalpath(int graph[10][10],int n)
{
	int i,j,k,Ae,Al,w,key[10],count=1;
	int *Ve=new int[n];
	int *Vl=new int[n];
	for(i=0;i<n;i++) Ve[i]=0;
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			w=graph[i][j];
			if(w!=0){
				if(Ve[i]+w>Ve[j]) Ve[j]=Ve[i]+w;
			}
		}
	}
	for(i=0;i<n;i++) Vl[i]=Ve[i];
	for(j=n-2;j>0;j--)
	{
		for(k=j+1;k<n;k++)
		{
			w=graph[j][k];
			if(w!=0)
			{
				if(Vl[k]-w<Vl[j]) Vl[j]=Vl[k]-w;
			}
		}
	}
	k=0;
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			w=graph[i][j];
			if(w!=0)
			{
				Ae=Ve[i];
				Al=Vl[j]-w;
				if(Al==Ae) 
				{
					key[k++]=i;
					key[k++]=j;
				}
			}
		}
	}
	
	cout<<"Path(s)"<<count<<endl;
	cout<<"(1)"<<" ";
	cout<<key[0];
		for(j=1;j<n*2-1;j+=2)
		cout<<"->"<<key[j];

}



void main()
{
	ifstream file("data.txt");
	int n,i,j;
	file>>n;
	int graph[10][10];
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			file>>graph[i][j];
		}
	}
	criticalpath(graph,n);
}