数据结构(严蔚敏)课件第7章教程文件.ppt

  1. 1、本文档共113页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第七章 图 ;【课前思考】;【学习目标】;【重点和难点】;【学习指南】;7.1 图的定义与术语; 图是由一个顶点集 V 和一个弧集 R构成的数据结构。 Graph = (V , VR ) 其中,VR={v,w| v,w∈V 且 P(v,w)} v,w表示从 v 到 w 的一条弧,并称 v 为弧头,w 为弧尾。 谓词 P(v,w) 定义了弧 v,w的意义或信息。; 由于“弧”是有方向的,因此称由顶点集和弧集构成的图为有向图。;名词和术语;A;假设图中有 n 个顶点,e 条边,则; 假若顶点v 和顶点w 之间存在一条边, 则称顶点v 和w 互为邻接点,;顶点的出度: 以顶点v为弧尾的弧的数目;;设图G=(V,{VR})中的一个顶点序列 { u=vi,0,vi,1, …, vi,m=w}中,(vi,j-1,vi,j)?VR 1≤j≤m, 则称从顶点u 到顶点w 之间存在一条路径。 路径上边(或弧)的数目称作路径长度。;若图G中任意两个顶点之间都有路径相通,则称此图为连通图;; 若任意两个顶点之间都存在一条有向路径,则称此有向图为强连通图。; 假设一个连通图有 n 个顶点和 e 条边,其中 n-1 条边和 n 个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成树。;结构的建立和销毁;CreatGraph(G, V, VR): // 按定义(V, VR) 构造图;对顶点的访问操作;对邻接点的操作;插入或删除顶点;插入和删除弧;遍 历;7.2 图的存储表示;Aij={;有向图的邻接矩阵为非对称矩阵;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;;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; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info; // 该弧相关信息的指针 } ArcNode;;typedef struct VNode { VertexType data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧 } VNode, AdjList[MAX_VERTEX_NUM];;typedef struct { AdjList vertices; int vexnum, arcnum; int kind; // 图的种类标志 } ALGraph;;三、有向图的十字链表存储表示 ;顶点的结点结构;typedef struct { VexNode xlist[MAX_VERTEX_NUM]; // 顶点结点(表头向量) int vexnum, arcnum; //有向图的当前顶

文档评论(0)

youngyu0329 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档