我的图的遍历程序(邻接多重表结构),求高手指教。
#define max_vertex_num 30#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define OK 1
#define ERROR 0
typedef int status;
/*定义图的邻接多重表结构*/
typedef struct ebox
{
int ivex,jvex;//该边依附的两个顶点位置
struct ebox *ilink,*jlink;//分别指向依附这两个顶点的下一条边
}ebox;
/*顶点*/
typedef struct vexbox
{
int data;
ebox *firstedge;//指向第一条依附该顶点的边
}vexbox;
/*图*/
typedef struct
{ vexbox vexes[max_vertex_num];
int vexnum,edgenum;//无向图的当前顶点数和边数
}amlgraph;
/* 采用邻接多重表存储结构,构造无向图G */
void creategraph(amlgraph &G)
{ int i,j,k;
ebox *p;
printf("Input the number of vertex and edge(eg:10 10):\n");
scanf("%d%d",&G.vexnum,&G.edgenum);
for(k=1;k<=G.vexnum;++k)
G.vexes[k].data=k;//vexes[0]不用
for(k=1;k<=G.edgenum;++k)
{
printf("Input an edge(eg:1 2):\n");
scanf("%d%d",&i,&j);
p=(ebox*)malloc(sizeof(ebox));
p->ivex=i;
p->jvex=j;
p->ilink=G.vexes[i].firstedge; /* 插在表头 */
G.vexes[i].firstedge=p;
p->jlink=G.vexes[j].firstedge; /* 插在表头 */
G.vexes[j].firstedge=p;
}
}
/*寻找V的第一个邻接点W*/
int firstadjvex(amlgraph G,int v)
{
if(G.vexes[v].firstedge->ivex==v)
return G.vexes[v].firstedge->jvex;
else
return G.vexes[v].firstedge->ivex;
}
/*返回V的下一个邻接点(相对于W)*/
int nextadjvex(amlgraph G,int v,int w)
{ ebox *p;
if(v<0||w<0)
return 0;
p=G.vexes[v].firstedge;
if(p->ivex==v&&p->jvex==w)
{ p=p->ilink;
if(p&&p->ivex==v)
return p->jvex;
else if(p&&p->jvex==v)
return p->ivex;
}
if(p && p->ivex==w && p->jvex==v)
{
p=p->jlink;
if(p && p->ivex==v)
return p->jvex;
else
if(p && p->jvex==v)
return p->ivex;
}
}
/*全局变量：访问标志数组*/
int visitedvexes[max_vertex_num+1];
/*访问顶点*/
void visitvex(amlgraph G,int v)
{
printf("%2d ",G.vexes[v].data);
}
/*从第V个顶点出发递归地深度优先遍历图*/
void dfs(amlgraph G,int v)
{
int w;
visitedvexes[v]=1;
visitvex(G,v);
for(w=firstadjvex(G,v);w>=0;w=nextadjvex(G,w,v))
if(!visitedvexes[w])
dfs(G,w);
}
void dfstraverse(amlgraph G,int v)
{
int i;
for(i=1;i<=G.vexnum;i++)
visitedvexes[i]=0;
dfs(G,v);
}
/*队列的链式存储结构*/
typedef struct qnode
{
int data;
struct qnode *next;
}qnode,*queueptr;
typedef struct
{ queueptr front;
queueptr rear;/*队头、队尾指针*/
}linkqueue;
/*构造空队列*/
status initqueue(linkqueue &q)
{
q.front=q.rear=(queueptr)malloc(sizeof(qnode));
if(!q.front)
exit(0);
q.front->next=NULL;
return OK;
}
/*q为空返回TRUE，否则返回FALSE*/
status queueempty(linkqueue q)
{
if(q.front==q.rear)
return OK;
else
return ERROR;
}
/*插入元素e为q的新队尾元素*/
status enqueue(linkqueue &q,int e)
{
queueptr p=(queueptr)malloc(sizeof(qnode));
if(!p)/*存储分配失败*/
exit(0);
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
return OK;
}
/*若队列不空，删除q的队头元素，用e返回其值*/
status dequeue(linkqueue &q)
{ int e;
queueptr p;
if(q.front==q.rear)
return ERROR;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
free(p);
return e;
}
/* 销毁队列Q(无论空否均可) */
status DestroyQueue(linkqueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
/*广度优先遍历*/
void bfstraverse(amlgraph G,int v)
{ int i,u,w;
linkqueue q;
for(i=1;i<=G.vexnum;i++)
visitedvexes[i]=0;
initqueue(q);//置空的队列
for(i=1;i<=G.vexnum;++i)
if(!visitedvexes[(i-1+v)%G.vexnum])
{
visitedvexes[(i-1+v)%G.vexnum]=1;
visitvex(G,(i-1+v)%G.vexnum);
enqueue(q,(i-1+v)%G.vexnum);//i入队列
while(!queueempty(q))
{
u=dequeue(q);//队头元素出队并置为u
for(w=firstadjvex(G,u);w>0;w=nextadjvex(G,u,w))
if(!visitedvexes[w])//w为u的尚未访问的邻接顶点
{
visitedvexes[w]=1;
visitvex(G,w);
enqueue(q,w);
}
}
}
}
void main()
{
int v,choice;
amlgraph G;
printf(" \t\t\t1--Create a graph\n \t\t\t2--Broad first\n \t\t\t3--Depth first\n \t\t\t4--Exit\n");
scanf("%d",&choice);
while(choice!=6)
{ switch(choice)
{case 1: creategraph(G);break;
case 2: printf("Input the first vertex to start:\n");
scanf("%d",&v);
dfstraverse(G,v);
break;
case 3: printf("Input the first vertex to start:\n");
scanf("%d",&v);
bfstraverse(G,v);
printf("\n");
break;
case 4: break;
}
scanf("%d",&choice);
}
}
[[italic] 本帖最后由 我想自爆 于 2007-12-22 18:19 编辑 [/italic]]
有问题吧～
至少DFS那一部分有问题，疑是＂nextadjvex＂函数有误，我验证过了。页:
[1]