邻接矩阵表示的图的基本操作的实现.docx
- 文档编号:8755212
- 上传时间:2023-05-14
- 格式:DOCX
- 页数:11
- 大小:16.53KB
邻接矩阵表示的图的基本操作的实现.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(i returnOK; 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;i scanf("%d",&(G->vector[i])); printf("顶点向量如下: \n");//输出顶点向量 for(i=0;i printf("%4d",G->vector[i]); printf("\n无向图还是有向图,0-无向图其它-有向图: "); scanf("%d",&sfyxt); for(i=0;i for(j=0;j G->adj[i][j]=0; printf("\n请输入无权图的边(共%d条)\n",G->arcnum); printf("格式为: vivj,vi及vj表示结点内容,注意有向图结点输入的前后次序: \n"); for(k=0;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;i printf("%4d",G.vector[i]); printf("\n"); for(i=0;i { printf("%4d",G.vector[i]); for(j=0;j printf("%4d",G.adj[i][j]); printf("\n"); } } //查找顶点v的第一个邻接点,v为当前顶点下标 intFirstAdjVex(MGraphG,intv) { intj,p=-1,found=1; for(j=0;((j if(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;((j if(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;v visited[v]=0; for(v=0;v if(visited[v]==0) Dfs(G,v); } //广度优先遍历 voidBfsTraverse(MGraphG) { intv,u,w; LinkQueueQ; for(v=0;v visited[v]=0; InitLinkQueue(&Q); for(v=0;v if(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; } } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 邻接矩阵 表示 基本 操作 实现
![提示](https://static.bingdoc.com/images/bang_tan.gif)