- 1、本文档共227页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Ch_7 图(数据结构)培训课件方案研究.ppt
线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继。;七桥问题;网络路由问题;一笔画问题;第7章 图(Graph);要求;7.1 图的定义和术语;7.1 图的定义和术语;若v, w?VR 必有w, v?VR,
即VR是对称的,则以无序对(v,w)代替这两个有序对,表示v 和 w 之间的一条边。;名词和术语;假设图中有 n 个顶点,e 条边或弧,不考虑顶点到自身的边或弧。;假设图中有 n 个顶点,e 条边或弧,;1;A;A;顶点的出度OD(v): 以顶点v为尾的弧的数目,;设图G=(V,{VR})中的一个顶点序列
{ u=vi,0,vi,1, …, vi,m=w}中,(vi,j-1,vi,j)?VR 1≤j≤m,
则称从顶点u 到顶点w 之间存在一条路径。
路径上边的数目称作路径长度。;简单路径:序列中顶点不重复出现的路径。;若无向图G中任意两个顶点之间都有路径相通,则称此图为连通图;;A; 若任意两个顶点之间都存在一条有向路径,则称此有向图为强连通图。;一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边;一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧;例;例;连通图;图的抽象数据类型定义;结构的建立和销毁;CreatGraph(G, V, VR);
// 按V和VR的定义构造图;对顶点的访问操作;对邻接点的操作;插入或删除顶点;插入和删除弧;遍历;7.2 图的存储结构;Aij={;有向图的邻接矩阵为非对称矩阵;A;;讨论2 :有向图的邻接矩阵表示。; 容易实现图的操作,如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等。
n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。;typedef struct ArcCell { // 弧的定义
VRType adj;// VRType是顶点关系类型。对无权图,
//用1或0表示相邻否;对带权图,则为权值类型。
InfoType *info; // 该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM];;typedef struct { // 图的定义
VertexType vexs[MAX_VERTEX_NUM];
// 顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum, arcnum; // 图的当前顶点数和弧数
GraphKind kind; // 图的种类标志
} MGraph;;Status CreateUDN(MGraph G){
//采用数组(邻接矩阵)表示法,构造无向网G
Scanf(G.vexnum,G.arcnum,IncInfo);
//IncInfo为0则各弧不含其他信息
For(i=0;iG.vexnum;++i)scanf(G.vexs[i])
//构造顶点向量
For(i=0;iG.vexnum;++i)//初始化邻接矩阵
For(j=0;jG.vexnum;++j)
G.arcs[i][j]={INFINITY,NULL};//{adj,info};For(k=0;kG.arcnum;++k){//构造邻接矩阵
Scanf(v1,v2,w);//输入一条边依附的顶点及权值
i=LocateVex(G,v1);j=LocateVex(G,v2);
//确定v1和v2在G中位置
G.arcs[i][j].adj=w;//弧v1,v2的权值
If(IncInfo) Input(*G.arcs[i][j].info);
//若弧含有相关信息,则输入
G.arcs[j][i]=G.arcs[i][j];//置v1,v2的对称弧v2,v1
}Return OK;
}//CreateUDN;0 A 1 4
1 B 0 4 5
2 C 3 5
3 D 2 5
4 E 0 1
5 F 1 2 3;1 4;A;typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点
您可能关注的文档
- Chapter 2 蛋白质-3-蛋白质分离技术培训课件方案研究.ppt
- Chapter 3-1 矩阵的初等变换教学教材.ppt
- Chapter 3-热喷涂知识研讨.ppt
- chapter-one案例实例.ppt
- chapter02 全面预算与公司治理内部控制知识讲稿.ppt
- chapter1 牵引供电系统概述教材课程.ppt
- Chapter1-2绪论-基本概念培训课件方案研究.ppt
- chapter1-生物信息学简介案例实例.ppt
- Chapter3 高频功率放大器 RF Power Amplifier培训课件方案研究.ppt
- Chapter3-厦门大学-林子雨-大数据技术原理与应用-第三章-分布式文件系统HDFS知识讲稿.ppt
- 大学生职业规划大赛《新闻学专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《应用统计学专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《音乐学专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《中医学专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《信息管理与信息系统专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《汽车服务工程专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《水产养殖学专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《市场营销专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《音乐表演专业》生涯发展展示PPT.pptx
- 大学生职业规划大赛《音乐学专业》生涯发展展示PPT.pptx
文档评论(0)