资源描述：
《数据结构chapter9图图的基本概念与抽象数据类型定义,图的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、上堂课要点回顾树的应用等价问题等价关系、等价类的定义并查集ADT并查集实现数组表示法链表表示法及改进森林表示法及改进第十三次课阅读：朱战立，第209-223页习题：作业12数据结构课程内容Chapter9图9.1图的定义及ADT9.2-3存储结构和实现9.4图的遍历深度优先搜索广度优先搜索应用：9.7拓扑排序9.5最小生成树prim算法kruskul算法9.6最短路径dijkstra算法floyd算法9.8关键路径图的应用领域电路网络分析交通运输管理线路的铺设印刷电路板与集成电路的布线工作的分配工程进度的安排课程表的制订关系数据库的设计9.1图的定义及抽象数据类型9.1
2、.1图(graph)的基本概念定义图G由两个集合V(G)和E(G)所组成，记作G=(V,E)。其中，V(G)是图中顶点vertex(即图的数据元素)的有限集合，E(G)是图中边edge(即两个顶点之间的关系)的有限集合。分类(1)有向图(directedgraph)：每条边是顶点的有序偶对有向图中的边也称为弧。用尖括号表示顶点的有序对，如，vi称为弧尾，vj称为弧头，并称它们互为邻接点(adjacent)。例：132G1V(G1)={V1,V2,V3},E(G1)={,,}(2)无向图(undirectedgrap
3、h)：每条边是顶点的无序偶对。用圆括号表示顶点的无序对，如（Vi,Vj），其中Vi和Vj为此边的起点和终点，并称它们互为邻接点(adjacent)。例：3124G24217536G3V(G2)={V1,V2,V3,V4}E(G2)={(V1,V2),(V1,V3),(V1,V4),(V2,V3),(V2,V4),(V3,V4)}树图无向完全图，有向完全图设n为图的顶点数，e为边或弧的数目，假设不考虑顶点到其自身的边或弧。具有n个顶点、n(n-1)条边的有向图，称为有向完全图(directedcompletegraph)。具有n个顶点、条边的无向图，称为无向完全图(und
4、irectedcompletegraph)。当一个图接近完全图时，则称它为稠密图(densegraph)，相反地，当一个图中含有较少的边或弧时，则称它为稀疏图(sparsegraph)。网若图的边或弧上附带有数据信息,这些附带的数据信息称为称为权。这种带权的图(weightedgraph)称作网。子图假设有两个图G和G’，且满足条件：V(G’)V(G)，E(G’)E(G)，则称G’是G的子图。例：G1的一些子图：1132132132G1G1的一些子图G2的一些子图：312412431213124G2G2的子图度、入度和出度(1)度(无向图中)顶点vi的度(total
5、degree)：是和vi相关联的边的数目，记作TD(vi)。(2)入度、出度、度(有向图中)顶点vi的入度(indegree)：是以顶点vi为头(终端点)的弧的数目，记作ID(vi)。顶点vi的出度(outdegree)：是以顶点vi为尾(初始点)的弧的数目，记作OD(vi)。顶点vi的度(totaldegree)：入度和出度之和。即TD(vi)=ID(vi)+OD(vi)路径、回路(1)路径(path)在无向图G中，从顶点vp到顶点vq的一条路径是顶点的序列(vp,vi1,vi2,…,vin,vq)，且(vp,vi1),(vi1,vi2),…,(vin,vq)都是E(
6、G)中的边。路径上边的数目称为该路径的长度(length)。对于有向图，其路径也是有向的，其顶点序列为，且,,…,都是E(G)中的弧。路径上弧的数目称为该路径的长度。(2)回路(cycle,环)第一个顶点和最后一个顶点相同的路径称为回路或环。简单路径(simplepath)：序列中各顶点不重复出现的路径。简单回路：第一个顶点和最后一个顶点相同的简单路径称为简单回路(simplecycle)。例：图G2中，(v1,v2,v4,v3)是一条简单路径；(v1,v2,v4,v3,v1)是
7、一条简单回路；(v1,v2,v4,v3,v2,v1)是一条回路。3124G2连通图、强连通图和生成树(1)在无向图G中，若V(G)中的每一对不同的顶点vi和vj都是连通的，则称G为连通图(connectedgraph)。在无向图G中，最大的连通子图称为G的连通分量(connectcompoent)。例：3124G2的连通分量：312423154G4的连通分量：231(1)54(2)(2)在有向图G中，若对于V(G)中每一对不同顶点vi和vj之间，都存在从vi到vj以及从vj到vi的路径，则称G为强连通图。有向图中最大的强连通子图称为它的强
