深度优先搜索、广度优先搜索及其生成树

#include<iostream.h>
#include<malloc.h>
#define MAXVEX 30
typedef  struct vertextype
{ 
	char nam[10];
}name;

typedef struct edgenode 
{
	int adjvex;
	int value;
struct edgenode *next;
}arcnode;

typedef struct vexnode
{
	name data;
	arcnode *firstarc;
}vheadnode;
typedef struct
{
	int n,e;
	vheadnode vhnode[MAXVEX];
}adjlist;

int count=0;

     int createadjlist(adjlist *&g)
     {
		int i,b,t,w;
     	arcnode *p,*q;
     	g=(adjlist *)malloc(sizeof(adjlist));
     	cout<<"请输入顶点数，边数：";
     	cin>>g->n>>g->e;
         for(i=0;i<g->n;i++)
         {

			 cout<<"  序号为"<<i<<"的顶点信息："; 
             cin>>g->vhnode[i].data.nam;
             g->vhnode[i].firstarc=NULL;
             cout<<endl;
         }
         for(i=0;i<g->e;i++)
         {
            cout<<" 序号为"<<i<<"边=>";
            cout<<" 起点序号 终点序号 权值：";
            cin>>b>>t>>w;
            if(b<0||b>g->n)
            {
				 cout<<"输入的起点序号不存在！"<<endl;
				 return 0;
            }
            if(t<0||t>g->n)
            {
				cout<<"输入的重点序号不存在！"<<endl;
				return 0;
            }
            p=(arcnode *)malloc(sizeof(arcnode));
            p->value=w;p->adjvex=t;
            p->next=g->vhnode[b].firstarc;
            g->vhnode[b].firstarc=p;
            q=(arcnode *)malloc(sizeof(arcnode));
            q->value=w;q->adjvex=b;
            q->next=g->vhnode[t].firstarc;
            g->vhnode[t].firstarc=q;
         }
         return 1;
     }

     void display(adjlist *g)
     {
		 int i;
		 arcnode *p;
		 cout<<"图的邻接表表示如下："<<endl;
		 for(i=0;i<g->n;i++)
		 {
			 cout<<"["<<i<<","<<g->vhnode[i].data.nam<<"]=>";
			 p=g->vhnode[i].firstarc;
			  while(p!=NULL)
			  {
				  cout<<"("<<p->adjvex<<","<<p->value<<")->";
				  p=p->next;
			  }
		 cout<<"^\n";
		 }
     }
     void bfs(adjlist *g,int vi)//广度优先搜索
     {
		 int i,v,visited[MAXVEX],count;
		count=0;
		int Q[MAXVEX],front=0,rear=0;
		arcnode *p;
		 for(i=0;i<g->n;i++)
         visited[i]=0;
		visited[vi]=1;
		cout<<vi<<" ";
		count++;
		 rear=(rear=1)%MAXVEX;
		Q[rear]=vi;
        while(front!=rear)
		{
         front=(front+1)%MAXVEX;
         v=Q[front];
         p=g->vhnode[v].firstarc;
            while(p!=NULL)
            {   
				if(visited[p->adjvex]==0)
				{   
					visited[p->adjvex]=1;
					cout<<p->adjvex<<" ";
					count++;
					if(count%5==0)cout<<endl;
					rear=(rear+1)%MAXVEX;
					Q[rear]=p->adjvex;
				}
              p=p->next;
            }
        }
     }
     void dfs(adjlist *g,int vi,int visited[])
     {
		 arcnode *p; 
         visited[vi]=1;
         cout<<vi<<" ";
         count++;
         if(count%5==0)cout<<endl;
            p=g->vhnode[vi].firstarc;
			while(p!=NULL)
			{
				if(visited[p->adjvex]==0)
				dfs(g,p->adjvex,visited);
				 p=p->next;
			}
     }
            void dfsb(adjlist *g,int start,int visited[])
            {
				arcnode *p;
                visited[start]=1;
                p=g->vhnode[start].firstarc;
               while(p!=NULL)
			   {        
				   if(visited[p->adjvex]==0)
                 {
                     cout<<"("<<start<<","<<p->adjvex<<")";
                     count++;
                     if(count%5==0)cout<<endl;
                     dfsb(g,p->adjvex,visited);
                 }
                 p=p->next;
			   }
            }
         
	void bfsb(adjlist *g,int vi)
	{
		int i,v,visited[MAXVEX];
		int count=0;
        int Q[MAXVEX],front=0,rear=0;
        arcnode *p;
        for(i=0;i<g->n;i++) visited[i]=0;
        visited[vi]=1;
        rear=(rear=1)%MAXVEX;
        Q[rear]=vi;
        while(front!=rear)
		{
           front=(front+1)%MAXVEX;
           v=Q[front];
           p=g->vhnode[v].firstarc;
           while(p!=NULL)
           {   
				if(visited[p->adjvex]==0)
				{   
					visited[p->adjvex]=1;
					cout<<"("<<v<<","<<p->adjvex<<")";
					count++;
					if(count%5==0) cout<<endl;
					rear=(rear+1)%MAXVEX;
					Q[rear]=p->adjvex;
				}
				p=p->next;
            }
       }
	}
     void main()
     {
	    adjlist *g;
        createadjlist(g);
        display(g);
        int s;
		cout<<"请输入起点位置："<<endl;
		cin>>s;
		int visited[MAXVEX];
		 for(int i=0;i<g->n;i++)
         visited[i]=0;
		cout<<"深度优先搜索序列：";
		dfs(g,s,visited);
		cout<<endl;
		cout<<"广度优先搜索序列：";
		count=0;
         bfs(g,s);
         cout<<endl;
		cout<< "深度优先搜索生成树边集："<<endl;
        for(i=0;i<g->n;i++)
         visited[i]=0;
        count=0;
		 dfsb(g,s,visited);
		cout<<endl;
		cout<< "广度优先搜索生成树边集："<<endl;
       count=0;
         bfsb(g,s);
     }