圖的一系列算法（待續）

#include<iostream>
using namespace std;

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum {DG, DN, UDG, UDN} GraphKind;

//鄰接矩陣
typedef struct ArcCell
{
	int key;    //對於無權圖，用1或0表示相鄰否，對帶權圖，則為權值類型
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   //這種定義數組的方式一定要記住

typedef struct {
   int vexs[MAX_VERTEX_NUM];
   AdjMatrix arcs;
   int vexnum,arcnum; //圖的當前定點數和弧邊數
   GraphKind kind;
}MGraph;

//鄰接表
typedef struct ArcNode
{
     int adjvex;
	 struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode
{
	int key;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct {
	AdjList vertices;
	int vexnum,arcnum;
	GraphKind kind;
} ALGraph;

void CreateUD(MGraph &G)      //用鄰接矩陣無向圖
{  
   int i,j;
   cout<<"Input vexnum:"<<endl;
   cin>>G.vexnum;
   cout<<"Input arcnum:"<<endl;
   cin>>G.arcnum;
   for(  i=0; i<G.vexnum; ++i)
   {
	   for( j=0; j<G.vexnum; ++j)
	   {
		   G.arcs[i][j].key = 0;
	   }
   }
   int v1,v2;
   for( int k=0; k<G.arcnum; ++k)
   {
      cout<<"Input two index:"<<endl;
	  cin>>v1>>v2;
	  G.arcs[v1][v2].key=1;
	  G.arcs[v2][v1].key = G.arcs[v1][v2].key;  //有向圖和無向圖的區別
   }
   cout<<"Graph:"<<endl;
   for( i=0; i<G.vexnum; ++i)
   {
	   for( j=0; j<G.vexnum; ++j)
	   {
		   cout<<G.arcs[i][j].key<<" ";
	   }
	   cout<<endl;
   }
}


void CreateDG(ALGraph &G)      //用鄰接表創建有向圖
{
   int i;
   cout<<"Input vexnum:"<<endl;
   cin>>G.vexnum;
   cout<<"Input arcnum:"<<endl;
   cin>>G.arcnum;
   for( i=0; i<G.vexnum; i++)
   {
	   G.vertices[i].key=i;
	   G.vertices[i].firstarc=NULL;
   }
   int v1,v2;
   for( int k=0; k<G.arcnum; ++k)
   {
      cout<<"Input two index:"<<endl;
	  cin>>v1>>v2;
	  if( v1==v2 )
	  {
		  --k;
		  cout<<"two index are same, renew input:"<<endl;
		  continue;
	  }
	  ArcNode *node = (ArcNode *)malloc(sizeof(ArcNode));
	  node->adjvex=v2;
	  node->nextarc=NULL;
      if(G.vertices[v1].firstarc==NULL)
	  {
         G.vertices[v1].firstarc=node;
	  }
	  else
	  {   
		  ArcNode *next=G.vertices[v1].firstarc;
		  while(next->nextarc)
		  {
			  next=next->nextarc;
		  }
		  next->nextarc=node;
	  }
	  
   }
   for( int j=0; j<G.vexnum; j++)
   {
       cout<<G.vertices[j].key<<" :";
	   ArcNode *next=G.vertices[j].firstarc;
	   while( next!=NULL)
	   {
		   cout<<next->adjvex<<" ";
		   next=next->nextarc;
	   }
	   cout<<endl;
   }
}