printf（"%d",tu.iedges[i][j]）;
printf（"\n"）;
}
printf（"\n\n深度优先遍历的结果为：
\n\n"）;
DFSTraverseAL（&tu）;printf（"\n"）;
}
三、编写实现以邻接表方式存储的无向图的深度优先遍历算法，并上机调试运行
#include
#include
#defineMaxVertexNum100//最大顶点数，应由用户定义
typedefcharVertexType;//顶点类型应由用户定义
typedefstructnode{//边表结点
intadjvex;//邻接点域
structnode*next;//链域
//若要表示边上的权，则应增加一个数据域
}EdgeNode;
typedefstructvnode{//顶点表结点
VertexTypevertex;//顶点域
EdgeNode*firstedge;//边表头指针
}VertexNode;
typedefVertexNodeAdjList[MaxVertexNum];
//AdjList是邻接表类型
typedefstruct{
AdjListadjlist;//邻接表
intn,e;//图中当前顶点数和边数
}ALGraph;
//对于简单的应用，无须定义此类型，可直接使用AdjList类型
typedefenum{FALSE,TRUE}Boolean;//FALSE为0，TRUE为1
Booleanvisited[MaxVertexNum];//访问标志向量是全局量
voidDFS（ALGraph*G,inti）;
voidmain（）
{
voidCreateALGraph（ALGraph*G）;
voidPrintALGraph（ALGraph*G）;
voidDFSTraverse（ALGraph*G）;
ALGraphG;
CreateALGraph（&G）;
PrintALGraph（&G）;
printf（"深度优先搜索结果：
"）;
DFSTraverse（&G）;
printf（"\n"）;
}
voidCreateALGraph（ALGraph*G）
{//建立无向图的邻接表表示
inti,j,k;
EdgeNode*s;
printf（"请输出顶点数和边数：
"）;
scanf（"%d%d",&G->n,&G->e）;//读入顶点数和边数
printf（"请输出顶点信息：
"）;
for（i=0;in;i++）{//建立顶点表
while（（G->adjlist[i].vertex=getchar（））=='\n'）;//读入顶点信息
G->adjlist[i].firstedge=NULL;//边表置为空表
}
for（k=0;ke;k++）{//建立边表
printf（"\n请输出第%d边的起点、终点：
",k+1）;
scanf（"%d%d",&i,&j）;//读入边（vi,vj）的顶点对序号
s=（EdgeNode*）malloc（sizeof（EdgeNode））;//生成边表结点
s->adjvex=j;//邻接点序号为j
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;//将新结点*s插入顶点vi的边表头部
s=（EdgeNode*）malloc（sizeof（EdgeNode））;
s->adjvex=i;//邻接点序号为i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s;//将新结点*s插入顶点vj的边表头部
}
}
//打印邻接表：
voidPrintALGraph（ALGraph*G）
{
inti;
EdgeNode*p;
for（i=0;in;i++）
{
printf（"%d%c:
\t",i,G->adjlist[i].vertex）;
p=G->adjlist[i].firstedge;
while（p）
{
printf（"%d\t",p->adjvex）;
p=p->next;
}
printf（"\n"）;
}
}
voidDFSTraverse（ALGraph*G）
{//深度优先遍历以邻接表表示的图G
inti;
for（i=0;in;i++）
visited[i]=FALSE;//标志向量初始化
for（i=0;in;i++）
if（!
visited[i]）//vi未访问过
DFS（G,i）;//以vi为源点开始DFS搜索
}
voidDFS（ALGraph*G,inti）
{//以vi为出发点对邻接表表示的图G进行深度优先搜索
EdgeNode*p;
printf（"%c",G->adjlist[i].vertex）;//访问顶点vi
visited[i]=TRUE;//标记vi已访问
p=G->adjlist[i].firstedge;//取vi边表的头指针
while（p）
{//依次搜索的vi邻接点vj，这里j=p->adjvex
if（!
visited[p->adjvex]）//若vj尚未被访问
DFS（G,p->adjvex）;//则以vj为出发点向纵深搜索
p=p->next;//找vi的下一邻接点
}
}
四、设计算法对邻接表表示的无向网进行广度优先遍历。
#include
#include
typedefintDataType;//将队列中元素的数据类型改为Person
//循环队列的类型定义
#defineQueueSize100//应根据具体情况定义该值
typedefstruct
{intfront;//头指针，队非空时指向队头元素
intrear;//尾指针，队非空时指向队尾元素的下一位置
intcount;//计数器，记录队中元素总数
DataTypedata[QueueSize];
}CirQueue;
#defineMaxVertexNum100//最大顶点数，应由用户定义
typedefcharVertexType;//顶点类型应由用户定义
typedefstructnode{//边表结点
intadjvex;//邻接点域
structnode*next;//链域
//若要表示边上的权，则应增加一个数据域
}EdgeNode;
typedefstructvnode{//顶点表结点
VertexTypevertex;//顶点域
EdgeNode*firstedge;//边表头指针
}VertexNode;
typedefVertexNodeAdjList[MaxVertexNum];
//AdjList是邻接表类型
typedefstruct{
AdjListadjlist;//邻接表
intn,e;//图中当前顶点数和边数
}ALGraph;
//对于简单的应用，无须定义此类型，可直接使用AdjList类型
typedefenum{FALSE,TRUE}Boolean;//FALSE为0，TRUE为1
Booleanvisited[MaxVertexNum];//访问标志向量是全局量
voidmain（）
{
voidInitQueue（CirQueue*Q）;
intQueueEmpty（CirQueue*Q）;
intQueueFull（CirQueue*Q）;
voidEnQueue（CirQueue*Q,DataTypex）;
DataTypeDeQueue（CirQueue*Q）;
DataTypeQueueFront（CirQueue*Q）;
voidCreateALGraph（ALGraph*G）;
voidPrintALGraph（ALGraph*G）;
voidBFS（ALGraph*G,intk）;
ALGraphG;
CreateALGraph（&G）;
PrintALGraph（&G）;
printf（"广度优先搜索结果：
"）;
BFS（&G,0）;
printf（"\n"）;
}
voidCreateALGraph（ALGraph*G）
{//建立无向图的邻接表表示
inti,j,k;
EdgeNode*s;
printf（"请输出顶点数和边数：
"）;
scanf（"%d%d",&G->n,&G->e）;//读入顶点数和边数
printf（"请输出顶点信息：
"）;
for（i=0;in;i++）{//建立顶点表
while（（G->adjlist[i].vertex=getchar（））=='\n'）;//读入顶点信息
G->adjlist[i].firstedge=NULL;//边表置为空表
}
for（k=0;ke;k++）{//建立边表
printf（"\n请输出第%d边的起点、终点：
",k+1）;
scanf（"%d%d",&i,&j）;//读入边（vi,vj）的顶点对序号
s=（EdgeNode*）malloc（sizeof（EdgeNode））;//生成边表结点
s->adjvex=j;//邻接点序号为j
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;//将新结点*s插入顶点vi的边表头部
s=（EdgeNode*）malloc（sizeof（EdgeNode））;
s->adjvex=i;//邻接点序号为i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s;//将新结点*s插入顶点vj的边表头部
}
}
//打印邻接表：
voidPrintALGraph（ALGraph*G）
{
inti;
EdgeNode*p;
for（i=0;in;i++）
{
printf（"%d%c:
\t",i,G->adjlist[i].vertex）;
p=G->adjlist[i].firstedge;
while（p）
{
printf（"%d\t",p->adjvex）;
p=p->next;
}
printf（"\n"）;
}
}
voidInitQueue（CirQueue*Q）
{（*Q）.front=（*Q）.rear=0;
（*Q）.count=0;//计数器置0
}
intQueueEmpty（CirQueue*Q）
{
return（*Q）.count==0;//队列无元素为空
}
intQueueFull（CirQueue*Q）
{
return（*Q）.count==QueueSize;
//队中元素个数等于QueueSize时队满
}
voidEnQueue（CirQueue*Q,DataTypex）
{
if（QueueFull（Q））
{printf（"Queueoverflow"）;
exit（0）;//队满上溢
}
（*Q）.count++;//队列元素个数加1
（*Q）.data[（*Q）.rear]=x;//新元素插入队尾
（*Q）.rear=（（*Q）.rear+1）%QueueSize;//循环意义下将尾指针加1
}
DataTypeDeQueue（CirQueue*Q）
{
DataTypetemp;
if（QueueEmpty（Q））
{printf（"Queueunderflow"）;
exit（0）;//队空下溢
}
temp=（*Q）.data[（*Q）.front];
（*Q）.count--;//队列元素个数减1
（*Q）.front=（（*Q）.front+1）%QueueSize;//循环意义下的头指针加1
returntemp;
}
DataTypeQueueFront（CirQueue*Q）
{
if（QueueEmpty（Q））
{printf（"Queueisempty"）;
exit（0）;
}
return（*Q）.data[（*Q）.front];
}
voidBFS（ALGraph*G,intk）
{//以vk为源点对用邻接表表示的图G进行广度优先搜索
inti;
CirQueueQ;//须将队列定义中DataType改为int
EdgeNode*p;
InitQueue（&Q）;//队列初始化
printf（"%c",G->adjlist[k].vertex）;//访问源点vk
visited[k]=TRUE;
EnQueue（&Q,k）;//vk已访问，将其入队。
注意，实际上是将其序号入队
while（!
QueueEmpty（&Q））{//队非空则执行
i=DeQueue（&Q）;//相当于vi出队
p=G->adjlist[i].firstedge;//取vi的边表头指针
while（p）{//依次搜索vi的邻接点vj（令p->adjvex=j）
if（!
visited[p->adjvex]）{//若vj未访问过
printf（"%c",G->adjlist[p->adjvex].vertex）;//访问vj
visited[p->adjvex]=TRUE;
EnQueue（&Q,p->adjvex）;//访问过的vj入队
}
p=p->next;//找vi的下一邻接点
}
}
}
升级会员 