#include "stdafx.h"
#include <iostream.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 20

typedef struct ArcNode
{
 int adjvex;    //弧鄰接的頂點
 char info;     //弧相關(guān)信息
 struct ArcNode *nextarc;   //指向下一條弧的指針
}ArcNode;
typedef struct Vnode
{
 char data;     //結(jié)點信息
 ArcNode *link;    //指向第一個和該頂點相連的弧
}Vonde,AdjList[MAX+1];
//圖結(jié)構(gòu)體
typedef struct
{
 AdjList vertices;
 int vexnum;   //頂點
 int arcnum;    //邊數(shù)
}ALGraph;

void CreateGraph(ALGraph &G)
{
 int i,j,s,d;
 ArcNode *p;
 //輸入結(jié)點信息
 for(i=1;i<=G.vexnum;i++)
 {
  getchar();
  printf("第%d個結(jié)點信息(char型):",i);
  scanf("%c",&G.vertices[i].data);
  G.vertices[i].link=NULL;
 }
 //輸入邊的信息
 for(i=1;i<=G.arcnum;i++)
 {
  printf("第%d條----起點序號，終點序號:",i);
  scanf("%d%d",&s,&d);
  p=(ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex=d;
  p->info=G.vertices[d].data;    //存儲邊的權(quán)值等信息，此處以頂點數(shù)據(jù)代替
  p->nextarc=G.vertices[s].link;   //p插入頂點S的鄰接表中
  G.vertices[s].link=p;
 }
}
 //深度遍歷的算法實現(xiàn)
 void DFS(AdjList g,int v,int visited[])
 {
  ArcNode *w;
  int i;
  printf("%d",v);
  visited[v]=1;
  w=g[v].link;
  while(w!=NULL)
  {
   i=w->adjvex;
   if(visited[i]==0)
    DFS(g,i,visited);
   w=w->nextarc;
  }
 }
 //廣度優(yōu)先遍歷圖的算法實現(xiàn)
void bfs(AdjList g,int v, int visited[])
 {
  int qu[MAX],f=0,r=0;
  ArcNode *p;
  printf("%d",v);
  qu[0]=v;
  while(f<=r)
  {
   v=qu[f++];
   if(visited[v]==0)
   {
    v=p->adjvex;
    if (visited[v]==0)
    {
     visited[v]=1;
     printf("%d",v);
     qu[++r]=v;
    }
    p=p->nextarc;
   }
  }
 }
   void Traver(AdjList g,int n,int id)
 {
  int i;
  static int visited[MAX];
  for(i=1;i<=n;i++)
   visited[i]=0;
  for(i=1;i<=n;i++)
   if(visited[i]==0)
   {
    if(id==1)  DFS(g,i,visited);
    if(id==2)   DFS(g,i,visited);
   }
 }
int main(int argc, char* argv[])
{
        ALGraph G;
  int id;
  printf("輸入結(jié)點數(shù)和邊數(shù)：");
   scanf("%d%d",&G.vexnum,&G.arcnum);
  CreateGraph(G);
        printf("選擇深度遍歷或者廣度遍歷:(1 DFS,2 BFS)");
  scanf("%d",&id);
  Traver(G.vertices,G.vexnum,id);

 return 0;
}