《第7章图结构》习题解答分解.doc

《数据结构与算法》 第7章 图结构 -. PAGE \* MERGEFORMAT 226.- -. PAGE \* MERGEFORMAT 66.- [键入文字]  PAGE \* MERGEFORMAT 1 第7章 图 结 构 本章学习要点 ◆熟悉图的定义、相关术语以及基本概念 ◆熟练掌握图的4种存储结构，能根据实际问题选择合适的存储结构 ◆熟练掌握图的两种遍历方法 ◆理解并掌握最小生成树意义和两种算法 ◆理解并掌握查找最短路径的有关算法 ◆理解并掌握拓扑排序的有关算法 ◆理解并掌握查找关键路径的有关算法 在计算机科学、工程以及其它许多学科中，常常需要研究数据对象之间的各种关系。比如，可以用线性表来表示数据对象之间的线性关系，用树结构来表示数据对象之间的某种层次关系。但是，还有许多问题（比如信息通信网络）中的数据对象是不能用以上两种关系来明确表示的，这就需要一种更为复杂的数据结构—图结构。图结构可以用来表示数据对象之间的任意关系，图中的每个结点都可以和其它任一结点相连接，即图中数据对象之间的对应关系是“多个对多个”的关系。 本章将详细介绍图的基本概念、各种存储结构、遍历方法，求图的连通分量、生成树、最短路径，最后介绍一些有关图的应用问题。 7.1图的定义和基本术语 7.1.1图的定义 图G(graph) 是由两个集合V和VR组成，记为G=(V,VR)。V是顶点的有穷非空集合；VR是定义在V上的所有关系（两个不同顶点之间的弧或边）的集合。VR可以是空集合，当VR为空集时G表示集合类结构类型。如图7.1(a)、(b)所示的是一个有向图和一个无向图。 7.1.2图结构的基本术语 （1）顶点(Vertex) 图中的数据元素。比如，图7.1中的顶点有：v1,v2,v3,v4,v5,v6。 （2）弧(Arc) 设VR是图中所有顶点之间的关系集，若v,w∈VR，则v,w表示从顶点v到顶点w的一条弧。 例如，在图7.1(a)所示的图G中的弧有：v1,v2,v1,v4,v3,v1,v3,v6,v4,v3,v5,v4和v6,v5,v6,v1共8条弧。 （3）弧尾(Tail) 弧的起始点。 （4）弧头(Head) 弧的终端点。一条弧用有序对符号“弧尾，弧头”来表示。 （5）有向图(Digraph) 由顶点和弧组???的图称为有向图。比如，图7.1(a)表示一个有向图。 （6）边(Edge) 设VR是图中所有顶点之间的关系集，若v,w∈VR必有w,v∈VR，则以无序对符号(v,w)或(w,v)来代替v,w和w,v，表示顶点v与顶点w之间的一条边。 例如，在图7.1(b)所示的图G中的边有：(v1,v2),(v1,v4),(v2,v3),(v2,v6),(v3,v5),(v4,v5)和(v5,v6)共7条边。 （7）无向图(Undigraph) 由顶点和边组成的图称为无向图。比如，图7.1(b)表示一个无向图。 （8）完全图(Completed graph) 用n表示图中的顶点数，则具有n(n-1)/2条边的无向图称为无向完全图；具有n(n-1)条弧的有向图称为有向完全图。当图G中边(或弧)的总数e满足：时，称其为稀疏图(sparse graph)；当e满足：时称其为稠密图(dense graph)。显然，完全图是稠密图，反之不然。图7.2(a)所示为由4个顶点组成的无向完全图，而图7.2(b)则是由3个顶点组成的有向完全图。 （9）权(Weight) 与图的边或弧相关的数（比如长度）称为权。 （10）网(Network) 具有权值的图称为网，带权的有向图称为有向网，带权的无向图称为无向网。比如，图7.3(a)表示的是一个有向网，而图7.3(b)表示的是一个无向网。 （11）子图(Subgraph) 假设有两个图G=(V,E)和G’=(V’,E’)，若V’V并且E’E，则称G’是G的子图。 例如，图7.4(a)为有向图及其部分子图，图7.4(b)为无向图及其部分子图。 （12）邻接点(Adjacent) 对于无向图G=(V,VR)，若边(v,w)∈VR，则称v和w互为邻接点，边(v,w)依附(Incident)于顶点v和w，或者说边(v,w)与顶点v、w相关联。对于有向图G=(V,VR)，若弧v,w∈VR，则称顶点v邻接到顶点w，顶点w邻接自顶点v。 （13）度(Degree) 在无向图中，顶点v的度是指和v相关联的边的数目，记为TD(v)。 （14）出度(Out degree)和入度(In degree) 在有向图中，顶点v的出度是指以v为弧尾的弧的数目，记为OD(v)；顶点v的入度是指以v为弧头的弧的数目，记为ID(v)；顶点v的度是指v的出度、入度的和，记为TD(v)。 一般地，如果顶点vi的度记为TD(v