c数据结构h6a.ppt

《c数据结构h6a.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实例图的定义和术语图的存储结构下一章第六章图图的遍历生成树拓扑排序关键路径最短路径6.0实例多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED1.顶点数任意，顶点之间关系任意2.如何存储3.数据操作：顶点染色（遍历与找邻接点）田径赛的时间安排问题设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）.设计比赛日程表，使得在尽可能短的时间内完成比赛（1）设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米ABCDEF（2）用顶点代表比赛项目,不

2、能同时进行比赛的项目间连上边（3）某选手比赛的项目必定有边相连（不能同时比赛）AEBFDC姓名项目1项目2项目3丁一ABE马二CD张三CEF李四DFA王五BFABECDF比赛时间比赛项目1A，C2B，D3E4F只需安排四个单位时间进行比赛公园导游问题1.顶点数任意，顶点之间关系任意2.如何存储3.数据操作：任意两点之间最短路径入口6.1图的定义和术语图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对有向图——有向

3、图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为，v为弧尾，w为弧头无向图——无向图G是由两个集合V(G)和E(G)组成的其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)例245136G1图G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例157324G2

4、6图G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}有向完备图——n个顶点的有向图最大边数是n(n-1)无向完备图——n个顶点的无向图最大边数是n(n-1)/2权——与图的边或弧相关的数叫~网——带权的图叫~子图——如果图G(V,E)和图G′(V′,E′),满足：V′VE′E则称G‘为G的子图顶点的度无向图中，顶点的度为与每个顶点相连的边数有向图中，顶点的度分成入度与出度入度：以该顶点为头的弧的数目出度：以该顶点为尾的

5、弧的数目路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E或E,(1

6、V,ViVj,从Vi到Vj和从Vj到Vi都存在路径，则称G是~例213213有向完备图无向完备图356例245136图与子图例245136G1顶点2入度：1出度：3顶点4入度：1出度：0例157324G26顶点5的度：3顶点2的度：4例157324G26例245136G1路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5，6回路：1，2，3，5，6，3，1简单回路：3，5，6，3路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，

7、2，3，1连通图例245136强连通图356例非连通图连通分量例2451366.2图的存储结构多重链表例G12413例15324G2V1V2V4V3V1V2V4V5V3^^^^^^^邻接矩阵——表示顶点间相联关系的矩阵定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵例G12413例15324G201100000000110000101010101010111010001100特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+

8、1)/2有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和例G12413例15324G2例145237531864