第9章图9.1图的基本概念9.1.1图的定义图(Graph)G由两个集合V(Vertex)和E(Edge)组成，记为G-(V,E),其中V是顶点的有限集合，记为V(G),E是连接V中两个不同顶点(顶点对)的边的有限集合，记为E(G)。在图G中如果代表边的顶点对是无序的，则称G为无向图，无向图中代表边的无序顶点对通常用圆括号括起来，用以表示一条无向边。9.1.2图的基本术语1.端点和邻接点在一个无向图中，若存在一条边(vi,vi),则称vi和vj为此边的两个端点,并称它们互为邻接点。在一个有向图中,若存在一条边<vi,vi>,则称此边是顶点vi的一条出边,同时也是顶点vi的一条入边：称vi和vi分别为此边的起始端点（简称为起点）和终止端点（简称终点）：称vi和vj互为邻接点。2.顶点的度、入度和出度在无向图中，顶点所具有的边的数目称为该项点的度。在有向图中，以顶点vi为终点的入边的数目，称为该顶点的入度。以顶点vi为始点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。若一个图中有n个顶点和e条边，每个顶点的度为di(1≤i≤n),则有：3.完全图若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。显然，完全无向图包含有条边,完全有向图包含有n(n-1)条边。例如,图(a)所示的图是一个具有4个顶点的完全无向图，共有6条边。图(b)所示的图是一个具有4个顶点的完全有向图，共有12条边。6.路径和路径长度在一个图G=(V,E)中，从顶点vi到顶点vi的一条路径是一个顶点序列(vi,vil,vi2,"",vim,vi),若此图G是无向图,则边(vivil)(vil,vi2),"",(vim-1,vim)(vim,vi)属于E(G)：若此图是有向图,则<vi,vil><vilvi2>,""<vim-1,vim><vim,vp>属于E(G)。路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外,其余顶点均不相同,则称此路径为简单路径。例如,有图中,(v0,v2,v1)就是一条简单路径，其长度为2。7.回路或环若一条路径上的开始点与结束点为同一个顶点,则此路径被称为回路或环。开始点与结束点相同的简单路径被称为简单回路或简单环。8.连通、连通图和连通分量在无向图G中，若从顶点vi到顶点vi有路径，则称vi和vi是连通的。若图G中任意两个顶点都连通则称G为连通图否则称为非连通图。无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。9.强连通图和强连通分量在有向图G中,若从顶点vi到顶点vj有路径,则称从vi到vi是连通的。若图G中的任意两个顶点vi和vj都连通,即从vi到vj和从vi到vi都存在路径,则称图G是强连通图。例如，右边两个图都是强连通图
第 9 章 图 9.1 图的基本概念 9.1.1 图的定义 图(Graph)G 由两个集合 V(Vertex)和 E(Edge)组成,记为 G=(V,E),其中 V 是顶点的有 限集合,记为 V(G),E 是连接 V 中两个不同顶点(顶点对)的边的有限集合,记为 E(G)。 在图 G 中,如果代表边的顶点对是无序的,则称 G 为无向图,无向图中代表边的无序顶点对通 常用圆括号括起来,用以表示一条无向边。 9.1.2 图的基本术语 1. 端点和邻接点 在一个无向图中,若存在一条边(vi,vj),则称 vi 和 vj 为此边的两个端点,并称它们互为邻 接点。 在一个有向图中,若存在一条边<vi,vj>,则称此边是顶点 vi 的一条出边,同时也是顶点 vj 的一条入边；称 vi 和 vj 分别为此边的起始端点(简称为起点)和终止端点(简称终点)；称 vi 和 vj 互为邻接点。 2. 顶点的度、入度和出度 在无向图中,顶点所具有的边的数目称为该顶点的度。 在有向图中,以顶点 vi 为终点的入边的数目,称为该顶点的入度。以顶点 vi 为始点的出 边的数目,称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。 若一个图中有 n 个顶点和 e 条边,每个顶点的度为 di(1≤i≤n),则有： 3. 完全图 若无向图中的每两个顶点之间都存在着一条边,有向图中的每两个顶点之间都存在着方 向相反的两条边,则称此图为完全图。 显然,完全无向图包含有条边,完全有向图包含有 n(n-1)条边。例如,图(a)所示的图是一个 具有 4 个顶点的完全无向图,共有 6 条边。图(b)所示的图是一个具有 4 个顶点的完全有向图, 共有 12 条边。 6. 路径和路径长度 在一 个图 G=(V,E) 中 , 从 顶点 vi 到顶点 vj 的一 条 路径 是 一个 顶点 序 列 (vi,vi1,vi2,.,vim,vj),若此图 G 是无向图,则边(vi,vi1),(vi1,vi2),.,(vim-1,vim),(vim,vj)属于 E(G)；若此图是有向图,则<vi,vi1>,<vi1,vi2>,.,<vim-1,vim>,<vim,vj>属于 E(G)。 路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相 同外,其余顶点均不相同,则称此路径为简单路径。例如,有图中,(v0,v2,v1)就是一条简单路径, 其长度为 2。 7. 回路或环 若一条路径上的开始点与结束点为同一个顶点,则此路径被称为回路或环。开始点 与结束点相同的简单路径被称为简单回路或简单环。 8. 连通、连通图和连通分量 在无向图 G 中,若从顶点 vi 到顶点 vj 有路径,则称 vi 和 vj 是连通的。 若图 G 中任意两个顶点都连通,则称 G 为连通图,否则称为非连通图。 无向图 G 中的极大连通子图称为 G 的连通分量。显然,任何连通图的连通分量只有 一个,即本身,而非连通图有多个连通分量。 9. 强连通图和强连通分量 在有向图 G 中,若从顶点 vi 到顶点 vj 有路径,则称从 vi 到 vj 是连通的。 若图 G 中的任意两个顶点 vi 和 vj 都连通,即从 vi 到 vj 和从 vj 到 vi 都存在路径,则 称图 G 是强连通图。例如,右边两个图都是强连通图
有向图G中的极大强连通子图称为G的强连通分量。显然强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。9.2图的存储结构9.2.1邻接矩阵存储方法邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n(n>O)个顶点的图,顶点的顺序依次为(vO,vl,",vn-1),则G的邻接矩阵A是n阶方阵,其定义如下：(1)如果G是无向图,则：A[][]=1:若(vi,vi)EE(G)0:其他(2)如果G是有向图,则：A[][i]=1:若<vi,vj>EE(G)0:其他(3）如果G是带权无向图，则：8其他A[iji]=wij：若vi≠vj且(vi,vi)EE(G)(4）如果G是带权有向图,则：A[i][i]=wij:若vivj且<vi,vj>EE(G)80:其他邻接矩阵的特点如下：（1）图的邻接矩阵表示是惟一的。(2）无向图的邻接矩阵一定是一个对称矩阵。因此,按照压缩存储的思想,在具体存放邻接矩阵时只需存放上（或下）三角形阵的元素即可。(3）不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵,因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。(4)对于无向图，邻接矩阵的第i行(或第i列)非零元素或非α元素)的个数正好是第i个顶点vi的度。(5）对于有向图，邻接矩阵的第i行(或第i列)非零元素(或非80元素的个数正好是第i个顶点vi的出度(或入度)。（6）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。9.2.2邻接表存储方法图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。在邻接表中对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧)。每个单链表上附设一个表头结点。邻接表的特点如下：（1）邻接表表示不惟一。这是因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的取决于建立邻接表的算法以及边的输入次序。(2）对于有n个顶点和e条边的无向图,其邻接表有n个顶点结点和2e个边结点。显然.在总的边数小于n（n-1)/2的情况下，邻接表比邻接矩阵要节省空间。(3）对于无向图,邻接表的顶点vi对应的第i个链表的边结点数目正好是顶点vi的度。(4）对于有向图，邻接表的顶点vi对应的第i个链表的边结点数目仅仅是vi的出度。其入度为邻接表中所有adjvex域值为i的边结点数目。9.3图的遍历9.3.1图的遍历的概念从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。如果给定图是连通的无向图或者是强连通的有向图，则遍历过程一次就能完成，并可按访问的先后顺序得到由该图所
有向图 G 中的极大强连通子图称为 G 的强连通分量。显然,强连通图只有一个强连 通分量,即本身,非强连通图有多个强连通分量。 9.2 图的存储结构 9.2.1 邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵。设 G=(V,E)是具有 n(n＞0)个顶点的图, 顶点的顺序依次为(v0,v1,.,vn-1),则 G 的邻接矩阵 A 是 n 阶方阵,其定义如下： (1) 如果 G 是无向图,则： A[i][j]= 1:若(vi,vj)∈E(G) 0:其他 (2) 如果 G 是有向图,则： A[i][j]= 1:若<vi,vj>∈E(G) 0:其他 (3) 如果 G 是带权无向图,则： A[i][j]= wij :若 vi≠vj 且(vi,vj)∈E(G) ∞:其他 (4) 如果 G 是带权有向图,则： A[i][j]= wij :若 vi≠vj 且<vi,vj>∈E(G) ∞:其他 邻接矩阵的特点如下： (1) 图的邻接矩阵表示是惟一的。 (2) 无向图的邻接矩阵一定是一个对称矩阵。因此,按照压缩存储的思想,在具体存放 邻接矩阵时只需存放上(或下)三角形阵的元素即可。 (3) 不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵,因此,当图的顶点较多时,可 以采用三元组表的方法存储邻接矩阵。 (4) 对于无向图,邻接矩阵的第 i 行(或第 i 列)非零元素(或非∞元素)的个数正好是第 i 个顶点 vi 的度。 (5) 对于有向图,邻接矩阵的第 i 行(或第 i 列)非零元素(或非∞元素)的个数正好是第 i 个顶点 vi 的出度(或入度)。 (6) 用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连。但是, 要确定图中有多少条边,则必须按行、按列对每个元素进行检测,所花费的时间代价很大。这 是用邻接矩阵存储图的局限性。 9.2.2 邻接表存储方法 图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。在邻接表中, 对图中每个顶点建立一个单链表,第 i 个单链表中的结点表示依附于顶点 vi 的边(对有向图是 以顶点 vi 为尾的弧)。每个单链表上附设一个表头结点。 邻接表的特点如下： (1) 邻接表表示不惟一。这是因为在每个顶点对应的单链表中,各边结点的链接次序可 以是任意的,取决于建立邻接表的算法以及边的输入次序。 (2) 对于有 n 个顶点和 e 条边的无向图,其邻接表有 n 个顶点结点和 2e 个边结点。显 然,在总的边数小于 n(n-1)/2 的情况下,邻接表比邻接矩阵要节省空间。 (3) 对于无向图,邻接表的顶点 vi 对应的第 i 个链表的边结点数目正好是顶点 vi 的度。 (4) 对于有向图,邻接表的顶点 vi 对应的第 i 个链表的边结点数目仅仅是 vi 的出度。 其入度为邻接表中所有 adjvex 域值为 i 的边结点数目。 9.3 图的遍历 9.3.1 图的遍历的概念 从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问 图中的所有顶点,使每个顶点仅被访问一次,这个过程称为图的遍历。如果给定图是连通的无 向图或者是强连通的有向图,则遍历过程一次就能完成,并可按访问的先后顺序得到由该图所
有项点组成的一个序列。根据搜索方法的不同,图的遍历方法有两种：一种叫做深度优先搜索法(DFS)；另一种叫做广度优先搜索法(BFS)。9.3.2深度优先搜索遍历深度优先搜索遍历的过程是：从图中某个初始顶点v出发，首先访问初始顶点v,然后选择一个与项点V相邻且没被访问过的顶点W为初始顶点再从W出发进行深度优先搜索直到图中与当前项点v邻接的所有顶点都被访问过为止。显然,这个遍历过程是个递归过程。9.3.3广度优先搜索遍历广度优先搜索遍历的过程是：首先访问初始点vi接着访问vi的所有未被访问过的邻接点vil,vi2,,vit,然后再按照vil,vi2,vit的次序，访问每一个顶点的所有未被访问过的邻接点，依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。以邻接表为存储结构,用广度优先搜索遍历图时，需要使用一个队列,以类似于按层次遍历二叉树遍历图。9.3.4非连通图的遍历对于无向图来说，若无向图是连通图，则一次遍历能够访问到图中的所有顶点：但若无向图是非连通图，则只能访问到初始点所在连通分量中的所有顶点，其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点分别进行遍历，才能够访问到图中的所有顶点；对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点：否则不能访问到所有项点，为此同样需要再选初始点，继续进行遍历，直到图中的所有顶点都被访问过为止。9.3.5图遍历的应用9.4生成树和最小生成树9.4.1生成树的概念一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的(n-1)条边。如果在一棵生成树上添加一条边，必定构成一个环：因为这条边使得它依附的那两个顶点之间有了第二条路径。一棵有n个顶点的生成树(连通无回路图)有且仅有(n-1)条边）如果一个图有n个顶点和小于(n-1)条边,则是非连通图。如果它多于(n-1)条边,则一定有回路。但是，有（n-1）条边的图不一定都是生成树。对于一个带权（假定每条边上的权均为大于零的实数）连通无向图G中的不同生成树，其每棵树的所有边上的权值之和也可能不同；图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。按照生成树的定义,n个顶点的连通图的生成树有n个顶点、n-1条边。因此,构造最小生成树的准则有三条：(1）必须只使用该图中的边来构造最小生成树；(2）必须使用且仅使用n-1条边来连接图中的n个顶点；(3）不能使用产生回路的边。9.4.2无向图的连通分量和生成树在对无向图进行遍历时,对于连通图，仅需调用遍历过程(DFS或BFS)一次，从图中任一项点出发，便可以遍历图中的各个项点。对非连通图，则需多次调用遍历过程，每次调用得到的项点集连同相关的边就构成图的一个连通分量。设G=(V,E)为连通图则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T和B,其中T是遍历图过程中走过的边的集合,B是剩余的边的集合：TnB=Φ,TUB=E(G)
有顶点组成的一个序列。 根据搜索方法的不同,图的遍历方法有两种：一种叫做深度优先搜索法(DFS)；另一 种叫做广度优先搜索法(BFS)。 9.3.2 深度优先搜索遍历 深度优先搜索遍历的过程是：从图中某个初始顶点 v 出发,首先访问初始顶点 v,然后 选择一个与顶点 v 相邻且没被访问过的顶点 w 为初始顶点,再从 w 出发进行深度优先搜索, 直到图中与当前顶点 v 邻接的所有顶点都被访问过为止。显然,这个遍历过程是个递归过程。 9.3.3 广度优先搜索遍历 广度优先搜索遍历的过程是：首先访问初始点 vi,接着访问 vi 的所有未被访问过的 邻接点 vi1,vi2,.,vit,然后再按照 vi1,vi2,.,vit 的次序,访问每一个顶点的所有未被访问过的 邻接点,依次类推,直到图中所有和初始点 vi 有路径相通的顶点都被访问过为止。 以邻接表为存储结构,用广度优先搜索遍历图时,需要使用一个队列,以类似于按层次 遍历二叉树遍历图。 9.3.4 非连通图的遍历 对于无向图来说,若无向图是连通图,则一次遍历能够访问到图中的所有顶点； 但若无向图是非连通图,则只能访问到初始点所在连通分量中的所有顶点,其他连通 分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点,分别进行遍 历,才能够访问到图中的所有顶点； 对于有向图来说,若从初始点到图中的每个顶点都有路径,则能够访问到图中的所有顶点；否 则不能访问到所有顶点,为此同样需要再选初始点,继续进行遍历,直到图中的所有顶点都被 访问过为止。 9.3.5 图遍历的应用 9.4 生成树和最小生成树 9.4.1 生成树的概念 一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有构成一棵树 的(n-1)条边。 如果在一棵生成树上添加一条边,必定构成一个环：因为这条边使得它依附的那两 个顶点之间有了第二条路径。一棵有 n 个顶点的生成树(连通无回路图)有且仅有(n-1)条边, 如果一个图有 n 个顶点和小于(n-1)条边,则是非连通图。如果它多于(n-1)条边,则一定有回路。 但是,有(n-1)条边的图不一定都是生成树。 对于一个带权(假定每条边上的权均为大于零的实数)连通无向图 G 中的不同生成树,其每棵 树的所有边上的权值之和也可能不同；图的所有生成树中具有边上的权值之和最小的树称为 图的最小生成树。 按照生成树的定义,n 个顶点的连通图的生成树有 n 个顶点、n-1 条边。因此,构造最 小生成树的准则有三条： (1) 必须只使用该图中的边来构造最小生成树； (2) 必须使用且仅使用 n-1 条边来连接图中的 n 个顶点； (3) 不能使用产生回路的边。 9.4.2 无向图的连通分量和生成树 在对无向图进行遍历时,对于连通图,仅需调用遍历过程(DFS 或 BFS)一次,从图中任 一顶点出发,便可以遍历图中的各个顶点。对非连通图,则需多次调用遍历过程,每次调用得到 的顶点集连同相关的边就构成图的一个连通分量。 设 G=(V,E)为连通图,则从图中任一顶点出发遍历图时,必定将 E(G)分成两个集合 T 和 B,其中 T 是遍历图过程中走过的边的集合,B 是剩余的边的集合：T∩B=Φ,T∪B=E(G)
显然,G=(VT)是G的极小连通子图，即G是G的一棵生成树。由深度优先遍历得到的生成树称为深度优先生成树；由广度优先遍历得到的生成树称为广度优先生成树。这样的生成树是由遍历时访问过的n个顶点和遍历时经历的n-1条边组成。对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树，各个连通分量的生成树组成非连通图的生成森林。9.4.4普里姆算法普里姆(Prim)算法是一种构造性算法。9.4.5克鲁斯卡尔算法克鲁斯卡尔(Kruskal)算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。9.5最短路径9.5.1路径的概念在一个无权的图中，若从一顶点到另一顶点存在着一条路径,则称该路径长度为该路径上所经过的边的数目，它等于该路径上的项点数减1。由于从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。对于带权的图，考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度。从源点到终点可能不止一条路径,把带权路径长度最短的那条路径称为最短路径,其路径长度（权值之和）称为最短路径长度或者最短距离。9.5.2从一个顶点到其余各顶点的最短路径问题：给定一个带权有向图G与源点v求从v到G中其他顶点的最短路径并限定各边上的权值大于或等于0。9.5.3每对顶点之间的最短路径问题：对于一个各边权值均大于零的有向图,对每一对顶点vi≠vi求出vi与vj之间的最短路径和最短路径长度。本章小结本章基本学习要点如下：（1)掌握图的相关概念，包括图、有向图、无向图、完全图、子图、连通图、度、入度、出度、简单回路和环等定义。(2)重点掌握图的各种存储结构，包括邻接矩阵和邻接表等。(3)重点掌握图的基本运算，包括创建图、输出图、深度优先遍历、广度优先遍历算法等。练习教材中p217习题2、3和5。上机实验题教材中p217题1、2和3。(4)掌握图的其他运算，包括最小生成树、最短路径、拓扑排序等算法。(5)灵活运用图这种数据结构解决一些综合应用问题
显然,G'=(V,T)是 G 的极小连通子图,即 G'是 G 的一棵生成树。 由深度优先遍历得到的生成树称为深度优先生成树；由广度优先遍历得到的生成树称为广度 优先生成树。这样的生成树是由遍历时访问过的 n 个顶点和遍历时经历的 n-1 条边组成。 对于非连通图,每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树,各 个连通分量的生成树组成非连通图的生成森林。 9.4.4 普里姆算法 普里姆(Prim)算法是一种构造性算法。 9.4.5 克鲁斯卡尔算法 克鲁斯卡尔(Kruskal)算法是一种按权值的递增次序选择合适的边来构造最小生成树 的方法。 9.5 最短路径 9.5.1 路径的概念 在一个无权的图中,若从一顶点到另一顶点存在着一条路径,则称该路径长度为该路 径上所经过的边的数目,它等于该路径上的顶点数减 1。 由于从一顶点到另一顶点可能存在着多条路径,每条路径上所经过的边数可能不同, 即路径长度不同,我们把路径长度最短(即经过的边数最少)的那条路径叫做最短路径,其路径 长度叫做最短路径长度或最短距离。 对于带权的图,考虑路径上各边上的权值,则通常把一条路径上所经边的权值之和定义为该路 径的路径长度或称带权路径长度。 从源点到终点可能不止一条路径,把带权路径长度最短的那条路径称为最短路径,其 路径长度(权值之和)称为最短路径长度或者最短距离。 9.5.2 从一个顶点到其余各顶点的最短路径 问题：给定一个带权有向图 G 与源点 v,求从 v 到 G 中其他顶点的最短路径,并限定各 边上的权值大于或等于 0。 9.5.3 每对顶点之间的最短路径 问题：对于一个各边权值均大于零的有向图,对每一对顶点 vi≠vj,求出 vi 与 vj 之间 的最短路径和最短路径长度。 本章小结 本章基本学习要点如下： (1)掌握图的相关概念,包括图、有向图、无向图、完全图、子图、连通图、度、入度、 出度、简单回路和环等定义。 (2)重点掌握图的各种存储结构,包括邻接矩阵和邻接表等。 (3)重点掌握图的基本运算,包括创建图、输出图、深度优先遍历、广度优先遍历算法等。 练习 教材中 p217 习题 2、3 和 5。 上机实验题 教材中 p217 题 1、2 和 3。 (4)掌握图的其他运算,包括最小生成树、最短路径、拓扑排序等算法。 (5)灵活运用图这种数据结构解决一些综合应用问题