西华师范大学：《算法与程序设计》课程教学资源_第六章 图

第6章图 本章中介绍下列主要内容: 图的定义 图的存储结构 ●图的遍历操作 ●图的几个典型问题 西加大学数学与信息学院

ぜ6【 భ ᴀゴЁҟ㒡ϟ߫Џ㽕ݙᆍ˖ l ೒ⱘᅮН l ೒ⱘᄬټ㒧ᵘ l ೒ⱘ䘡ग़᪡԰ l ೒ⱘ޴Ͼ݌ൟ䯂乬 ߎ䗔

61图的定义 62图的存储结构 6.3图的遍历 64最小生成树问题 6.5拓扑排序问题 西加大学数学与信息学院

6.1 ೒ⱘᅮН 6.2 ೒ⱘᄬټ㒧ᵘ 6.3 ೒ⱘ䘡ग़ 6.4 ᳔ᇣ⫳៤ᷥ䯂乬 6.5 ᢧᠥᥦᑣ䯂乬

6l图的定义 6.1.1定义 图是由结点的有穷集合V和边的集合E组成。其 中,为了与树形结构加以区别,在图结构中常常将结 点称为顶点,边是顶点的有序偶对,若两个顶点之间 存在一条边,就表示这两个顶点具有相邻关系。 西加大学数学与信息学院

6.1 ೒ⱘᅮН 6.1.1 ᅮН ೒ᰃ⬅㒧⚍ⱘ᳝か䲚ড়V੠䖍ⱘ䲚ড়E㒘៤DŽ݊ ЁˈЎњϢᷥᔶ㒧ᵘࡴҹऎ߿೒೼ˈ㒧ᵘЁᐌᐌᇚ㒧 ⚍⿄Ў乊⚍ˈ䖍ᰃ乊⚍ⱘ᳝ᑣيᇍˈ㢹ϸϾ乊⚍П䯈 ᄬ೼ϔᴵ䖍ˈህ㸼⼎䖭ϸϾ乊⚍݋᳝Ⳍ䚏݇㋏DŽ

图6-1 西加大学数学与信息学院 网囧

೒ 6-1 (a) (b)

在上面两个图结构中,一个是有向图,即每条 边都有方向,另一个是无向图,即每条边都没有方 向 在有向图中,通常将边称作弧,含箭头的一端 称为弧头,另一端称为弧尾,记作两条弧。若无向图中有n个顶点,则 最多有m(n-)/2条边,我们又将具有n(n-)/2条边的 无向图称作无向完全图 西加大数学与信启学览 网囧

೼Ϟ䴶ϸϾ೒㒧ᵘЁˈϔϾᰃ᳝৥೒ˈे↣ᴵ 䖍䛑᳝ᮍ৥ˈ঺ϔϾᰃ᮴৥೒ˈे↣ᴵ䖍䛑≵᳝ᮍ ৥DŽ ೼᳝৥೒Ёˈ䗮ᐌᇚ䖍⿄԰ᓻˈ৿ㆁ༈ⱘϔッ ⿄Ўᓻ༈ˈ঺ϔッ⿄Ўᓻሒˈ䆄԰ˈᅗ㸼⼎ Ң乊⚍viࠄ乊⚍vj᳝ϔᴵ䖍DŽ 㢹᳝৥೒Ё᳝nϾ乊⚍ˈ᳔߭໮᳝n(n-1)ᴵᓻˈ ៥Ӏজᇚ݋᳝n(n-1)ᴵᓻⱘ᳝৥೒⿄԰᳝৥ᅠܼ ೒DŽ ҹ乊⚍vЎᓻሒⱘᓻⱘ᭄Ⳃ⿄԰乊⚍vⱘߎᑺˈ ҹ乊⚍vЎᓻ༈ⱘᓻⱘ᭄Ⳃ⿄԰乊⚍vⱘܹᑺDŽ ೼᮴৥೒Ёˈ䖍䆄԰(vi ,vj )ˈᅗ㭈⎉ⴔᄬ೼੠ϸᴵᓻDŽ㢹᮴৥೒Ё᳝nϾ乊⚍ˈ߭ ᳔໮᳝n(n-1)/2ᴵ䖍ˈ៥Ӏজᇚ݋᳝n(n-1)/2ᴵ䖍ⱘ ᮴৥೒⿄԰᮴৥ᅠܼ೒DŽ

与顶点v相关的边的条数称作顶点v的度。 路径长度是指路径上边或弧的数目。 若第一个顶点和最后一个顶点相同,则这条路 径是一条回路。 若路径中顶点没有重复出现,则称这条路径为 简单路径。 在无向图中,如果从顶点v到顶点v有路径, 则称v和v连通。如果图中任意两个顶点之间都连通, 则称该图为连通图,否则,将其中的极大连通子图称 为连通分量。 在有向图中,如果对于每一对顶点v和v;,从v 到v和从v到v都有路径,则称该图为强连通图;否 则,将其中的极大连通子图称为强连通分量。 西加大学数学与信息学院 网囧

Ϣ乊⚍vⳌ݇ⱘ䖍ⱘᴵ᭄⿄԰乊⚍vⱘᑺDŽ 䏃ᕘ䭓ᑺᰃᣛ䏃ᕘϞ䖍៪ᓻⱘ᭄ⳂDŽ 㢹㄀ϔϾ乊⚍੠᳔ৢϔϾ乊⚍Ⳍৠˈ߭䖭ᴵ䏃 ᕘᰃϔᴵಲ䏃DŽ 㢹䏃ᕘЁ乊⚍≵᳝䞡໡ߎ鹵߭ˈ⦃䖭ᴵ䏃ᕘЎ ㅔऩ䏃ᕘDŽ ೼᮴৥೒ЁˈབᵰҢ乊⚍viࠄ乊⚍vj᳝䏃ᕘˈ ߭⿄vi੠vj䖲䗮DŽབᵰ೒ЁӏᛣϸϾ乊⚍П䯈䛑䖲䗮ˈ ߭⿄䆹೒Ў䖲䗮೒ˈ৺߭ˈᇚ݊Ёⱘᵕ໻䖲䗮ᄤ೒⿄ Ў䖲䗮ߚ䞣DŽ ೼᳝৥೒ЁˈབᵰᇍѢ↣ϔᇍ乊⚍vi੠vjˈҢvi ࠄvj੠Ңvjࠄvi䛑᳝䏃ᕘˈ߭⿄䆹೒Ўᔎ䖲䗮೒˗৺ ߭ˈᇚ݊Ёⱘᵕ໻䖲䗮ᄤ೒⿄Ўᔎ䖲䗮ߚ䞣DŽ

6.1.2图的基本操作 基本操作: 1)创建一个图结构 Create Graph(G) (2)检索给定顶点 Locate vex(G,item) (3)获取图中某个顶点 Getvex(G,y) (4)为图中顶点赋值 Putvex(G,y,lue) 5)返回第一个邻接点 FirstAdjvex(G,y) (6)返回下一个邻接点 NextAdjVex(G,v,w) (7)插入一个顶点 InsertVex(G,y) (8)删除一个顶点 Deletevex(G,y) 9)插入一条边 Inserted(G,y,w) 10)删除一条边 Deleteedge(Gv,w) (11)遍历图 Traverse(G,y) 西加大学数学与信息学院 网囧

6.1.2 ೒ⱘ෎ᴀ᪡԰ ෎ᴀ᪡԰˖ ˄1˅߯ᓎϔϾ೒㒧ᵘ CreateGraph(G) ˄2˅Ẕ㋶㒭ᅮ乊⚍ LocateVex(G,item) ˄3˅㦋প೒ЁᶤϾ乊⚍ GetVex(G,v) ˄4˅Ў೒Ё乊⚍䌟ؐ PutVex(G,v,value) ˄5˅䖨ಲ㄀ϔϾ䚏᥹⚍ FirstAdjVex(G,v) ˄6˅䖨ಲϟϔϾ䚏᥹⚍ NextAdjVex(G,v,w) ˄7˅ᦦܹϔϾ乊⚍ InsertVex(G,v) ˄8˅ߴ䰸ϔϾ乊⚍ DeleteVex(G,v) ˄9˅ᦦܹϔᴵ䖍 InsertEdge(G,v,w) ˄10˅ߴ䰸ϔᴵ䖍 DeleteEdge(G,v,w) ˄11˅䘡ग़೒ Traverse(G,v)

6.2图的存储结构 6.2.1邻接矩阵 1.有向图的邻接矩阵 具有n个顶点的有向图可以用一个nXn的方形矩阵 表示。假设该矩阵的名称为M,则当~>是该有向图 中的一条弧时,Mi=1;否则Mj=0。第个顶点的 出度为矩阵中第i行中“1”的个数;入度为第i冽中“1”的 个数,并且有向图弧的条数等于矩阵中“1”的个数。 西加大学数学与信息学院 网囧

6.2 ೒ⱘᄬټ㒧ᵘ 6.2.1 䚏᥹ⶽ䰉 1. ᳝৥೒ⱘ䚏᥹ⶽ䰉 ݋᳝nϾ乊⚍ⱘ᳝৥೒ৃҹ⫼ϔϾn´nⱘᮍᔶⶽ䰉 㸼⼎DŽ؛䆒䆹ⶽ䰉ⱘৡ⿄ЎMˈ߭ᔧᰃ䆹᳝৥೒ ЁⱘϔᴵᓻᯊˈM[i,j]=1˗৺߭M[i,j]=0DŽ㄀iϾ乊⚍ⱘ ߎᑺЎⶽ䰉Ё㄀i㸠Ё³´ⱘϾ᭄˗ܹᑺЎ㄀i߫Ё³´ⱘ Ͼ᭄ˈᑊϨ᳝৥೒ᓻⱘᴵ᭄ㄝѢⶽ䰉Ё³´ⱘϾ᭄DŽ

1.2无向图的邻接矩阵 具有n个顶点的无向图也可以用一个nxn的方形矩 阵表示。假设该矩阵的名称为M,则当(vy)是该无 向图中的一条边时,M[=Mij=1;否则, M[ij=Mⅰ}=0。第个顶点的度为矩阵中第i行中“1 的个数或第i中“1”的个数。图中边的数目等于矩阵 中“1”的个数的一半,这是因为每条边在矩阵中描述了 两次。 西加大学数学与信息学院 网囧

ˊ2 ᮴৥೒ⱘ䚏᥹ⶽ䰉 ݋᳝nϾ乊⚍ⱘ᮴৥೒гৃҹ⫼ϔϾn´nⱘᮍᔶⶽ 䰉㸼⼎DŽ؛䆒䆹ⶽ䰉ⱘৡ⿄ЎMˈ߭ᔧ˄vi ,vj˅ᰃ䆹᮴ ৥೒Ёⱘϔᴵ䖍ᯊˈM[i,j]=M[j,i]=1˗৺߭ˈ M[i,j]=M[j,j]=0DŽ㄀iϾ乊⚍ⱘᑺЎⶽ䰉Ё㄀i 㸠Ё³´ ⱘϾ᭄៪㄀i߫Ё³´ⱘϾ᭄DŽ೒Ё䖍ⱘ᭄ⳂㄝѢⶽ䰉 Ё³´ⱘϾ᭄ⱘϔञˈ䖭ᰃ಴Ў↣ᴵ䖍೼ⶽ䰉Ёᦣ䗄њ ϸ⃵DŽ

01000 M=00010 10000 00100 图6-4 西加大学数学与信息学院 网囧

೒ 6-4