各位大神，void BFS()好像寫的不對，我執行出來是adcefb
跟題目不一樣，希望您給看看
#include <iostream>
using namespace std;
#define mvnum 10
#define Null 0
#define maxsize 10
#define error 0
#define ok 1
typedef char vertextype;
typedef int arctype;
typedef struct ArcNode
{
int AdjVex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct
{
vertextype data;
ArcNode *firstarc;
}Vnode,AdjList[mvnum];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
//__________________________________________________Queue
typedef int status;
typedef int QelemType;
typedef struct sqQueue
{
int front,rear;
QelemType *base;
}sqQueue;
status InitQueue(sqQueue &Q)
{
Q.base=new QelemType[maxsize];
if(!Q.base)return error;
Q.front=0;
Q.rear=0;
return ok;
}
status EnQueue(sqQueue &Q,QelemType e)
{
if((Q.rear+1)%maxsize==Q.front)
return error;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%maxsize;
return ok;
}
status DeQueue(sqQueue &Q,QelemType &e)
{
if(Q.front==Q.rear)return error;
e=Q.base[Q.front];
Q.front=(Q.front+1)%maxsize;
return ok;
}
bool QueueEmpty(sqQueue Q)
{
if(Q.rear==Q.front)return true;
else return false;
}
//____________________________________________Queue
int LocateVex(ALGraph G,vertextype p)
{
int xiabiao;
for(int i=0;i<G.vexnum;i++)
{
if(G.vertices[i].data=https://bbs.csdn.net/topics/=p)
{
xiabiao=i;
}
}
return xiabiao;
}
void CreateGraph(ALGraph &G)
{
int i,k,j;
cin>>G.vexnum>>G.arcnum;
for(i=0;i<G.vexnum;++i)
{
cin>>G.vertices[i].data;
G.vertices[i].firstarc=Null;
}
for(k=0;k<G.arcnum;++k)
{
vertextype v1,v2;
cin>>v1>>v2;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
ArcNode *p1=new ArcNode;
p1->AdjVex=j;
p1->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p1;
ArcNode *p2=new ArcNode;
p2->AdjVex=i;
p2->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p2;
}
}
bool visited[mvnum];
int FirstAdjVex(ALGraph G,int u)
{
ArcNode *p;
p=G.vertices[u].firstarc;
if(p) return p->AdjVex;
else return -1;
}
int NextAdjVex(ALGraph G,int u,int w)
{
ArcNode *p;
p=G.vertices[u].firstarc;
while(p->AdjVex!=w)
p=p->nextarc;
if(p) return p->AdjVex;
else return -1;
}
void BFS(ALGraph G,int v)
{
int w,u;
sqQueue Q;
ArcNode *p;
cout<<G.vertices[v].data;visited[v]=true;
p=G.vertices[v].firstarc;
InitQueue(Q);
EnQueue(Q,v);
while(!QueueEmpty(Q))
{
DeQueue(Q,u);
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
while(p!=Null)
{
w=p->AdjVex;
if(!visited[w]) BFS(G,w);
p=p->nextarc;
}
EnQueue(Q,w);
}
}
void BFSTraverse(ALGraph G)
{
int v;
for(v=0;v<G.vexnum;++v)
visited[v]=false;
for(v=0;v<G.vexnum;++v)
if(!visited[v]) BFS(G,v);
}
int main()
{
ALGraph G;
CreateGraph(G);
BFSTraverse(G);
return 0;
}
uj5u.com熱心網友回復：
FirstAdjVex和NextAdjVex函式，我也不太會轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/110372.html
標籤：疑難問題