图的一系列算法（待续）

#include<iostream>using namespace std;#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef 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;   }}