A_yue.

#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#defineINFINITY INT_MAX
#define MAX_VERTEX_NUM 20
#define MAXQSIZE 30
enum BOOL {False,True};
typedef struct ArcNode{
int adjvex;              
    struct ArcNode *nextarc;
int *info;
}ArcNode;  
typedef struct VNode{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
ArcNode* AdjList[MAX_VERTEX_NUM];
int vexnum,arcnum;      
int GraphKind;    
}Graph;   
typedef struct{
int  base[MAXQSIZE]; //初始化的动态分配存储空间
int front;           
int rear;            
}SqQueue; 
BOOL visited[MAX_VERTEX_NUM]; 
void CreateGraph(Graph &G)
{
int i;
int start,end,weight; 
ArcNode *s;
for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; //初始化指针数组
for(i=1;i<=G.arcnum;i++)
{
scanf("%d,%d,%d",&start,&end,&weight);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.AdjList[start];
s->adjvex=end;
G.AdjList[start]=s;
if(G.GraphKind==0)
{
s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.AdjList[end];
s->adjvex=start;
G.AdjList[end]=s;
}
}
}

int FirstAdjVex(Graph G,int v)
{
if(!G.AdjList[v]) return 0;
else return(G.AdjList[v]->adjvex);
}
int NextAdjVex(Graph G,int v,int u)
{
ArcNode *p;
p=G.AdjList[v];
while(p->adjvex!=u) p=p->nextarc; 
if(p->nextarc==NULL) return 0; 
else return(p->nextarc->adjvex); 
}

void Initial(SqQueue &Q)      
{
Q.front=Q.rear=0; 
}
BOOL QueueEmpty(SqQueue Q)
{ 
if(Q.front==Q.rear) return True;
else return False;
}

BOOL EnQueue(SqQueue &Q,int e)
{
if((Q.rear+1)%MAXQSIZE==Q.front) return False;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return True;
}

BOOL DeQueue(SqQueue &Q,int &e)
{
if(Q.front==Q.rear) return False;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return True;
}
void DFS(Graph G,int i)
{
int w;
visited[i]=True;  
printf("%d->",i);
for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w))
   if(!visited[w]) DFS(G,w); 
}
void DFSTraverse(Graph G)
{
int i;
printf("DFSTraverse:");
for(i=1;i<=G.vexnum;i++) visited[i]=False; 
for(i=1;i<=G.vexnum;i++)
     if(!visited[i]) DFS(G,i); 
printf("\b\b  \n");
}



void BFSTraverse(Graph G)
{
int i,u,w;
SqQueue Q; 
printf("BFSTreverse:");
for(i=1;i<=  G.vexnum;i++)  visited[i]=False; 
Initial(Q);  
for(i=1;i<=G.vexnum;i++)
   if(!visited[i])
     {visited[i]=True; 
      printf("%d->",i);
      EnQueue(Q,i);     
      while(!QueueEmpty(Q)) 
       {DeQueue(Q,u);  
for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
  if(!visited[w]) 
     {visited[w]=True;
      printf("%d->",w);
      EnQueue(Q,w);
     }
       }
     }
printf("\b\b  \n");
}



int main(){
Graph G;
char j='y';
while(j!='N'&&j!='n')
{
printf("请输入要生成的图的种类，0---无向图，1---有向图(0/1):");
scanf("%d",&G.GraphKind);
printf("请输入顶点数和弧数及权值：");
scanf("%d,%d",&G.vexnum,&G.arcnum);
CreateGraph(G);
DFSTraverse(G);
BFSTraverse(G);
printf("图遍历完毕，继续进行吗?(Y/N)");
scanf(" %c",&j);
}
}
/*
8,5
8,4
4,2
5,2
2,1
7,6
6,3
7,3
3,1

*/