123.txt

在Borland C++ Builder 实现 图的深度和广度遍历

	#include<iostream.h>
	typedef int elemtype;
	const int n=8;
	const int e=10;
	bool visited[n+1];
	class link
	{public:
	elemtype  data;
	link *next;
	};
	class GRAPH
	{
	 public:
	 link a[n+1];
	 void creatlink()
 {int i,j,k;
  link *s;
  for(i=1;i<=n;i++)
  {a[i].data=i;
  a[i].next=NULL;
  }
  for(k=1;k<=e;k++)
  {cout<<"请输入一条边";
   cin>>i>>j;
   s=new link;
   s->data=j;
   s->next=a[i].next;
   a[i].next=s;
   s=new link;
   s->data=i;
   s->next=a[j].next;
   a[j].next=s; }
   }
   void dfs(int i)
   {link *p;
    int h[n],z=0;
     cout<<a[i].data<<" ";
    h[z++]=a[i].data;
     visited[i]=true;
    p=a[i].next;
    while(z<n)
    {
    while(p!=NULL)
   {while(!visited[p->data])
   {cout<<a[p->data].data<<" ";
    h[z++]=a[p->data].data;
    visited[p->data]=true;
    p=a[p->data].next;
    }
     p=p->next;
     }
     p=a[h[z-2]].next; }
     }
     void bfs(int i)
     {int c[n+1];
     int front,rear;
      link *p;
      front=rear=0;
      cout<<a[i].data<<" ";
      visited[i]=true;
      rear++;c[rear]=i;
      while(front<rear)
      {front++;
      i=c[front];
      p=a[i].next;
      while(p!=NULL)
      {if(!visited[p->data])
      {cout<<a[p->data].data<<" ";
      visited[p->data]=true;
     rear++;
      c[rear]=p->data;
      }
     p=p->next; }
     }
     }
     };
void main()
{
link *p;int i;
 GRAPH G;
G.creatlink();
for(i=1;i<=n;i++)
{p=G.a[i].next;
cout<<G.a[i].data<<"->";
while(p->next!=NULL)
{cout<<p->data<<"->";
p=p->next;
}
cout<<p->data<<endl;
}
 for(i=1;i<=n;i++)
 visited[i]=false;
 cout<<endl<<"请输入深度优先搜索开始访问的顶点";
 cin>>i;
	cout<<endl<<"从"<<i<<"出发的深度优先搜索遍历序列为"<<endl;
 G.dfs(i);
 for(i=1;i<=n;i++)
 visited[i]=false;
 cout<<endl<<"请输入广度优先搜索开始访问的顶点";
 cin>>i;
 cout<<"从"<<i<<"出发的广度优先搜索遍历序列为"<<endl;
 G.bfs(i);
}