邻接矩阵表示的图的基本操作的实现.docx
《邻接矩阵表示的图的基本操作的实现.docx》由会员分享，可在线阅读，更多相关《邻接矩阵表示的图的基本操作的实现.docx（11页珍藏版）》请在冰点文库上搜索。
邻接矩阵表示的图的基本操作的实现
邻接矩阵表示的图的基本操作的实现
//采用邻接矩阵完成无权无向及有向图的"建立、输出、深度遍历、广度遍历"操作
#include
#include
#defineOK1
#defineERROR-1
typedefintStatus;
typedefintElemType;//此例中设元素为单值元素，类型为整型
#defineMAX_VERTEX_NUM20//最大顶点个数
typedefintElemType;//图顶点数据类型
typedefintQueueElemType;//队列结点数据类型
//链表结点类型定义
typedefstructQnode
{
QueueElemTypedata;
structQnode*next;
}QNode;
//队列类型定义：
typedefstructLinkqueue
{
QNode*front,*rear;
}LinkQueue;
//图的数据类型定义
typedefstructMgraph
{
ElemTypevector[MAX_VERTEX_NUM];//顶点向量
intadj[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵
intvexnum;//图中当前顶点数
intarcnum;//图中当前边数
}MGraph;
//队列初始化
StatusInitLinkQueue（LinkQueue*Q）
{
QNode*p;
p=（QNode*）malloc（sizeof（QNode））;//开辟头结点空间
if（p!
=NULL）
{
p->next=NULL;
Q->front=Q->rear=p;
returnOK;
}
else
returnERROR;
}
//链式队列的入队操作，在已知队列的队尾插入一个元素e，修改队尾指针rear。
StatusInsertLinkQueue（LinkQueue*Q,ElemTypee）
{
QNode*p;
p=（QNode*）malloc（sizeof（QNode））;
if（p==NULL）
returnERROR;//申请新结点空间失败，返回错误标志
else
{
p->data=e;//存入新结点数据
p->next=NULL;
Q->rear->next=p;//新结点插入到队尾
Q->rear=p;//新插入结点成为新的队尾
returnOK;
}
}
//链式队列的出队操作，取第一个数据结点的数据后删除该结点
StatusDeleteLinkQueue（LinkQueue*Q,ElemType*e）
{
QNode*p;
if（Q->front==Q->rear）//可改为：
if（Q->front->next==NULL）
returnERROR;//队空
else
{
p=Q->front->next;//取队首结点
*e=p->data;
Q->front->next=p->next;//修改队首指针
if（p==Q->rear）//条件成立说明只有一个数据结点
Q->rear=Q->front;//当队列只有一个数据结点时应防止丢失队尾指针
free（p）;
Q->rear->next=NULL;
returnOK;
}
}
//判断队列是否为空
StatusIsEmptyLinkQueue（LinkQueue*Q）
{
if（Q->front==Q->rear）
returnOK;
else
returnERROR;
}
//释放队列
voidDestroyLinkQueue（LinkQueue*Q）
{
QNode*p,*q;
p=Q->front;//指向链表第一个结点，即整个链表的第一个结点
while（p!
=NULL）
{
q=p->next;//保存链表后半段首地址以防丢失
free（p）;
p=q;
}
}
/**************以下为图的操作************/
//顶点在顶点向量中的定位，找到返回OK，否则返回ERROR
//G为的数据结构，v为待查顶点，n用于返回找到的顶点下标
StatusLocateVex（MGraphG,ElemTypev,int*n）
{
inti;
for（i=0;（（i=v））;i++）
;
*n=i;
if（ireturnOK;
else
returnERROR;
}
//建立无向图的邻接矩阵
voidCreateGraph（MGraph*G）
{
inti,j,k,sfyxt;//sfyxt:
0-无向图其它-有向图
ElemTypev1,v2;
printf（"请输入图的顶点数及边数：
"）;
scanf（"%d%d",&（G->vexnum）,&（G->arcnum））;
fflush（stdin）;
printf（"请输入%d个顶点信息：
\n",G->vexnum）;
for（i=0;ivexnum;i++）//输入顶点向量
scanf（"%d",&（G->vector[i]））;
printf（"顶点向量如下：
\n"）;//输出顶点向量
for（i=0;ivexnum;i++）
printf（"%4d",G->vector[i]）;
printf（"\n无向图还是有向图，0-无向图其它-有向图：
"）;
scanf（"%d",&sfyxt）;
for（i=0;ivexnum;i++）//邻接矩阵初始化
for（j=0;jvexnum;j++）
G->adj[i][j]=0;
printf（"\n请输入无权图的边（共%d条）\n",G->arcnum）;
printf（"格式为：
vivj，vi及vj表示结点内容，注意有向图结点输入的前后次序：
\n"）;
for（k=0;karcnum;k++）//输入无权图的边
{
fflush（stdin）;
printf（"No.%2d/%d：
",k+1,G->arcnum）;
scanf（"%d%d",&v1,&v2）;
LocateVex（*G,v1,&i）;
LocateVex（*G,v2,&j）;
G->adj[i][j]=1;
if（sfyxt==0）//无向图则同时产生两条边的信息
G->adj[j][i]=G->adj[i][j];
}
}
//输出无向图的邻接矩阵
voidPrintGraph（MGraphG）
{
inti,j;
printf（"图信息如下：
\n"）;
printf（"%4s",""）;
for（i=0;iprintf（"%4d",G.vector[i]）;
printf（"\n"）;
for（i=0;i{
printf（"%4d",G.vector[i]）;
for（j=0;jprintf（"%4d",G.adj[i][j]）;
printf（"\n"）;
}
}
//查找顶点v的第一个邻接点，v为当前顶点下标
intFirstAdjVex（MGraphG,intv）
{
intj,p=-1,found=1;
for（j=0;（（jif（G.adj[v][j]==1）
{
p=j;
found=0;
}
returnp;
}
//查找顶点v的下一个邻接点，w为当前邻接点下标
intNextAdjVex（MGraphG,intv,intw）
{
intj,p=-1,found=1;
for（j=w+1;（（jif（G.adj[v][j]==1）
{
p=j;
found=0;
}
returnp;
}
//深度优先遍历
charvisited[MAX_VERTEX_NUM];//访问标志数组
voidDfs（MGraphG,intv）
{
intw;
visited[v]=1;//置当前结点为已访问状态
printf（"%4d",G.vector[v]）;//访问当前结点
//依次深度遍历当前结点未被遍历的邻接结点，采用递归方式实现
for（w=FirstAdjVex（G,v）;w>=0;w=NextAdjVex（G,v,w））
if（visited[w]==0）
Dfs（G,w）;
}
voidDfsTraverse（MGraphG）
{
intv;
for（v=0;vvisited[v]=0;
for（v=0;vif（visited[v]==0）
Dfs（G,v）;
}
//广度优先遍历
voidBfsTraverse（MGraphG）
{
intv,u,w;
LinkQueueQ;
for（v=0;vvisited[v]=0;
InitLinkQueue（&Q）;
for（v=0;vif（visited[v]==0）
{
visited[v]=1;
printf（"%4d",G.vector[v]）;
InsertLinkQueue（&Q,v）;
while（IsEmptyLinkQueue（&Q）!
=OK）
{
DeleteLinkQueue（&Q,&u）;
for（w=FirstAdjVex（G,u）;w>=0;w=NextAdjVex（G,u,w））
if（visited[w]==0）
{
visited[w]=1;
printf（"%4d",G.vector[w]）;
InsertLinkQueue（&Q,w）;
}
}
}
DestroyLinkQueue（&Q）;
}
//主函数
voidmain（）
{
intxz=1;
MGraphG;
while（xz!
=0）
{
printf（"1－输入图信息\n"）;
printf（"2－输出图信息\n"）;
printf（"3－图的深度优先遍历\n"）;
printf（"4－图的广度优先遍历\n"）;
printf（"0－退出\n请选择：
"）;
fflush（stdin）;
scanf（"%d",&xz）;
switch（xz）
{
case1:
CreateGraph（&G）;
break;
case2:
PrintGraph（G）;
break;
case3:
DfsTraverse（G）;
printf（"\n"）;
break;
case4:
BfsTraverse（G）;
printf（"\n"）;
break;
case0:
printf（"再见！
\n"）;
break;
default:
printf（"输入错误！
\n"）;
break;
}
}
}
升级会员 