chap08 v3数据结构-图VIP免费

下载本文档

阅读 149
下载 10
格式 pdf
大小 889.48 KB
约155页
2024-11-11 发布于河南
收藏
评论
点赞(0)
海报
举报

1/155页

2/155页

3/155页

在线预览已结束，请下载后查看完整版，加入VIP享文档下载特权

/155

文本预览下载提示常见问题

第8章图8.1图的基本概念8.2图的存储结构8.3图的遍历8.4最小生成树8.5一点到其他点最短路径问题8.6拓扑排序8.1图的基本概念�图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x|x∈某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,y∈V}或E={|x,y∈V&&Path(x,y)}�有向图与无向图是有序的。边就称为弧，x为弧尾，y为弧头。(x,y)是无序的。�完全图00001111222265433�邻接顶点�子图设有两个图G＝(V,E)和G’＝(V’,E’)。若V’⊆V且E’⊆E,则称图G’是图G的子图。0123子图0130123023�权�带权图也叫做网络。�稠密图和稀疏图eclassGraph{//图的类定义protected:intmaxVertices;//图中最大顶点数intnumEdges;//当前边数intnumVertices;//当前顶点数intgetVertexPos(Tvertex);//给出顶点vertex在图中位置public:Graph(intsz=DefaultVertices);//构造函数～Graph();//析构函数boolGraphEmpty()const//判图空否{returnnumEdges==0;}intNumberOfVertices(){returnnumVertices;}//返回当前顶点数intNumberOfEdges(){returnnumEdges;}//返回当前边数virtualTgetValue(inti);//取顶点i的值virtualEgetWeight(intv1,intv2);//取边上权值virtualintgetFirstNeighbor(intv);//取顶点v的第一个邻接顶点virtualintgetNextNeighbor(intv,intw);//取邻接顶点w的下一邻接顶点virtualboolinsertVertex(constTvertex);//插入一个顶点vertexvirtualboolinsertEdge(intv1,intv2,Ecost);//插入边(v1,v2),权为costvirtualboolremoveVertex(intv);//删去顶点v和所有与相关联边virtualboolremoveEdge(intv1,intv2);//在图中删去边(v1,v2)};8.2图的存储表示一、邻接矩阵（相邻矩阵）�图(n个顶点)的邻接矩阵是一个二维数组edge[n][n]，�定义：⎩⎨⎧∈∈=,),(,,]][[.否则或者如果0><1AEjiEjijiEdge0123⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=0101101001011010A.edge012⎥⎥⎦⎤⎢⎢⎣⎡=000101010A.edge�邻接矩阵的特征：�无向图的邻接矩阵是对称的;�有向图的邻接矩阵可能是不对称的。�在有向图中,统计第i行1的个数可得顶点i的出度，统计第j行1的个数可得顶点j的入度。�在无向图中,统计第i行(列)1的个数可得顶点i的度。网络(带权图)的邻接矩阵⎪⎩⎪⎨⎧==∉>∉<≠∞∈>∈<≠=jiji,ji,jiji,ji,jijiji若或且若或且若,)(,)(),,(]][[0EEEEWA.edge863129542031⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡∞∞∞∞=068053290410A.edge邻接矩阵存储图的类定义templateclassGraphmtx:publicGraph{friendistream&operator>>(istream&in,Graphmtx&G);//输入friendostream&operator<<(ostream&out,Graphmtx&G);//输出private:T*VerticesList;//顶点表E**Edge;//邻接矩阵intgetVertexPos(Tvertex){//给出顶点vertex在图中的位置for(inti=0;i

1、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
3、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。

碎片内容

chap08 v3数据结构-图

1图的基本概念8

2图的存储结构8

3图的遍历8

4最小生成树8

5一点到其他点最短路径问题8

6拓扑排序8

1图的基本概念�图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x|x∈某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,y∈V}或E={|x,y∈V&&Path(x,y)}�有向图与无向图是有序的

边就称为弧，x为弧尾，y为弧头

(x,y)是无序的

�完全图00001111222265433�邻接顶点�子图设有两个图G＝(V,E)和G’＝(V’,E’)

若V’⊆V且E’⊆E,则称图G’是图G的子图

0123子图0130123023�权�带权图也叫做网络

�稠密图和稀疏图e∉∈>(istream&in,Graphmtx&G);//输入friendostream&operator

您可能关注的文档

海纳百川 + 关注: 实名认证
内容提供者

热爱教学事业，对互联网知识分享很感兴趣

收藏店铺进入空间

chap08 v3数据结构-图VIP免费

chap08 v3数据结构-图

您可能关注的文档

相关文档

热门下载

相关标签