为什么遍历老是错误

43 阅读 0 评论 29 点赞

我是靠谱客的博主高大戒指，最近开发中收集的这篇文章主要介绍为什么遍历老是错误，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include<iostream>
#include<queue>
using namespace std;
#define MVNum 100
#define OK 1
#define ERROR -1
#define OVERFLOW -2
#define MaxInt 100
#define MAXQSIZE 100
typedef int status;
typedef int VerTexType;
typedef int ArcType;
typedef int QElemType;
typedef int OtherInfor;
typedef struct
{
QElemType *base;
int front;
int rear;
}SqQueue;
typedef struct
{
VerTexType vexs[MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *NextAdjVex;
OtherInfor info;
}ArcNode;
typedef struct VNode
{
VerTexType date;
ArcNode *FirstAdjVex;

}VNode,AdjList[MVNum];
int LocateVex(AMGraph G,VerTexType v)
{
int i;
for(i=0;i<G.vexnum;++i)
  if(v==G.vexs[i])
   return i;
  else
   return ERROR;
}
status CreatUDN(AMGraph &G);
void DFS(AMGraph G,int v);
void BFS(AMGraph G,int v);
void DFSTraverse(AMGraph G);
status InitQueue(SqQueue &Q);
status EnQueue(SqQueue &Q, int e);
status DeQueue(SqQueue &Q,int &e);
status CreatUDN(AMGraph &G)
{
int i,j,k,w,v1,v2;
cout << "输入顶点数、边数" << endl;
cin>>G.vexnum>>G.arcnum;
for(i=0;i<G.vexnum;i++)
{
  cout << "输入点的信息" << endl;
  cin>>G.vexs[i];
}
for(i=0;i<G.vexnum;++i)
{
  for(j=0;j<G.vexnum;++j)
  {
   G.arcs[i][j]=0;
  }
}
for(k=0;k<G.arcnum;++k)
{
  cout << "输入一条边依附的顶点 " << endl;
  cin>>v1>>v2;
  //i=LocateVex(G,v1);
  //j=LocateVex(G,v2);
  G.arcs[v1-1][v2-1]=1;
  G.arcs[v2-1][v1-1]=G.arcs[v1-1][v2-1];
}
return OK;
}
int visited[MVNum];
void DFS(AMGraph G,int v)
{
int w;
cout<<v;visited[v]=true;
for(w=0;w<G.vexnum;w++)
  if((G.arcs[v][w]!=0)&&(!visited[w]))
   DFS(G,w);
}
status InitQueue(SqQueue &Q)
{
Q.base=new QElemType[MAXQSIZE];
if(!Q.base) exit(OVERFLOW);
Q.front=Q.rear=0;
return OK;
}
status EnQueue(SqQueue &Q, int e)
{
    if((Q.rear+1)%MAXQSIZE==Q.front)
        return ERROR;
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return OK;
}
status DeQueue(SqQueue &Q,int &e)
{
if(Q.front==Q.rear)
return ERROR;
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
status QueueEmpty(SqQueue Q)
{
    if(Q.rear==Q.front)
        return OK;
else
        return ERROR;
}
int FirstAdjVex(AMGraph G,int v)
{/*v的第一个邻接点*/
    int i;
    for(i=0;i<G.vexnum;++i)
    {
        if(G.arcs[v][i]==1&&visited[i]==false)
            return i;
    }
    return ERROR;
}
int NextAdjVex(AMGraph G,int v,int w)
{/*v相对于w的下一个邻接点*/
    int i;
    for(i=w;i<G.vexnum;++i)
    {
        if(G.arcs[v][i]==1&&visited[i]==false)
            return i;
    }
    return ERROR;
}
void BFS(AMGraph G,int v)
{
int u,w;
SqQueue Q;
cout<<v;visited[v]=true;
InitQueue(Q);
EnQueue(Q,v);
while(!QueueEmpty(Q))
{
  int w;
  DeQueue(Q,u);
  for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
  if(!visited[w])
  {
   cout<<w;visited[w]=true;
   EnQueue(Q,w);
  }
}
}
int main()
{
int i,v;
AMGraph G;
CreatUDN(G);
cout<<"深度优先遍历："<< endl;
DFS(G,v);
cout<<"广度优先遍历："<< endl;
BFS(G,v);
}