//图的创建及深度优先和广度优先遍历；（原上原创版）

#include <iostream.h>
#define n  8  //声明图的顶点个数；
#define e  10  //声明图的边数；
#define max  n+1
int visited [max]; 
struct EdgeNode   {
                    int data;
                    EdgeNode  *next;
                  };
struct node   {
               EdgeNode  Adjlist[max];
              }g;
node creatlist(node g);
void dfs(node g,int i);
void bfs(node g,int i);
//==========================================
void main()
{   
    int i;
    cout<<"创建邻接表："<<endl;
    g=creatlist(g);
    cout<<"深度优先遍历结果："<<endl;
    for(i=0;i<max;i++)  visited[i]=0;
    dfs(g,1);
    cout<<endl<<"广度优先遍历结果："<<endl;
    for(i=0;i<max;i++)  visited[i]=0;
    bfs(g,1);
}
//=========创建邻接表==================================
node creatlist(node g)
{
    int i,j,k;
    EdgeNode  *p;
    for(i=0;i<max;i++)
    {
        g.Adjlist[i].data=i;
        g.Adjlist[i].next=NULL;
    }
   cout<<"输入"<<e<<"组两个接点值:"<<endl;
  for(k=0;k<e;k++)
  {
    cout<<"             第"<<k+1<<"组：";
    cin>>i>>j;
    p=new  EdgeNode;
    p->data=j;
    p->next=g.Adjlist[i].next;
    g.Adjlist[i].next=p;
  }
  return g;
}
//==========深度优先遍历==============================
void dfs(node g,int i)
{
   cout<<g.Adjlist[i].data<<"  ";//1 3 7 8 6 2 5 4 
   visited[i]=1;
   EdgeNode  *p;
   p=g.Adjlist[i].next;
   while(p!=NULL)
   {
    if(visited[p->data]==0)  dfs(g,p->data);
    p=p->next;
   }
  return;
}
//=========广度优先遍历==============================
void bfs(node g,int i)
{
 int q[max];//
 int f,r;
    EdgeNode  *p;
 f=r=0;
 cout<<g.Adjlist[i].data<<"   ";//1 3 2 7 6 5 4 8 
 visited[i]=1;
 q[++r]=i;
 while(f<r)
 {
  i=q[++f];
  p=g.Adjlist[i].next;
  while(p!=NULL)
  {
   if(visited[p->data]==0)
   {
    cout<<g.Adjlist[p->data].data<<"  ";
    visited[p->data]=1;
    q[++r]=p->data;
   }
   p=p->next;
  }
 }
 cout<<endl;
 return;
}
//==========================================


此帖转自:[url]http://www.programfan.com/team/team.asp?team_id=1346[/url]