liaoxj 我的资料 - 大傻测试空间！

空间管理您的位置: 51Testing软件测试网 » 大傻测试空间！ » 我的资料

管理给我的留言

myjeya | 2011-08-29 16:36:22: 能加我嗎50630786，我是工作兩年的測試員

summertears | 2011-05-19 22:51:24: 学习来啦群主

天上的星星 | 2011-05-18 17:25:45: 悄悄话，只给空间主人查看...

jijy2010 | 2010-12-20 15:12:40: 嗨，，，，，

张艺文 | 2010-12-11 19:59:00: #include<iostream.h>
struct ArcNode//定义边表结点
{ int adjvex;//邻接点域
   ArcNode *next;
};
template <class T>
struct VertexNode //定义顶点表结点
{
   T vertex;//
   ArcNode *firstedge;
};
const int MaxSize=10; //图的最大顶点数
int visited [MaxSize];
template <class T>
class ALGraph
{
public:
   ALGraph(T a[ ], int n, int e);  //n是顶点数，e是边数
   ~ALGraph(){}
   void DFSTraverse(int v);
   void BFSTraverse(int v);
  private:
   VertexNode<T> adjlist[MaxSize]; //??????????
   int vertexNum, arcNum;
};
template <class T>
ALGraph<T>::ALGraph(T a[ ], int n, int e)
{
vertexNum=n; arcNum=e;
int i,j,k;
ArcNode  *s;
ArcNode  *p;
for (i=0; i<vertexNum; i++)
//输入顶点信息，初始化边表
{
   adjlist[i].vertex=a[i];
   adjlist[i].firstedge=NULL; // 以上两句是什么意思？？？？一个链表还是  vertexNum个链表？？
}
for (k=0; k<arcNum; k++)
   //输入边的信息存储在边表中
   {
      cin>>i>>j;
      s=new ArcNode;
   s->adjvex=j;
   s->next=adjlist[i].firstedge;
      adjlist[i].firstedge=s;
   p=new ArcNode;
      p->adjvex=i;
      p->next=adjlist[i].firstedge;
   adjlist[i].firstedge=p;
   }
}
template <class T>
void ALGraph<T>::DFSTraverse(int v)
{
ArcNode *p;
int j;
cout<<adjlist[v].vertex;  visited[v]=1;
p=adjlist[v].firstedge;
while (p!=NULL)
{
      j=p->adjvex;
      if (visited[j]==0) DFSTraverse(j);
p=p->next;
}
}
template <class T>
void ALGraph<T>::BFSTraverse(int v)
{
int Q[MaxSize],front,rear,j;
ArcNode *p;
front=rear=-1; //假设采用顺序队列且不会发生溢出
front=rear=-1;
cout<<adjlist[v].vertex; visited[v]=1; Q[++rear]=v;
while (front!=rear)
{
   v=Q[++front]; p=adjlist[v].firstedge;
   while (p!=NULL)
   {
      j= p->adjvex;
      if (visited[j]==0) {
         cout<<adjlist[j].vertex;  visited[j]=1; Q[++rear]=j;
      }
      p=p->next;
   }
   if(visited[v+1]==0) v=v+1;
}
}
void main()
{
  int a[5]={0,1,2,3,4};
ALGraph<int> graph(a,5,4);

graph.BFSTraverse(0);

}
2010-12-15 09:20:52
不明白你的留言