主题:[原创]跪求编程高手帮忙之图的遍历
邻接多重表图的遍历,运行不出来,请高手帮下忙,小妹感激涕零
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include <conio.h>
#include<malloc.h>
using namespace std;
#define MAX_VERTEX_NUM 30
struct EBox
{
int mark;
int ivex,jvex;
EBox *ilink,*jlink;
};
struct VexBox
{
int data;
EBox *firstedge;
};
struct AMLGraph
{
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,edgenum;
};
typedef struct QNode
{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int visited[MAX_VERTEX_NUM];
int LocateVex(AMLGraph ,int );
void Initilized(AMLGraph &G)
{
int i,j,k,n,m;
int va,vb;
EBox *p;
printf("请输入无向图的顶点数,边数\n ");
cin>>n>>m;
G.vexnum=n;
G.edgenum=m;
printf("请输入顶点的值:\n");
for(i=0;i<n;i++)
{
cin>>G.adjmulist[i].data;
G.adjmulist[i].firstedge=NULL;
}
printf("请输入每条边的两个端点:\n");
for(k=0;k<m;k++)
{
printf("第%d边",k+1);
cin>>va>>vb;
i=LocateVex(G,va);
j=LocateVex(G,vb);
p=(EBox*)malloc(sizeof(EBox));
p->mark=0;
p->ivex=i;
p->ilink=G.adjmulist[i].firstedge;
G.adjmulist[i].firstedge=p;
p->jvex=j;
p->jlink=G.adjmulist[j].firstedge;
G.adjmulist[j].firstedge=p;
}
}
int LocateVex(AMLGraph G,int u)
{
int i;
for(i=0;i<G.vexnum;++i)
{
if(G.adjmulist[i].data==u)
return i;
}
return -1;
}
int FirstAdjVex(AMLGraph G,int v)
{
int i;
i=LocateVex(G,v);
if(i<0)
return -1;
if(G.adjmulist[i].firstedge)
if(G.adjmulist[i].firstedge->ivex==i)
return G.adjmulist[i].firstedge->jvex;
else if(G.adjmulist[i].firstedge->jvex==i)
return G.adjmulist[i].firstedge->ivex;
else
return -1;
}
int NextAdjVex(AMLGraph G,int v,int w)
{
int i,j;
EBox *p;
i=LocateVex(G,v);
j=LocateVex(G,w);
if(i<0||j<0)
return -1;
p=G.adjmulist[i].firstedge;
while(p)
if(p->ivex==i&&p->jvex!=j)
p=p->ilink;
else if(p->jvex==i&&p->ivex!=j)
p=p->jlink;
else
break;
if(p&&p->ivex==i&&p->jvex==j)
{
p=p->ilink;
if(p&&p->ivex==i)
return p->jvex;
else if(p&&p->jvex==i)
return p->ivex;
}
if(p&&p->ivex==j&&p->jvex==i)
{
p=p->jlink;
if(p&&p->ivex==i)
return p->jvex;
else if(p&&p->jvex==i)
return p->ivex;
}
return -1;
}
void DFS(AMLGraph G,int v)
{
int j;
EBox *p;
if(visited[v]==1)
return;
visited[v]=1;
printf("%d\n",v);
p=G.adjmulist[v].firstedge;
while(p)
{
if(p->ivex==v)
j=p->jvex;
else
j=p->ivex;
if(visited[j]==0)
printf("<%d,%d>\n",v,j);
DFS(G,j);
if(p->ivex==v)
p=p->ilink;
else p=p->jlink;
}
}
void DFS(AMLGraph ,int);
void DFSTraverse(AMLGraph G)
{
for(int v=0;v<G.vexnum;v++)
visited[v]=0;
for( v=0;v<=G.vexnum;v++)
if(visited[v]==0)
DFS(G,v);
}
void InitQueue(LinkQueue &Q)
{ // 构造一个空队列Q
if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))
exit(0);
Q.front->next=NULL;
}
void EnQueue(LinkQueue &Q,int e)
{ // 插入元素e为Q的新的队尾元素
QueuePtr p;
if(!(p=(QueuePtr)malloc(sizeof(QNode))))
exit(0);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
int DeQueue(LinkQueue &Q,int &e)
{
QueuePtr p;
if(Q.front==Q.rear)
return -1;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
}
int QueueEmpty(LinkQueue Q)
{
if(Q.front->next==NULL)
return 1;
else
return 0;
}
void BFSTraverse(AMLGraph G)
{
int u,w,v;
LinkQueue Q;
for( v=0;v<G.vexnum;v++)
visited[v]=0;
InitQueue(Q);
for(v=0;v<G.vexnum;v++)
if(visited[v]==0)
{
printf("%d\n",v);
visited[v]=1;
EnQueue(Q,v);
while(QueueEmpty(Q)==0)
{
DeQueue(Q,u);
for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))
if(visited[w]==0)
{
printf("<%d,%d>\n",u,w);
visited[w]=1;
printf("%d\n",w);
EnQueue(Q,w);
}
}
}
}
void main()
{
AMLGraph G;
int v1,v2;
Initilized(G);
printf("深度优先搜索的结果:\n");
DFSTraverse(G);
printf("广度优先搜索的结果:\n");
BFSTraverse(G);
}
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include <conio.h>
#include<malloc.h>
using namespace std;
#define MAX_VERTEX_NUM 30
struct EBox
{
int mark;
int ivex,jvex;
EBox *ilink,*jlink;
};
struct VexBox
{
int data;
EBox *firstedge;
};
struct AMLGraph
{
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,edgenum;
};
typedef struct QNode
{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int visited[MAX_VERTEX_NUM];
int LocateVex(AMLGraph ,int );
void Initilized(AMLGraph &G)
{
int i,j,k,n,m;
int va,vb;
EBox *p;
printf("请输入无向图的顶点数,边数\n ");
cin>>n>>m;
G.vexnum=n;
G.edgenum=m;
printf("请输入顶点的值:\n");
for(i=0;i<n;i++)
{
cin>>G.adjmulist[i].data;
G.adjmulist[i].firstedge=NULL;
}
printf("请输入每条边的两个端点:\n");
for(k=0;k<m;k++)
{
printf("第%d边",k+1);
cin>>va>>vb;
i=LocateVex(G,va);
j=LocateVex(G,vb);
p=(EBox*)malloc(sizeof(EBox));
p->mark=0;
p->ivex=i;
p->ilink=G.adjmulist[i].firstedge;
G.adjmulist[i].firstedge=p;
p->jvex=j;
p->jlink=G.adjmulist[j].firstedge;
G.adjmulist[j].firstedge=p;
}
}
int LocateVex(AMLGraph G,int u)
{
int i;
for(i=0;i<G.vexnum;++i)
{
if(G.adjmulist[i].data==u)
return i;
}
return -1;
}
int FirstAdjVex(AMLGraph G,int v)
{
int i;
i=LocateVex(G,v);
if(i<0)
return -1;
if(G.adjmulist[i].firstedge)
if(G.adjmulist[i].firstedge->ivex==i)
return G.adjmulist[i].firstedge->jvex;
else if(G.adjmulist[i].firstedge->jvex==i)
return G.adjmulist[i].firstedge->ivex;
else
return -1;
}
int NextAdjVex(AMLGraph G,int v,int w)
{
int i,j;
EBox *p;
i=LocateVex(G,v);
j=LocateVex(G,w);
if(i<0||j<0)
return -1;
p=G.adjmulist[i].firstedge;
while(p)
if(p->ivex==i&&p->jvex!=j)
p=p->ilink;
else if(p->jvex==i&&p->ivex!=j)
p=p->jlink;
else
break;
if(p&&p->ivex==i&&p->jvex==j)
{
p=p->ilink;
if(p&&p->ivex==i)
return p->jvex;
else if(p&&p->jvex==i)
return p->ivex;
}
if(p&&p->ivex==j&&p->jvex==i)
{
p=p->jlink;
if(p&&p->ivex==i)
return p->jvex;
else if(p&&p->jvex==i)
return p->ivex;
}
return -1;
}
void DFS(AMLGraph G,int v)
{
int j;
EBox *p;
if(visited[v]==1)
return;
visited[v]=1;
printf("%d\n",v);
p=G.adjmulist[v].firstedge;
while(p)
{
if(p->ivex==v)
j=p->jvex;
else
j=p->ivex;
if(visited[j]==0)
printf("<%d,%d>\n",v,j);
DFS(G,j);
if(p->ivex==v)
p=p->ilink;
else p=p->jlink;
}
}
void DFS(AMLGraph ,int);
void DFSTraverse(AMLGraph G)
{
for(int v=0;v<G.vexnum;v++)
visited[v]=0;
for( v=0;v<=G.vexnum;v++)
if(visited[v]==0)
DFS(G,v);
}
void InitQueue(LinkQueue &Q)
{ // 构造一个空队列Q
if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))
exit(0);
Q.front->next=NULL;
}
void EnQueue(LinkQueue &Q,int e)
{ // 插入元素e为Q的新的队尾元素
QueuePtr p;
if(!(p=(QueuePtr)malloc(sizeof(QNode))))
exit(0);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
int DeQueue(LinkQueue &Q,int &e)
{
QueuePtr p;
if(Q.front==Q.rear)
return -1;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
}
int QueueEmpty(LinkQueue Q)
{
if(Q.front->next==NULL)
return 1;
else
return 0;
}
void BFSTraverse(AMLGraph G)
{
int u,w,v;
LinkQueue Q;
for( v=0;v<G.vexnum;v++)
visited[v]=0;
InitQueue(Q);
for(v=0;v<G.vexnum;v++)
if(visited[v]==0)
{
printf("%d\n",v);
visited[v]=1;
EnQueue(Q,v);
while(QueueEmpty(Q)==0)
{
DeQueue(Q,u);
for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))
if(visited[w]==0)
{
printf("<%d,%d>\n",u,w);
visited[w]=1;
printf("%d\n",w);
EnQueue(Q,w);
}
}
}
}
void main()
{
AMLGraph G;
int v1,v2;
Initilized(G);
printf("深度优先搜索的结果:\n");
DFSTraverse(G);
printf("广度优先搜索的结果:\n");
BFSTraverse(G);
}