资源描述：
《《数据结构图》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第7章图陈守孔孟佳娜陈卓1东普鲁士的七桥问题2七桥问题的数学模型ABDC3图的应用历史东普鲁士的七桥问题要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。1736年欧拉将陆地作顶点，将桥作边，从而将这个实际问题抽象成图的模型。“一笔划问题”：当两个顶点的度为偶数，其余顶点的度为奇数时，可以从一个偶数顶点出发，经过每条边一次，最后到达另一偶数顶点。“欧拉回路问题”：只有所有的顶点的度都是偶数，才能从一个顶点出发，经过每条边一次，最后回这个顶点。欧拉证明七桥问题无解。4清华大学2001设在4地（A，B，C，
2、D）之间架设有6座桥，如图所示：要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。（1）试就以上图形说明：此问题有解的条件是什么？（5分）（2）设图中的顶点数为n,试用C或PASCAL描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。（10分）5本章目录7.1图的定义和术语7.2图的存储结构7.2.1数组表示法7.2.2邻接表（*7.2.3十字链表*7.2.4邻接多重表）7.3图的遍历7.3.1深度优先搜索7.3.2广度优先搜索7.4图的连通性问题7.4.1图的连通分量和生成树7.4
3、.2最小生成树7.5有向无环图及其应用7.5.1拓扑排序*7.5.2关键路径7.6最短路径（*7.7算法设计举例）7.6.1从某个源点到其它各顶点的最短路径7.6.2每一对顶点之间的最短路径6主要内容知识点1．图的定义，概念、术语及基本操作。2．图的存储结构，特别是邻接矩阵和邻接表。3．图的深度优先遍历和宽度优先遍历。4．图的应用（连通分量，最小生成树，拓扑排序，关键路经，最短路经）。重点难点1．基本概念中，完全图、连通分量、生成树和邻接点是重点。2．建立图的各种存储结构的算法。3．图的遍历算法及其应用。4
4、．通过遍历求出连通分量的个数，深（宽）度优先生成树。5．最小生成树的生成过程。6．拓扑排序的求法。关键路经的求法。7．最短路径的手工模拟。7图的示例（有向图与无向图）V1V4V2V3V5V4V3V2V1结点之间的关系：多对多，任两个结点之间都可能有关系存在8图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对有向图——有向图G是由两个集合V(G)和E(G)组成V(G)是顶点的非空有限集，E(G)是有向
5、边（也称弧）的有限集合，弧是顶点的有序对，记为，vi,vj是顶点，vi为弧尾，vj为弧头无向图——无向图G是由两个集合V(G)和E(G)组成V(G)是顶点的非空有限集，E(G)是边的有限集合，边是顶点的无序对，记为（vi,vj）或（vj,vi)，并且（vi,vj)=(vj,vi)图的概念（1）9例G1图G1中：V(G1)={v1,v2,v3,v4}E(G1)={,,,}G2图G2中：V(G2)={v1,v2,v3,v4}E(G2)={(v
6、1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)}v1v2v3v4v1v2v3v4图的示例10有向完全图:n个顶点的有向图最大边数是n(n-1)无向完全图:n个顶点的无向图最大边数是n(n-1)/2邻接点:若(vi,vj)是一条无向边，则称vi和vj互为~关联:vi和vj互为邻接点，称边(vi,vj)关联于顶点vi和vj顶点的度无向图中，顶点的度为与每个顶点相连的边数,记为D(v)有向图中，顶点的度分成入度与出度，其中入度是以该顶点为头的弧的数目，记为ID(v)。出
7、度是以该顶点为尾的弧的数目,记为OD(v)。顶点的度为入度和出度的和，即D(v)=ID(v)+OD(v)。v1v3v4v2v1v2v3v4图的概念（2）11子图——如果图G(V,E)和图G’(V’,E’),满足：V’V，E’E则称G’为G的子图24513635621v1v3v4v2v1v3v2v3v4图的概念（3）121573246路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1,2,3,5,6,3,1简单回路：3，5，6，3路径——是顶点的序列V={Vp,Vi1,……Vin,V
8、q}，满足(Vp,Vi1),(Vi1,Vi2),…,(Vin,Vq)E(G),则称vp到vq存在路径.路径长度——沿路径边的数目或沿路径各边权值之和.回路——第一个顶点和最后一个顶点相同的路径叫回路简单路径——序列中顶点不重复出现的路径叫简单路径简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，
