[指南]采纳邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操纵
/* 采用邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操作 */
#include "stdio.h"
#include "string.h"
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define OK 1
#define ERROR 0
typedef int Status;
#define INFINITY INT_MAX /*最大值“无穷”*/
#define MAX_VERTEX_NUM 20 /*最大顶点个数*/typedef int Boolean;
typedef char VertexType[20]; typedef int VRType;
/**************以下为队列的操作************/
/****队列的类型定义****/
typedef int QElemType;typedef struct QNode
{QElemType data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
} LinkQueue;
/****初始化队列****/
Status InitQueue(LinkQueue *Q) { (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if (!(*Q).front) exit(OVERFLOW);
(*Q).front->next=NULL;
return OK; }
/****判断队列是否为空****/ Status QueueEmpty (LinkQueue Q) { if (Q.front==Q.rear)
return TRUE;
else
return FALSE; }
/****入队列****/
Status EnQueue(LinkQueue *Q, QElemType e) { QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if (!p) exit(OVERFLOW);
p->data=e; p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
return OK; }
/****出队列****/
Status DeQueue(LinkQueue *Q, QElemType *e) { QueuePtr p;
if ((*Q).front==(*Q).rear) return ERROR;
>next; p=(*Q).front-
*e=p->data;
(*Q).front->next=p->next;
if ((*Q).rear==p) (*Q).rear=(*Q).front;
free(p);
return OK; }
/**************以下为图的操作************/
/*图的类型定义*/
typedef struct ArcCell
{ VRType adj; /*图中有1/0表示是否有边,网中表示边上的权值*/
/* InfoType *info; 与边相关的信息*/
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{ VertexType vexs[MAX_VERTEX_NUM]; /*顶点向量*/
AdjMatrix arcs; /*邻接矩阵*/
int vexnum,arcnum; /*图中当前顶点数和边数*/
} MGraph;
/*建立无向图的邻接矩阵*/
void CreateGraph(MGraph *G)
{ int i,j,k; VertexType v1,v2;
printf("\nInput MG vexnum,arcnum:");
scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);
printf("Input %d vexs:",(*G).vexnum);
for(i=0;i<(*G).vexnum;i++) /*输入顶点向量*/
{ scanf("%s",(*G).vexs[i]); }
printf("vexs list\n");
for(i=0;ivexnum;i++) /*输出顶点向量*/
puts(G->vexs[i]);
for(i=0;i<(*G).vexnum;i++) /*邻接矩阵初始化*/
for(j=0;j<(*G).vexnum;j++)
(*G).arcs[i][j].adj=0;
printf("\nInput %d arcs(vi vj):\n",(*G).arcnum);
for(k=0;k<(*G).arcnum;k++) /*输入无权图的边*/
{ scanf("%s%s",v1,v2);
i=LocateVex(*G,v1); j=LocateVex(*G,v2);
(*G).arcs[i][j].adj=1;
(*G).arcs[j][i]=(*G).arcs[i][j];
}
}
/* 顶点在顶点向量中的定位*/
int LocateVex(MGraph G,VertexType v) { int i;
for(i=0;i=0; w=NextAdjVex(G,v,w))
if(!visited[w]) Dfs(G,w); }
void DfsTraverse(MGraph G) { int v;
for (v=0; v=0; w=NextAdjVex(G,u,w))
if (!visited[w])
{ visited[w]=TRUE;
printf("%s",G.vexs[w]);
EnQueue(&Q,w);
}
}
}
}
/*主函数*/
main()
{ int w;
MGraph G;
CreateGraph(&G);
PrintGraph(G);
printf("\nDfs:"); DfsTraverse(G); /* 深度遍历 */
nBfs:"); BfsTraverse(G); /* 广度遍历 */ printf("\
}
本文档为【[指南]采纳邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操纵】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。