数据结构之图课件[精].ppt

数据结构
第7章图
第7章图
知识点
图的逻辑结构特征及图的基本术语
邻接矩阵和邻接表两种图的存储结构的特点及适用范围
深度优先搜索和广度优先搜索两种遍历算法的特点和执行过程
生成树和最小生成树的概念及构造最小生成树的prim和kruskal算法
最短路径的含义及求最短路径的算法
拓扑排序的基本思想和步骤
关键路径法及其在管理科学中的作用
难点
图的遍历、最小生成树、最短路径、拓朴排序算法的理解
关键路径法求关键活动和关键路径的方法
要求
熟练掌握以下内容:
图的存储结构
图的遍历算法
了解以下内容:
图的最小生成树和求最小生成树算法的基本思想
带权有向图的最短路径问题
利用AOV网络的拓朴排序问题
利用AOE网络的关键路径法
图的定义和基本术语
图是一个二元组
G=(V,E)
其中 V={x | xdata object} 点的集合
E={<x,y> | p(x,y)  x, y  V} 边的集合
P(x,y)表示从x到y的一条边
无向图:对于一个图G,若边集合E(G)为无向边的集合,则称该图为无向图。
有向图:对于一个图G,若边集合E(G)为有向边的集合,则称该图为有向图。
有向图与无向图
无向图G1
有向图G2
子图
顶点的度:图中与每个顶点相连的边数,叫该顶点的度(Degree),记作TD(V)。
入度、出度:对于有向图,顶点的度分为入度和出度,入度是以该顶点为终点的入边数目;出度是以该顶点为起点的出边数目,该顶点的度等于其入度和出度之和。分别记作
ID(V),OD(V)。
路径(回路):若从某顶点Vp出发,沿一些边经过顶点V1,V2,…,Vm到达,Vq,则称顶点序列(Vp, V1,V2,…,Vm, Vq)为从Vp到Vq的路径(Path)。
若其中间顶点不重复,则称简单路径;若第1个顶点和最后一个顶点相同,则称为回路。
路径长度:对于无权的图,路径长度指的是沿此路径上边的数目;对于有权图,一般是取沿路径各边的权之和作为此路径的长度。