图第8章8.1图的基本概念8.2图的存储结构8.3图的遍历8.4生成树和最小生成树8.5最短路径8.6拓扑排序8.7AOE网与关键路径本章小结
1 8.1 图的基本概念 第8章 图 8.2 图的存储结构 8.3 图的遍历 8.4 生成树和最小生成树 8.5 最短路径 8.6 拓扑排序 8.7 AOE网与关键路径 本章小结
8.1图的基本概念8.1.1图的定义图（Graph）G由两个集合V（vertex）和E（Edge）组成，记为G-(V，E），其中V是顶点的有限集合，记为V（G），E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)。和离散数学中采用的方法相同，通过顶点集和边集来表示一个图的逻辑结构，实际上就是二元组表示
2 8.1 图的基本概念 8.1.1 图的定义 图（Graph）G由两个集合V（vertex）和E（Edge） 组成，记为G=(V，E)，其中V是顶点的有限集合，记为 V(G)，E是连接V中两个不同顶点（顶点对）的边的有限集 合，记为E(G)。 和离散数学中采用的方法相同，通过顶点集和边集 来表示一个图的逻辑结构，实际上就是二元组表示
说明：对于n个顶点的图，对每个顶点连续编号，即顶点的编号为0-n-1。通过编号唯一确定一个顶点在图G中，如果代表边的顶点对是无序的，则称G为无向图，无向图中代表边的无序顶点对通常用圆括号括起来，用以表示一条无向边如果表示边的顶点对是有序的，则称G为有向图，在有向图中代表边的顶点对通常用尖括号括起来
3 在图G中，如果代表边的顶点对是无序的，则称G为无向 图，无向图中代表边的无序顶点对通常用圆括号括起来，用 以表示一条无向边。 如果表示边的顶点对是有序的，则称G为有向图，在有向 图中代表边的顶点对通常用尖括号括起来 。 说明：对于n个顶点的图，对每个顶点连续编号，即顶 点的编号为0－n-1。通过编号唯一确定一个顶点
8.1.2图的基本术语1.端点和邻接点在一个无向图中，若存在一条边(i4j），则称顶点和顶点为此边的两个端点并称它们互为邻接点(a)在一个有向图中，若存在一条边<i>，则称此边是顶点的一条出边，同时也是顶点的一条入边；称顶点和顶点分别为此边的起始端点（简称为起点）和终止端点（简称终点）：称顶点i和顶点i互为邻接点4(b)
4 8.1.2 图的基本术语 1. 端点和邻接点 在一个无向图中，若存在一条边(i， j)，则称顶点i和顶点j为此边的两个端点， 并称它们互为邻接点。 在一个有向图中，若存在一条边<i， j>，则称此边是顶点i的一条出边，同时 也是顶点j的一条入边；称顶点i和顶点j 分别为此边的起始端点（简称为起点） 和终止端点（简称终点）；称顶点i 和 顶点j 互为邻接点。 1 2 3 0 4 (a) 1 2 3 0 4 (b)
2.顶点的度入度和出度在无向图中，顶点所具有的边的数目称为该顶点的度在有向图中，以顶点为终点的入边的数目，称为该顶点的入度。以顶点为4始点的出边的数自，称为该顶点的出度(a)一个顶点的入度与出度的和为该顶点的度。若一个图中有n个顶点和e条边，每个顶点的度为d，（1≤n），则有：e=之4(b)5
5 2. 顶点的度、入度和出度 在无向图中，顶点所具有的边的数 目称为该顶点的度。 在有向图中，以顶点i为终点的入边 的数目，称为该顶点的入度。以顶点i为 始点的出边的数目，称为该顶点的出度。 一个顶点的入度与出度的和为该顶点的 度。 若一个图中有n个顶点和e条边，每 个顶点的度为di（1≤i≤n），则有： = n i i e d 1 2 1 ＝ 1 2 3 0 4 (a) 1 2 3 0 4 (b)