51Testing软件测试论坛

标题: 新手！可以请各位前辈指点吗？？？求解 [打印本页]

作者: 张艺文 时间: 2010-12-11 19:27
标题: 新手！可以请各位前辈指点吗？？？求解
#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>:

FSTraverse(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);

}

构造图，遍历图！应用到实际当中有什么用？哪里需要类似图的代码？？

作者: heng612 时间: 2010-12-20 17:53

好怀念C语音啊？好久没有看过了？期待别人解决版主的问题

欢迎光临 51Testing软件测试论坛 (http://bbs.51testing.com/)