复件 c4.1.cpp

多段图用邻接矩阵存储

#include<stdio.h>
#include"conio.h"
#define n 12 //顶点数
#define k 5 //段数
#define e 21 //图中的边数
#define MAX 1000
typedef int NodeNumber;
typedef int CostType;
NodeNumber cur = -1;
NodeNumber p[k];
CostType cost[n][n];
class FMultiGraph
{
public:
  void Creat_Graph(CostType cost[n][n]) //建邻接矩阵
  {
	int i,j,x,y,value;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			cost[i][j]=300;
    printf("Enter the node1 and node2 and the cost:\n");
	for(i=0;i<e;i++)
	{
       scanf("%d%d%d",&x,&y,&value);   
	   cost[x][y]=value;
	}
  }
 void outgraph(int cost[n][n])
 { 
	int i,j;
	printf("outgraph:\n");
    for(i=0;i<n;i++)
	{ 
		for(j=0;j<n;j++)
			printf(" %d",cost[i][j]);
		printf("\n");
	}
 }
  
 
 void Bp(CostType cost[n][n],NodeNumber p[k])
 { 
	 int i,j,length,temp,v[n],d[n];
	 for(i=0;i<n;i++) v[i]=0;
	 for(i=1;i<=n-1;i++)
     { 
		 for(length=MAX,j=i-1;j>=0;j--)
         if(cost[j][i]>0 && (cost[j][i])+v[j]<length)
          {length=cost[j][i]+v[j]; temp=j;}
		 v[i]=length;
		 d[i]=temp;
	 }
     p[0]=0;
     p[k-1]=n-1;
     for(i=k-2;i>=1;i--) (p[i])=d[p[i+1]];
 }
 void Outp(NodeNumber p[k])
 { 
	int i;
	for(i=0;i<k;i++)
		printf("%d ",p[i]);
 }
};
void main()
{   
   FMultiGraph pt;
    int i,j;
    for(i=0;i<n;i++)
	{
	    for(j=0;j<n;j++)
		cost[i][j]=300;
	}
   cost[0][1]=9;
   cost[0][2]=7;
   cost[0][3]=3;
   cost[0][4]=2;
   cost[1][5]=4;
   cost[1][6]=2;
   cost[1][7]=1;
   cost[2][5]=2;
   cost[2][6]=7;
   cost[3][7]=11;
   cost[4][6]=11;cost[4][7]=8;cost[5][8]=6;cost[5][9]=5;cost[6][8]=4;cost[6][9]=3;
   cost[7][9]=5;cost[7][10]=6;cost[8][11]=4;cost[9][11]=2;
   cost[10][11]=5;
   pt.Creat_Graph(cost);
   pt.outgraph(cost);
   printf("Bp ");
   pt.Bp(cost,p);
   pt.Outp(p);
}