图的定义和基本术语 71 图的定义和基本术语

1、第7章图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.2最小生成树7.5有无定向用7.5.1拓扑分析排名7.5.2关键路径7.6最短路径7.6.1从某个源到其各顶点的最短路径7.6.2各顶点之间的最短路径，格拉夫(Graph )比线性表和树结构要复杂。 图中的任何数据都可能在两个元素之间相关。 第七章图，G1=(V1，A1) V1=v1，v2，v3，v4 A1=，G2=(V2，E2) V2=v1，v2，v3

2、，v4，v5 E2=(v1，v2)，(v1，v4)，(v2，v3)，(v5，v5)，(v3，v4)，(v4) 7.1图的定义和基础术语，顶点弧的尾弧头，顶点边，7.1图的定义和基础术语(续)，完全图： n个顶点有n(n-1)/2边的无向图： n个顶点有n(n-1 )条弧的有向图稀疏图：有少边的图(如边数e nlogn ) 密集图：非稀疏图权：关于边和弧的数量网络：带权图，2、7、4子格拉夫： G=(V，e )和G1=(V1， e1 )如果v1属于v，e1属于e，则G1为g的子格拉夫，7.1图的定义和基础术语(续2 )， 邻接点：用无向图边相连的2个顶点成为相互邻接点顶点的程度：与作为无向图的顶

3、点相连的邻接点的数入度：朝向图的顶点的弧的数出度：有从图的顶点出来的弧的数的7.1图的定义和基础术语(接下来3 )、路径： 2个顶点间的顶点系列、该系列的各顶点及其前驱是邻接点， 各顶点及其后续也是邻接点环(环):第一顶点和最后顶点相同的路径单纯路径：顶点不重复的路径连通： 2个顶点之间有路径连通图：任意2个顶点之间有路径连通成分：无向图中的极大连通子图。 强连通图：任意两个顶点之间有双向路径强连通成分：有有向图中的极大强连通子图。 连通图的生成树：极小连通子图。 虽然不是唯一的，但n个顶点的生成树只有n-1边。 森林的生成：图7.2的记忆结构7.2.1序列表示，# defineinfinit

4、int _ max # definemax _ vertex _ num关2.0字typedefenumdg，DN，AG，AN GraphKind； 类型基础架构销售线索类型adj； 信息类型*信息； ArcCell、adjmatrixmax _ vertex _ nummax _ vertex _ numtypedefstructvextypevexsmartx _ vertex _ num； adj矩阵arc； 数字，数字； 图形关键字； m图形； 数组表示法(邻接矩阵)、无向图、有向图、网络适用容易求出各顶点的度。 例如，关于有向图G1和无向图G2的邻接矩阵，n2的存储容量无向图的邻接矩

5、阵总是对称的压缩存储、网络及其邻接矩阵、7.2.2邻接表-链存储结构、# definemax _ vertex _ num 2.0 typedefstructarcnodeintadjvex 结构空间*下一个空间； 信息类型*信息； 锕系； 类型结构添加列表验证； 数字，数字； int键； ALGraph； 类型结构节点最佳类型数据； arcnode *初始化； 游戏名称：最大列表： 邻接表的链存储结构的图像，G1的邻接表，G2的邻接表，G1的逆邻接表，邻接表：容易求出，难以求出，容易求出，7.3图的老虎吧，图的老虎吧：从有图的顶点开始的所有顶点两种扫描图的路径：深度优先搜索和广度优先搜索对无向图和有向图两者都应用深度优先搜索，类似于树的先根扫描广度优先搜索对类似于树的分层扫描，7.3.1深度优先搜索，V1，扫描顺序：非连通的格拉夫重复上述过程，使得各顶点被网站数据库： V1，V2，堆栈，V4，V8，V5，深度优先搜索算法，