结构c语言版本图

《结构c语言版本图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章图重点难点要求掌握图的基本概念和术语；熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则；熟练掌握图的两种遍历算法，熟练掌握图在实际应用中的主要算法：最小生成树算法、最短路径算法、拓扑排序和关键路径算法。矚慫润厲钐瘗睞枥庑赖。典型例题1在下图所示的有向图中：　(1)该图是强连通的吗?若不是，则给出其强连通分量。　(2)请给出所有的简单路径及有向环。　(3)请给出每个顶点的度，入度和出度。　(4)请给出其邻接表、邻接矩阵及逆邻接表。答：　(1)该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。　(2)简单路径是指在一条路径上只有起点和终点可以相同

2、的路径：　　有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下：　　　　　v1v2v3v1、v1v4v3v1(这两个有向环可以任一顶点作为起点和终点)　(3)每个顶点的度、入度和出度：　　　D(v1)=3　ID(v1)=1　OD(v1)=2　　　D(v2)=2　ID(v2)=1　OD(v2)=1　　　D(v3)=3　ID(v3)=2　OD(v3)=1　　　D(v4)=2　ID(v4)=1　OD(v4)=1　(4)邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点

3、的下标值-1)  vertexfirstedge next　　　┌─┬─┐ ┌─┬─┐ ┌─┬─┐　　0│v1│　─→│1│　─→│3│∧│     ├─┼─┤ ├─┼─┤ └─┴─┘    1│v2│　─→│2│∧│     ├─┼─┤ ├─┼─┤    2│v3│　─→│0│∧│     ├─┼─┤ ├─┼─┤    3│v4│　─→│2│∧│     └─┴─┘ └─┴─┘ 逆邻接表：   ┌─┬─┐ ┌─┬─┐  0│v1│　─→│2│∧│   ├─┼─┤ ├─┼─┤  1│v2│　─→│0│∧│   ├─┼─┤ ├─┼─┤ ┌─┬─┐  2│v3│　─→│1│　─→│3│∧│  

4、 ├─┼─┤ ├─┼─┤ └─┴─┘  3│v4│　─→│0│∧│   └─┴─┘ └─┴─┘ 邻接矩阵：   0101   0010   1000   0010聞創沟燴鐺險爱氇谴净。2.对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题?(1)图中有多少条边?(2)任意两个顶点i和j是否有边相连?(3)任意一个顶点的度是多少?【解】对于n个顶点的无向图和有向图，用邻接矩阵表示时：(1)设m为矩阵中非零元素的个数　　　无向图的边数=m/2　　　有向图的边数=m　(2)无论是有向图还是无向图，在矩阵中第i行,第j列的元素若为非零值，则该两顶点有边相连。　(3)对于无

5、向图，任一顶点i的度为第i行中非零元素的个数。　　对于有向图，任一顶点i的入度为第i列中非零元素的个数，出度为第i行中非零元素的个数，度为入度出度之和。残骛楼諍锩瀨濟溆塹籟。　　当用邻接表表示时：　(1)对于无向图，图中的边数=边表中结点总数的一半。　　　对于有向图，图中的边数=边表中结点总数。　(2)对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的adjvex域有另一顶点位置的结点，则表示有边相连。酽锕极額閉镇桧猪訣锥。　　　对于有向图，则表示有出边相连。　(3)对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。对于有向图，任意一个顶点的出度由该顶点

6、的边表中结点的个数来决定，入度则需遍历各顶点的边表。(用逆邻接表可容易地得到其入度。)彈贸摄尔霁毙攬砖卤庑。3.DFS和BFS遍历各采用什么样的数据结构来暂存顶点?当要求连通图的生成树的高度最小，应采用何种遍历?謀荞抟箧飆鐸怼类蒋薔。【解】DFS遍历采用栈来暂存顶点。BFS采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用BFS遍历。厦礴恳蹒骈時盡继價骚。4.对下图所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。 答：　　5.什么样的DAG的拓扑序列是唯一的?答：确定了排序的源点，DAG图中无前趋顶点只有一个且从该点到终点只有一条路径时，它的拓扑序列才6.请以

7、V0为源点，给出用DFS搜索下图得到的逆拓扑序列。     答：   逆拓扑序列是：V4V2V1V0V1V6V5是唯一的。习题精选1．选择题（1）在一个图中，所有顶点的度数之和等于图的边数的（）倍。A．1/2B．1C．2D．4茕桢广鳓鯡选块网羈泪。（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A．1/2B．1C．2D．4鹅娅尽損鹌惨歷茏鴛賴。（3）具有n个顶点的有向图最多有（）条边。A．nB．n