第七章图第七章图学习要点1．熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法的密切联系；2．熟练掌握图的两种遍历，深度优先遍历和广度优先遍历。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略。第七章图7.1图的定义和术语7.4图的连通性7.2图的存储结构7.4.1无向图的连通分量和生成树7.2.1数组表示法7.4.2最小生成树7.2.2邻接表7.5有向无环图及其应用7.2.3十字链表7.5.1拓扑排序7.2.4邻接多重表7.5.2关键路径7.3图的遍历7.6最短路径7.3.1广度优先遍历7.6.1从某个源点到其余各顶点的最短路径7.3.2深度优先遍历7.6.2每一对顶点之间的最短路径7.1图的定义和术语例G2=<V2,E2>V2={v1,v2,v3,v4}E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}图的应用举例例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的通信线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系三图的基本操作1CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图G2DestroyGraph(&G);初始条件：图G存在操作结果：销毁图G3LocateVex(G,u);初始条件：图G存在，u和G中顶点有相同特征操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其它信息。4GetVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的值5PutVex(&G,v,value);初始条件：图G存在，v是G中某个顶点操作结果：对v赋值value6FirstAdjVex(G,v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”。7NextAdjVex(G,v,w);初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。8InsertVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v9DeleteVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征操作结果：删除G中顶点v及相关的弧10InsertArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>11DeleteArc(&G,v,w);初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>12DFSTraverse(G,v,Visit());初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数。操作结果：从顶点v起深度优先遍历图G，对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败13BFSTraverse(G,v,Visit());初始条件：图G存在，v是G中某个顶点，Visit是顶点的应用函数。操作结果：从顶点v起广度优先遍历图G，对每个顶点调用函数Visit一次且一次。一旦visit()失败，则操作失败四、图的基本术语1邻接点及关联边邻接点：边的两个顶点关联边：若边e=(v,u),则称顶点v、u关连边e2顶点的度、入度、出度顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点有向边数顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n，边数为e图的所有顶点的度数和=2*e（每条边对图的所有顶点的度数和“贡献”2度）连通图、（强连通图）在无（有）向图G=<V,E>中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）子图设有两个图G=（V，E）、G1=（V1，E1），若V1V，E1E，E1关联的顶点都在V1中，则称G1是G的子图；例：图2、图3是图1的子图连通分图（强连通分量）无向图G的极大连通子图称为G的连通分量极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通；有向图D的极大强连通子图称为D的强连通分量极大强连通子图意思是：该子图是D强