if（strcmp（u,G.adjmulist[i].data）==0）
returni;
return-1;
}
//采用邻接多重表存储结构,构造无向图G
intCreateGraph（AMLGraph*G）
{
inti,j,k,l,IncInfo;
chars[MAX_INFO];
VertexTypeva,vb;
EBox*p;
printf（"请输入无向图G的顶点数,边数,边是否含其它信息（是:
1，否:
0）:
"）;
scanf（"%d,%d,%d",&（*G）.vexnum,&（*G）.edgenum,&IncInfo）;
printf（"请输入%d个顶点的值（<%d个字符）:
\n",（*G）.vexnum,MAX_NAME）;
for（i=0;i<（*G）.vexnum;++i）//构造顶点向量
{
scanf（"%s",（*G）.adjmulist[i].data）;
（*G）.adjmulist[i].firstedge=NULL;
}
printf（"请顺序输入每条边的两个端点（以空格作为间隔）:
\n"）;
for（k=0;k<（*G）.edgenum;++k）//构造表结点链表
{
scanf（"%s%s%*c",va,vb）;//%*c吃掉回车符
i=LocateVex（*G,va）;//一端
j=LocateVex（*G,vb）;//另一端
p=（EBox*）malloc（sizeof（EBox））;
p->mark=unvisited;//设初值
p->ivex=i;
p->jvex=j;
p->info=NULL;
p->ilink=（*G）.adjmulist[i].firstedge;//插在表头
（*G）.adjmulist[i].firstedge=p;
p->jlink=（*G）.adjmulist[j].firstedge;//插在表头
（*G）.adjmulist[j].firstedge=p;
if（IncInfo）//边有相关信息
{
printf（"请输入该弧的相关信息（<%d个字符）：
",MAX_INFO）;
gets（s）;
l=strlen（s）;
if（l）
{
p->info=（char*）malloc（（l+1）*sizeof（char））;
strcpy（p->info,s）;
}
}
}
return1;
}
//返回v的值
VertexType*GetVex（AMLGraphG,intv）
{
if（v>=G.vexnum||v<0）
exit（0）;
return&G.adjmulist[v].data;
}
//对v赋新值value
intPutVex（AMLGraph*G,VertexTypev,VertexTypevalue）
{
inti;
i=LocateVex（*G,v）;
if（i<0）//v不是G的顶点
return0;
strcpy（（*G）.adjmulist[i].data,value）;
return1;
}
//返回v的第一个邻接顶点的序号。
若顶点在G中没有邻接顶点,则返回-1
intFirstAdjVex（AMLGraphG,VertexTypev）
{
inti;
i=LocateVex（G,v）;
if（i<0）
return-1;
if（G.adjmulist[i].firstedge）//v有邻接顶点
if（G.adjmulist[i].firstedge->ivex==i）
returnG.adjmulist[i].firstedge->jvex;
else
returnG.adjmulist[i].firstedge->ivex;
else
return-1;
}
//返回v的（相对于w的）下一个邻接顶点的序号。
若w是v的最后一个邻接点,则返回-1
intNextAdjVex（AMLGraphG,VertexTypev,VertexTypew）
{
inti,j;
EBox*p;
i=LocateVex（G,v）;//i是顶点v的序号
j=LocateVex（G,w）;//j是顶点w的序号
if（i<0||j<0）//v或w不是G的顶点
return-1;
p=G.adjmulist[i].firstedge;//p指向顶点v的第1条边
while（p）
if（p->ivex==i&&p->jvex!
=j）//不是邻接顶点w（情况1）
p=p->ilink;//找下一个邻接顶点
elseif（p->jvex==i&&p->ivex!
=j）//不是邻接顶点w（情况2）
p=p->jlink;//找下一个邻接顶点
else//是邻接顶点w
break;
if（p&&p->ivex==i&&p->jvex==j）//找到邻接顶点w（情况1）
{
p=p->ilink;
if（p&&p->ivex==i）
returnp->jvex;
elseif（p&&p->jvex==i）
returnp->ivex;
}
if（p&&p->ivex==j&&p->jvex==i）//找到邻接顶点w（情况2）
{
p=p->jlink;
if（p&&p->ivex==i）
returnp->jvex;
elseif（p&&p->jvex==i）
returnp->ivex;
}
return-1;
}
//在G中增添新顶点v（不增添与顶点相关的弧,留待InsertArc（）去做）
intInsertVex（AMLGraph*G,VertexTypev）
{
if（（*G）.vexnum==MAX_VERTEX_NUM）//结点已满，不能插入
return0;
if（LocateVex（*G,v）>=0）//结点已存在,不能插入
return0;
strcpy（（*G）.adjmulist[（*G）.vexnum].data,v）;
（*G）.adjmulist[（*G）.vexnum].firstedge=NULL;
（*G）.vexnum++;
return1;
}
//在G中删除弧
intDeleteArc（AMLGraph*G,VertexTypev,VertexTypew）
{
inti,j;
EBox*p,*q;
i=LocateVex（*G,v）;
j=LocateVex（*G,w）;
if（i<0||j<0||i==j）
return0;//图中没有该点或弧
//以下使指向待删除边的第1个指针绕过这条边
p=（*G）.adjmulist[i].firstedge;//p指向顶点v的第1条边
if（p&&p->jvex==j）//第1条边即为待删除边（情况1）
（*G）.adjmulist[i].firstedge=p->ilink;
elseif（p&&p->ivex==j）//第1条边即为待删除边（情况2）
（*G）.adjmulist[i].firstedge=p->jlink;
else//第1条边不是待删除边
{
while（p）//向后查找弧
{
if（p->ivex==i&&p->jvex!
=j）//不是待删除边
{
q=p;
p=p->ilink;//找下一个邻接顶点
}
elseif（p->jvex==i&&p->ivex!
=j）//不是待删除边
{
q=p;
p=p->jlink;//找下一个邻接顶点
}
else//是邻接顶点w
break;
}
if（!
p）//没找到该边
return0;
if（p->ivex==i&&p->jvex==j）//找到弧（情况1）
if（q->ivex==i）
q->ilink=p->ilink;
else
q->jlink=p->ilink;
elseif（p->ivex==j&&p->jvex==i）//找到弧（情况2）
if（q->ivex==i）
q->ilink=p->jlink;
else
q->jlink=p->jlink;
}
//以下由另一顶点起找待删除边且删除之
p=（*G）.adjmulist[j].firstedge;//p指向顶点w的第1条边
if（p->jvex==i）//第1条边即为待删除边（情况1）
{
（*G）.adjmulist[j].firstedge=p->ilink;
if（p->info）//有相关信息
free（p->info）;
free（p）;
}
elseif（p->ivex==i）//第1条边即为待删除边（情况2）
{
（*G）.adjmulist[j].firstedge=p->jlink;
if（p->info）//有相关信息
free（p->info）;
free（p）;
}
else//第1条边不是待删除边
{
while（p）//向后查找弧
if（p->ivex==j&&p->jvex!
=i）//不是待删除边
{
q=p;
p=p->ilink;//找下一个邻接顶点
}
elseif（p->jvex==j&&p->ivex!
=i）//不是待删除边
{
q=p;
p=p->jlink;//找下一个邻接顶点
}
else//是邻接顶点v
break;
if（p->ivex==i&&p->jvex==j）//找到弧（情况1）
{
if（q->ivex==j）
q->ilink=p->jlink;
else
q->jlink=p->jlink;
if（p->info）//有相关信息
free（p->info）;
free（p）;
}
elseif（p->ivex==j&&p->jvex==i）//找到弧（情况2）
{
if（q->ivex==j）
q->ilink=p->ilink;
else
q->jlink=p->ilink;
if（p->info）//有相关信息
free（p->info）;
free（p）;
}
}
（*G）.edgenum--;
return1;
}
//删除G中顶点v及其相关的边
intDeleteVex（AMLGraph*G,VertexTypev）
{
inti,j;
VertexTypew;
EBox*p;
i=LocateVex（*G,v）;//i为待删除顶点的序号
if（i<0）
return0;
for（j=0;j<（*G）.vexnum;j++）//删除与顶点v相连的边（如果有的话）
{
if（j==i）
continue;
strcpy（w,*GetVex（*G,j））;//w是第j个顶点的值
DeleteArc（G,v,w）;
}
for（j=i+1;j<（*G）.vexnum;j++）//排在顶点v后面的顶点的序号减1
（*G）.adjmulist[j-1]=（*G）.adjmulist[j];
（*G）.vexnum--;//顶点数减1
for（j=i;j<（*G）.vexnum;j++）//修改顶点的序号
{
p=（*G）.adjmulist[j].firstedge;
if（p）
{
if（p->ivex==j+1）
{
p->ivex--;
p=p->ilink;
}
else
{
p->jvex--;
p=p->jlink;
}
}
}
return1;
}
voidDestroyGraph（AMLGraph*G）
{
inti;
for（i=（*G）.vexnum-1;i>=0;i--）
DeleteVex（G,（*G）.adjmulist[i].data）;
}
//在G中增添弧
intInsertArc（AMLGraph*G,VertexTypev,VertexTypew）
{
inti,j,l,IncInfo;
chars[MAX_INFO];
EBox*p;
i=LocateVex（*G,v）;//一端
j=LocateVex（*G,w）;//另一端
if（i<0||j<0）
return0;
p=（EBox*）malloc（sizeof（EBox））;
p->mark=unvisited;
p->ivex=i;
p->jvex=j;
p->info=NULL;
p->ilink=（*G）.adjmulist[i].firstedge;//插在表头
（*G）.adjmulist[i].firstedge=p;
p->jlink=（*G）.adjmulist[j].firstedge;//插在表头
（*G）.adjmulist[j].firstedge=p;
printf（"该边是否有相关信息（1:
有0:
无）:
"）;
scanf（"%d%*c",&IncInfo）;//吃掉回车符
if（IncInfo）//边有相关信息
{
printf（"请输入该边的相关信息（<%d个字符）：
",MAX_INFO）;
gets（s）;
l=strlen（s）;
if（l）
{
p->info=（char*）malloc（（l+1）*sizeof（char））;
strcpy（p->info,s）;
}
}
（*G）.edgenum++;
return1;
}
intvisite[MAX_VERTEX_NUM];//访问标志数组（全局量）
int（*VisitFunc）（VertexTypev）;
voidDFS（AMLGraphG,intv）
{
intj;
EBox*p;
VisitFunc（G.adjmulist[v].data）;
visite[v]=1;
p=G.adjmulist[v].firstedge;
while（p）
{
j=p->ivex==v?
p->jvex:
p->ivex;
if（!
visite[j]）
DFS（G,j）;
p=p->ivex==v?
p->ilink:
p->jlink;
}
}
//算法7.4
//从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit
voidDFSTraverse（AMLGraphG,int（*visit）（VertexType））
{
intv;
VisitFunc=visit;
for（v=0;vvisite[v]=0;
for（v=0;vif（!
visite[v]）
DFS（G,v）;
printf（"\n"）;
}
//构造一个空队列Q
intInitQueue（LinkQueue*Q）
{
（*Q）.front=（*Q）.rear=（QueuePtr）malloc（sizeof（QNode））;//动态分配一个空间
if（!
（*Q）.front）
exit（0）;
（*Q）.front->next=NULL;//队头指针指向空，无数据域，这样构成了一个空队列
return1;
}
//若Q为空队列,则返回1,否则返回0
intQueueEmpty（LinkQueueQ）
{
if（Q.front==Q.rear）
return1;
else
return0;
}
//插入元素e为Q的新的队尾元素
intEnQueue（LinkQueue*Q,QElemTypee）
{
QueuePtrp=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）//存储分配失败
exit（0）;
//生成一个以为e为数据域的队列元素
p->data=e;
p->next=NULL;
//将该新队列元素接在队尾的后面
（*Q）.rear->next=p;
（*Q）.rear=p;
return1;
}
//若队列不空,删除Q的队头元素,用e返回其值,并返回1,否则返回0
intDeQueue（LinkQueue*Q,QElemType*e）
{
QueuePtrp;
if（（*Q）.front==（*Q）.rear）
return0;
p=（*Q）.front->next;//队头元素
*e=p->data;
（*Q）.front->next=p->next;
if（（*Q）.rear==p）
（*Q）.rear=（*Q）.front;
free（p）;
return1;
}
//从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数
//Visit一次且仅一次。
使用辅助队列Q和访问标志数组visite
voidBFSTraverse（AMLGraphG,int（*Visit）（VertexType））
{
intv,u,w;
VertexTypew1,u1;
LinkQueueQ;
for（v=0;vvisite[v]=0;//置初值
InitQueue（&Q）;//置空的辅助队列Q
for（v=0;vif（!
visite[v]）//v尚未访问
{
visite[v]=1;//设置访问标志为1（已访问）
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"）;
}
//置边的访问标记为未被访问
voidMarkUnvizited（AMLGraphG）
{
inti
升级会员 