版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业#include stdafx.h#include conio.h#include stdio.h#include stdlib.htypedef enum FALSE, TRUE BOOLEAN;#define OVERFLOW -1#define OK 1#define ERROR 0#define INFINITY INT_MAX /* 最大值 */ /* 根据图的权值类型,分别定义为最大整数或实数 */#define MAX_VERTEX_NUM 20 /* 最
2、大顶点数目 */typedef enum DG, DN, UDG,UDN GraphKind ; /* 有向图,有向网,无向图,无向网 */BOOLEAN VisitedMAX_VERTEX_NUM;BOOLEAN visitedMAX_VERTEX_NUM;#define VEX_NUM 20#define MAXSIZE 50typedef char Vextype;typedef int ElemType;typedef int Status; / 邻接矩阵结构定义typedef struct Vextype vexsVEX_NUM; int adjVEX_NUMVEX_NUM; /*邻
3、接矩阵*/ int n,e; /*顶点数和边数*/ Mgraph; / 邻接表结构定义typedef struct node /*边结点*/int adjvex; /*邻接点域*/struct node * nextarc; /*指向下一个边结点的指针域*/ EdgeNode; typedef struct vnode /顶点结构,2个域,结点信息和第一个邻接点Vextype vertex; EdgeNode *firstedge; VertexNode; typedef struct /图结构VertexNode adjlistMAXSIZE;int n,e; ALGraph; /int F
4、irstAdjVex(ALGraph G,int v) /在图G中寻找第v个顶点的第一个邻接顶点 if(!G.adjlistv.firstedge) return -1; else return(G.adjlistv.firstedge-adjvex); int NextAdjVex(ALGraph G,int v,int w) /在图G中寻找第v个顶点的相对于w的下一个邻接顶点 EdgeNode *p;int vi; p=G.adjlistv.firstedge; if(!p) return -1; while(p-adjvex!=w) p=p-nextarc; /在顶点v的弧链中找到顶点w
5、 p=p-nextarc;if(!p) return -1; /若已是最后一个顶点,返回-1else vi=p-adjvex;return vi; /返回下一个邻接顶点的序号 /void CreateMGraph(Mgraph *G) int i,j,k; / char ch; printf(请输入顶点数和边数:n); scanf(%d,%d,&(G-n),&(G-e); /*输入*/ printf(请输入顶点信息:n); for (i=0;in;i+) scanf(%s,&(G-vexsi); for (i=0;in;i+) for (j=0;jn;j+) G-adjij=0; /*初始化邻
6、接矩阵*/ printf(输入每条边对应的两个顶点的序号:n); for (k=0;ke;k+) scanf(%d,%d,&i,&j); /*输入e条边*/G-adjij=1; G-adjji=1; /*对称加入,无向图的邻接矩阵存储建立*/ /*CreateMGraph*/ void CreateALGraph(ALGraph *G) /*建立无向图的邻接表存储*/int i,j,k;char vi;EdgeNode *s; printf(请输入顶点数和边数:n);scanf(%d,%d,&(G-n),&(G-e); printf(请输入顶点信息Vin例如a,每输入一个顶点后回车:n); f
7、or (i=0;in;i+) scanf(%s,&vi); G-adjlisti.vertex=vi;G-adjlisti.firstedge=NULL; printf(顶点:);for (i=0;in;i+) printf(%c(%d)-,G-adjlisti.vertex,i+1); printf(n请输入边的信息(vi,vj)n例如:1,2:n);for (k=0;ke;k+) /*建立边表*/scanf(%d,%d,&i,&j); /在头结点和边结点之间插入新的边结点 s=(EdgeNode*)malloc(sizeof(EdgeNode); s-adjvex=j-1; s-nexta
8、rc=G-adjlisti-1.firstedge;G-adjlisti-1.firstedge=s;s=(EdgeNode*)malloc(sizeof(EdgeNode); s-adjvex=i-1; s-nextarc=G-adjlistj-1.firstedge;G-adjlistj-1.firstedge=s; /输出邻接表./*CreateALGraph*/void DFS(ALGraph *G, int v) EdgeNode *p ; Visitedv=TRUE ; printf(%c-,G-adjlistv.vertex); /* 置访问标志,访问顶点v */ p=G-adj
9、listv.firstedge; /* 链表的第一个结点 */ while (p!=NULL) if(!Visitedp-adjvex) DFS(G, p-adjvex);/* 从v的未访问过的邻接顶点出发深度优先搜索 */ p=p-nextarc ; void DFS_traverse (ALGraph *G) int v ; EdgeNode *p ; printf(深度度优先搜索输出结点信息:);for (v=0; vn; v+) Visitedv=FALSE ; /* 访问标志初始化 */ p=G-adjlistv.firstedge ; for (v=0; vn; v+) if (!
10、Visitedv) DFS(G,v);/队列 /typedef struct Node ElemType data; / 元素数据 struct Node *next; / 链式队列中结点元素的指针 QNode, *QueuePtr; typedef struct QueuePtr front; / 队列头指针 QueuePtr rear; / 队列尾指针 LinkQueue; Status InitQueue(LinkQueue &Q) /构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if(Q.front = NULL
11、) exit(OVERFLOW); /存储失败 Q.front -next = NULL; return OK; Status DestoryQueue(LinkQueue &Q) /销毁队列Q while(Q.front)Q.rear = Q.front-next; /利用尾指针移动保存队头指针free(Q.front); /依次释放头结点 Q.front = Q.rear; return OK;Status QueueEmpty(LinkQueue Q) /assert(Q.front != NULL & Q.rear != NULL); if(Q.front = Q.rear) retu
12、rn TRUE; else return FALSE; Status EnQueue(LinkQueue &Q, ElemType e) /插入元素e为Q新的队尾元素 QueuePtr 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, Elem
13、Type *e) /若队列不空,则删除Q的队头元素,用e返回值,并返回OK。否则返回ERROR if(Q.front = Q.rear) return ERROR; QueuePtr p = Q.front -next; *e = p -data; Q.front -next= p -next; if(Q.rear = p) Q.rear = Q.front; /只有一个元素,恢复到空队列,只有各头结点 free(p); return OK; /int Visit(int v,ALGraph G)/printf(%d,v); printf(%c-,G.adjlistv.vertex); ret
14、urn OK;void BFSTraverse(ALGraph G, Status (*Visit)(int v,ALGraph G)/ 连通图 G 广度优先搜索 LinkQueue Q;ElemType u;/ EdgeNode *p;int v;int w;printf(广度优先搜索输出结点信息:);for(v=0;vG.n;+v) visitedv=FALSE;/ 初始化访问标志 InitQueue(Q); /置空的辅助队列 for(v=0;v=0; w=NextAdjVex(G,u,w) if(!visitedw) /w为u尚未访问的邻接顶点 visitedw=TRUE; Visit(w,G); EnQueue(Q,w);/访问的
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- GB/T 44398-2024冷冻烃类流体动态测量用于液化天然气(LNG)和其他冷冻烃类流体的流量计校准和安装的要求和指南
- GB/T 44336-2024素肉制品术语与分类
- GB/T 25915.17-2024洁净室及相关受控环境第17部分:粒子沉积速率应用
- 《2024年 城市街道景观设计文化研究》范文
- 《2024年 基于文化生态学的城市空间理论研究-以天津、青岛、大连为例》范文
- DB32-T 4825-2024 普通国省道数字化建设与应用技术规程
- 出国留学行业国际教育资源对接服务平台设计方案
- 农产品品牌建设与电商平台运营方案
- 餐厅防火安全管理制度
- 《探究决定导线电阻的因素》参考课件
- 网红直播基地孵化建设方案电商直播基地建设
- 手机领用申请单
- 电脑验收报告
- 剖面图、柱状图、地质图绘制方法
- 二年级上册科学课件-第2单元 人工与自然 复习课件-冀教版(共12张PPT)
- 【七年级上】书法教案
- 医护人员的压力管理共69张课件
- 西游记 品味经典名著导读PPT
- 金坛区苏科版四年级心理健康教育第1课《我的兴趣爱好》课件(定稿)
- 2022年环保标记试题库(含答案)
- 2023版本科软件工程实验教学大纲
评论
0/150
提交评论