第七章7.1图的概念图的二元组定义：E图的基本术语图的基本术语1、端点和邻接点2、顶点的度、入度、出度完全图、稠密图、稀疏图稀疏图子图路径和回路路径和回路路径和回路连通和连通分量（无向图）强连通和强连通分量权(weight)和网(network)7.2图的存储结构7.2.1邻接矩阵501100网的邻接矩阵存储表示无向带权图有向带权图7.2.2邻接表边结点无权图的邻接表01234注意！有向图的逆邻接表有向图的十字链表存储表示有向图的十字邻接表7.2.3边集数组structedge{intfromvex;intendvex;intweight;};007.3图的遍历7.3.1深度优先搜索遍历5555注意！7.3.2广度优先搜索遍历755分析！7.3.3非连通图的遍历和最小生成树在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G'555分析！一棵连通网(即连通带权图)中，具有权最小的生成树称为图的最小生成树最小生成树算法生成树的权为578Prim算法算法的关键：8算法实现技巧：80Kruskal算法算法的关键：将各顶点划分为不同集合，每个集合中的顶点表示一个无回路的连通分量。每当选取一条边时，若它的两个端点分属于不同的集合，应把它加入到生成树中，同时把端点所在的两个集合合并成一个集合，成为一个连同分量。若它的两个端点同属于一个集合，应放弃此边。18算法实现技巧：187.4拓扑排序概念：用顶点表示活动，边表示活动间先后关系的有向图称作顶点活动网，简称AOV网。一个AOV网应该是一个有向无环图，即不带有回路。若带有回路，则回路上的所有活动都无法进行。在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，此序列称作拓扑序列，由AOV网构造拓扑序列的过程叫做拓扑排序。由AOV网构造拓扑序列的拓扑排序算法4拓扑排序算法的实现