for(v=0;v<G.vexnum;v++)
if(!visite[v])
DFS(G,v);
printf("\n");
}
typedef int QElemType; /* 队列类型 */
/* BFSTraverse()用 */
/* BFSTraverse()用 */
void BFSTraverse(AMLGraph G,int(*Visit)(VertexType))
{ /* 初始条件: 图G存在,Visit是顶点的应用函数。算法7.6 */
/* 操作结果: 从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数 */
/* Visit一次且仅一次。一旦Visit()失败,则操作失败。 */
/* 使用辅助队列Q和访问标志数组visite */
int v,u,w;
VertexType w1,u1;
LinkQueue Q;
for(v=0;v<G.vexnum;v++)
visite[v]=0; /* 置初值 */
InitQueue(&Q); /* 置空的辅助队列Q */
for(v=0;v<G.vexnum;v++)
if(!visite[v]) /* v尚未访问 */
{
visite[v]=1; /* 设置访问标志为TRUE(已访问) */
Visit(G.adjmulist[v].data);
EnQueue(&Q,v); /* v入队列 */
while(!QueueEmpty(Q)) /* 队列不空 */
{
DeQueue(&Q,&u); /* 队头元素出队并置为u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visite[w]) /* w为u的尚未访问的邻接顶点的序号 */
{
visite[w]=1;
Visit(G.adjmulist[w].data);
EnQueue(&Q,w);
}
}
}
printf("\n");
}
void MarkUnvizited(AMLGraph G)
{ /* 置边的访问标记为未被访问 */
int i;
EBox *p;
for(i=0;i<G.vexnum;i++)
{
p=G.adjmulist[i].firstedge;
while(p)
{
p->mark=unvisited;
if(p->ivex==i)
p=p->ilink;
else
p=p->jlink;
}
}
}
void Display(AMLGraph G)
{ /* 输出无向图的邻接多重表G */
int i;
EBox *p;
MarkUnvizited(G); /* 置边的访问标记为未被访问 */
printf("%d个顶点：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.adjmulist[i].data);
printf("\n%d条边:\n",G.edgenum);
for(i=0;i<G.vexnum;i++)
{
p=G.adjmulist[i].firstedge;
while(p)
if(p->ivex==i) /* 边的i端与该顶点有关 */
{
if(!p->mark) /* 只输出一次 */
{
printf("%s－%s ",G.adjmulist[i].data,G.adjmulist[p->jvex].data);
p->mark=visited;
if(p->info) /* 输出附带信息 */
printf("相关信息: %s ",p->info);
}
p=p->ilink;
}
else /* 边的j端与该顶点有关 */
{
if(!p->mark) /* 只输出一次 */
{
printf("%s－%s ",G.adjmulist[p->ivex].data,G.adjmulist[i].data);
p->mark=visited;
if(p->info) /* 输出附带信息 */
printf("相关信息: %s ",p->info);
}
p=p->jlink;
}
printf("\n");
}
}
/*主程序*/
visit(VertexType v)
{
printf("%s ",v);
return 1;
}
void main()
{
int k,n;
AMLGraph g;
VertexType v1,v2;
CreateGraph(&g);
Display(g);
printf("DFS:\n");/*深度优先搜索的结果*/
DFSTraverse(g,visit);
printf("BFS:\n");/*广度优先搜索的结果*/
BFSTraverse(g,visit);
DestroyGraph(&g);
}