邻接矩阵表示的图的基本操作的实现

发布时间:2021-09-28 17:11:14

邻接矩阵表示的图的基本操作的实现
//采用邻接矩阵完成无权无向及有向图的"建立、输出、深度遍历、广度遍 历"操作 #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR -1 typedef int Status; typedef int ElemType; //此例中设元素为单值元素,类型为整型 //最大顶点个数

#define MAX_VERTEX_NUM 20

typedef int ElemType;

//图顶点数据类型

typedef int QueueElemType;//队列结点数据类型 //链表结点类型定义 typedef struct Qnode { QueueElemType data; struct Qnode *next; }QNode; //队列类型定义: typedef struct Linkqueue { QNode *front,*rear; }LinkQueue;

//图的数据类型定义 typedef struct Mgraph { ElemType vector[MAX_VERTEX_NUM]; int int int //顶点向量

adj[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 vexnum; arcnum; //图中当前顶点数 //图中当前边数

} MGraph;

//队列初始化 Status InitLinkQueue(LinkQueue *Q) { QNode *p; p=(QNode*)malloc(sizeof(QNode));//开辟头结点空间 if(p!=NULL) { p->next=NULL; Q->front=Q->rear=p; return OK; } else return ERROR; }

//链式队列的入队操作,在已知队列的队尾插入一个元素 e,修改队尾指针 rear。 Status InsertLinkQueue(LinkQueue *Q,ElemType e) { QNode *p; p=(QNode*)malloc(sizeof(QNode)); if(p==NULL) return ERROR;//申请新结点空间失败,返回错误标志 else { p->data=e;//存入新结点数据 p->next=NULL; Q->rear->next=p;//新结点插入到队尾 Q->rear=p;//新插入结点成为新的队尾 return OK;

} }

//链式队列的出队操作,取第一个数据结点的数据后删除该结点 Status DeleteLinkQueue(LinkQueue *Q,ElemType *e) { QNode *p; if(Q->front==Q->rear)//可改为:if(Q->front->next==NULL) return ERROR;//队空 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; return OK; } }

//判断队列是否为空 Status IsEmptyLinkQueue(LinkQueue *Q) { if(Q->front==Q->rear) return OK; else return ERROR; }

//释放队列 void DestroyLinkQueue(LinkQueue *Q) { QNode *p,*q; p=Q->front;//指向链表第一个结点,即整个链表的第一个结点 while(p!=NULL) { q=p->next;//保存链表后半段首地址以防丢失 free(p); p=q; } }

/**************以下为图的操作************/

//顶点在顶点向量中的定位,找到返回 OK,否则返回 ERROR //G 为的数据结构,v 为待查顶点,n 用于返回找到的顶点下标 Status LocateVex(MGraph G,ElemType v,int *n) { int i; for(i=0;((i<G.vexnum)&&(G.vector[i]!=v));i++) ; *n=i; if(i<G.vexnum) return OK; else return ERROR; }

//建立无向图的邻接矩阵 void CreateGraph(MGraph *G) {

int i,j,k,sfyxt;//sfyxt:0-无向图 其它-有向图 ElemType v1,v2; printf("请输入图的顶点数及边数:"); scanf("%d%d",&(G->vexnum),&(G->arcnum)); fflush(stdin); printf("请输入%d 个顶点信息:\n",G->vexnum); for(i=0;i<G->vexnum;i++) //输入顶点向量 scanf("%d",&(G->vector[i])); printf("顶点向量如下:\n"); for(i=0;i<G->vexnum;i++) printf("%4d",G->vector[i]); printf("\n 无向图还是有向图,0-无向图 其它-有向图:"); scanf("%d",&sfyxt); for(i=0;i<G->vexnum;i++) for(j=0;j<G->vexnum;j++) G->adj[i][j]=0; printf("\n 请输入无权图的边(共%d 条)\n",G->arcnum); printf("格式为:vi vj,vi 及 vj 表示结点内容,注意有向图结点输入 的前后次序:\n"); for(k=0;k<G->arcnum;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]; } } //输入无权图的边 //邻接矩阵初始化 //输出顶点向量

//输出无向图的邻接矩阵 void PrintGraph(MGraph G) { int i,j; printf("图信息如下:\n"); printf("%4s"," "); for(i=0;i<G.vexnum;i++) printf("%4d",G.vector[i]); printf("\n"); for(i=0;i<G.vexnum;i++) { printf("%4d",G.vector[i]); for(j=0;j<G.vexnum;j++) printf("%4d",G.adj[i][j]); printf("\n"); } }

//查找顶点 v 的第一个邻接点,v 为当前顶点下标 int FirstAdjVex(MGraph G,int v) { int j,p=-1,found=1; for(j=0;((j<G.vexnum)&&(found==1));j++) if(G.adj[v][j]==1) { p=j; found=0; } return p; }

//查找顶点 v 的下一个邻接点,w 为当前邻接点下标

int NextAdjVex(MGraph G,int v,int w) { int j,p=-1,found=1; for(j=w+1;((j<G.vexnum)&&(found==1));j++) if(G.adj[v][j]==1) { p=j; found=0; } return p; }

//深度优先遍历 char visited[MAX_VERTEX_NUM];//访问标志数组 void Dfs(MGraph G,int v) { int w; 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); }

void DfsTraverse(MGraph G) { int v; for(v=0;v<G.vexnum;v++) visited[v]=0; for(v=0;v<G.vexnum;v++) if(visited[v]==0)

Dfs(G,v); }

//广度优先遍历 void BfsTraverse(MGraph G) { int v,u,w; LinkQueue Q; for(v=0;v<G.vexnum;v++) visited[v]=0; InitLinkQueue(&Q); for(v=0;v<G.vexnum;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); }

//主函数 void main() { int xz=1; MGraph G; 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) { case 1: CreateGraph(&G); break; case 2: PrintGraph(G); break; case 3: DfsTraverse(G); printf("\n"); break; case 4: BfsTraverse(G); printf("\n"); break; case 0: printf("再见!\n");

break; default: printf("输入错误!\n"); break; } } }


相关文档

  • 图的表示和操作(邻接矩阵)
  • 图的基本操作(邻接矩阵法)
  • 实验12 图的基本操作-邻接矩阵
  • c++实现图的邻接矩阵表示法
  • 邻接表表示的图的基本操作的实现
  • 图的基本操作(邻接矩阵)
  • 图的邻接矩阵实现
  • 邻接矩阵实现图的遍历
  • 猜你喜欢

  • 中国高血压防治指PPT课件
  • 如何做好农业生产工作 农业生产工作情况汇报
  • 世博园区综合管廊监控系统的设计
  • 牛津深圳版(广州沈阳通用)九年级英语上册同步复*Unit1第一单元测试(带答案)
  • 我与未来有个约定600字初中作文素材 我们的约定作文600字
  • 时代光华-如何正确认知时间管理-课后测试
  • 学校五四晚会主持词3篇
  • 圣女果什么时候播种最好
  • 电脑连接蓝牙总是断
  • 电力系统核相的定义
  • 湖北省黄冈市麻城市七年级英语下册 Unit 8 Is there a post office near here Section A(1a-1c)教学设计
  • 法国留学 马恩-拉瓦雷大学的入学条件
  • 感谢信英语小作文
  • 初一下外研版Module1unit1教案
  • 杭州依音服饰有限公司企业信息报告-天眼查
  • 最新精编高三英语教学期末工作总结精品模板
  • 言语行为理论的跨文化语用对比分析
  • 如何加强初中语文现代文的阅读教学
  • 水利工程水文地质问题论文
  • 某手机游戏项目商业计划书(PPT21页)
  • 哺乳期乳头附*痒怎么办【母婴健康常识】
  • 最新版《统计学原理》201007计算复*(2)2013-06-27-11-09-41
  • 防雷减灾工作行政执法思考
  • 南京爱与美信息科技有限公司(企业信用报告)- 天眼查
  • 开学随想作文400字
  • 海上集装箱运输及杂货班轮运输的基础知识及货运流程
  • 普宁市南径镇卫生院医疗设备采购项目
  • 禁毒征文_6
  • GUI功能自动化测试
  • 电视台暑期实*心得体会
  • 最新继电保护课后*题答案第二版-张保会-尹项根资料
  • 教海探航信息奥赛辅导与能力培养初探
  • 读笑猫日记有感-1000字六年级作文叙事
  • 染料标准工岗位竞聘演讲个人介绍自我推荐演讲完整动态PPT模板
  • 物业公司物业管理部经理助理职位说明书
  • 高新技术产业发展能力评价研究
  • 书师生户外活动策划范文
  • 2017年事业单位公共基础知识:民事诉讼法之回避制度、民法之民事责任的类型
  • 连锁经营推广策划书范例
  • 最新烟草专卖局(公司)党风廉政建设责任制实施办法-范文精品
  • 阜新蒙古族自治县永盛玉米种植专业合作社企业信用报告-天眼查
  • 佳木斯世纪文化传播有限公司企业信用报告-天眼查
  • 电脑版