#include<iostream.h>
typedef char vextype;
const MAXVER=21;
typedef struct listnode      
{ 
 int adjvex;
 struct listnode* next;  
}listnode;//表結(jié)點(diǎn)                         
            
typedef struct
{   
 vextype data;
 listnode  *first;
}headnode;//頭結(jié)點(diǎn)

typedef struct
{ 
 headnode vexs[MAXVER];
    int vexnum,arcnum;
} ALgraph;//圖

void createALgraph(ALgraph &G)
{
    int i, s, d;
    listnode *p,*q;
    cout<<"輸入圖的頂點(diǎn)數(shù)和邊數(shù)：";
    cin>>G.vexnum>>G.arcnum;
    for(i=1;i<=G.vexnum;i++)
    { 
  cout<<"\n輸入第"<<i<<"個(gè)頂點(diǎn)信息："; 
  cin>>G.vexs[i].data;
  G.vexs[i].first=NULL;
    } //輸入第i個(gè)結(jié)點(diǎn)值并初始化第i個(gè)單鏈表為空  
 for(i=1; i<=G.arcnum; i++)
    { 
  cout<<"\n輸入第"<<i<<"條邊的始點(diǎn)和終點(diǎn)：";
        cin>>s>>d;//s為始點(diǎn)，d為終點(diǎn)
        p=new listnode;        p->adjvex=d;
        p->next=G.vexs[s].first;
        G.vexs[s].first=p;
  //將新建的以d為信息的表結(jié)點(diǎn)p插入s單鏈表的頭結(jié)點(diǎn)后
        q=new listnode;        
  q->adjvex=s;
        q->next=G.vexs[d].first;
        G.vexs[d].first=q;
  //將新建的以s為信息的表結(jié)點(diǎn)q插入d單鏈表的頭結(jié)點(diǎn)后
    }
}

int visited[MAXVER];//定義全局?jǐn)?shù)組遍歷visited
void dfs(ALgraph G, int v)//被遍歷的圖G采用鄰接表作為存儲結(jié)構(gòu)，v為出發(fā)頂點(diǎn)編號
{ 
 listnode *p;
 cout<<G.vexs[v].data;
 visited[v]=1;
 p=G.vexs[v].first;
 while(p!=NULL)
 {
  if(visited[p->adjvex]==0)  dfs(G,p->adjvex);
  //若p所指表結(jié)點(diǎn)對應(yīng)的鄰接頂點(diǎn)未訪問則遞歸地從該頂點(diǎn)出發(fā)調(diào)用dfs
  p=p->next;
    }
}

void dfsTraverse(ALgraph G)
{ 
 int v;
 //遍歷圖之前初始化各未訪問的頂點(diǎn)
 for(v=1; v<=G.vexnum; v++)
  visited[v]=0;
 //從各個(gè)未被訪問過的頂點(diǎn)開始進(jìn)行深度遍歷
 for(v=1;v<=G.vexnum;v++)
  if(visited[v]==0)   dfs(G,v);
}

void dsfComp(ALgraph G)
{  int v;
   //遍歷G以前，初始化visited數(shù)組為0
   for(v=1;v<=G.vexnum;v++)
         visited[v]=0;
   for(v=1;v<=G.vexnum;v++)
      if(visited[v]==0)
      {
    cout<<endl<<"\n一個(gè)深度遍歷連通分量為：";
          dfs(G,v);
   }
}

void BFS(ALgraph G, int v)
//從頂點(diǎn)編號v出發(fā)，廣度遍歷鄰接表存儲的圖G
{  
 int queue[MAXVER], front ,rear;
    listnode* p;
    front=rear=0;
    cout<<G.vexs[v].data;
    visited[v]=1;
    queue[++rear]=v;
    while(front!=rear)
 { 
  v=queue[++front];
  p=G.vexs[v].first;
  while(p!=NULL)
  {  
   if(visited[p->adjvex]==0)
   { 
    v=p->adjvex;
    cout<<G.vexs[v].data;
    visited[v]=1;
    queue[++rear]=v;
   }
   p=p->next;
  }
 }
}

void BFSTraverse(ALgraph G)
{
 int v;
 //遍歷G以前，初始化visited數(shù)組為0
 for(v=1;v<=G.vexnum;v++)
  visited[v]=0;
 for(v=1;v<=G.vexnum;v++)
  if(visited[v]==0)
   BFS(G,v);
}

void BFSComp(ALgraph G)
{ 
 int v;
 //遍歷G以前，初始化visited數(shù)組為0
 for(v=1;v<=G.vexnum;v++)
  visited[v]=0;
 for(v=1;v<=G.vexnum;v++)
  if(visited[v]==0)
  {
   cout<<endl<<"\n一個(gè)廣度遍歷連通分量為：";
   BFS(G,v);
  }
}

void main()
{
 ALgraph g;
 createALgraph(g);
 cout<<endl<<"深度遍歷結(jié)果為：";
 dfsTraverse(g);
 dsfComp(g);
 cout<<endl<<"廣度遍歷結(jié)果為：";
 BFSTraverse(g);
 BFSComp(g);
 cout<<endl;
}