|
在图所示的各无向图中 ()找出所有的简单环 ()哪些图是连通图?对非连通图给出其连通分量 ()哪些图是自由树(或森林)? 答: ()所有的简单环(同一个环可以任一顶点作为起点) (a) (b)无 (c) (d)无 ()连通图 (a)(c)(d)是连通图 (b)不是连通图因为从到没有路径具体连通分量为 ()自由树(森林)自由树是指没有确定根的树无回路的连通图称为自由树 (a)不是自由树因为有回路 (b)是自由森林其两个连通分量为两棵自由树 (c)不是自由树 (d)是自由树 在图(下图)所示的有向图中 () 该图是强连通的吗? 若不是则给出其强连通分量 () 请给出所有的简单路径及有向环 () 请给出每个顶点的度入度和出度 () 请给出其邻接表邻接矩阵及逆邻接表 答 ()该图是强连通的所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径 ()简单路径是指在一条路径上只有起点和终点可以相同的路径 有vvvvvvvvvvvvvvvvvvvvvvvvvvvv另包括所有有向环有向环如下 vvvvvvvv(这两个有向环可以任一顶点作为起点和终点) ()每个顶点的度入度和出度 D(v)= ID(v)= OD(v)= D(v)= ID(v)= OD(v)= D(v)= ID(v)= OD(v)= D(v)= ID(v)= OD(v)= ()邻接表(注意边表中邻接点域的值是顶点的序号这里顶点的序号是顶点的下标值) vertex firstedge next ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ │v│─→│ │─→│ │∧│ ├─┼─┤ ├─┼─┤ └─┴─┘ │v│─→│ │∧│ ├─┼─┤ ├─┼─┤ │v│─→│ │∧│ ├─┼─┤ ├─┼─┤ │v│─→│ │∧│ └─┴─┘ └─┴─┘ 逆邻接表 ┌─┬─┐ ┌─┬─┐ │v│─→│ │∧│ ├─┼─┤ ├─┼─┤ │v│─→│ │∧│ ├─┼─┤ ├─┼─┤ ┌─┬─┐ │v│─→│ │─→│ │∧│ ├─┼─┤ ├─┼─┤ └─┴─┘ │v│─→│ │∧│ └─┴─┘ └─┴─┘ 邻接矩阵 假设图的顶点是AB请根据下述的邻接矩阵画出相应的无向图或有向图 ┌┓ ┌ ┓ | | | | | | | | | | | | | | | | | | ┕ ┙ ┕ ┙ (a) (b) 答: 假设一棵完全二叉树包括ABC等七个结点写出其邻接表和邻接矩阵 解 邻接表如下 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ │A │─→│ │ ─→│ │∧│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐ │B │─→│ │─→│ │─→│ │∧│ ├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤ │C │─→│ │─→│ │─→│ │∧│ ├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘ │D │─→│ │∧│ ├─┼─┤ ├─┼─┤ │E │─→│ │∧│ ├─┼─┤ ├─┼─┤ │F │─→│ │∧│ ├─┼─┤ ├─┼─┤ │G │─→│ │∧│ └─┴─┘ └─┴─┘ 邻接矩阵如下 对n个顶点的无向图和有向图采用邻接矩阵和邻接表表示时如何判别下列有关问题? () 图中有多少条边? ()任意两个顶点i和j是否有边相连? () 任意一个顶点的度是多少? 答 对于n个顶点的无向图和有向图用邻接矩阵表示时 ()设m为矩阵中非零元素的个数 无向图的边数=m/ 有向图的边数=m ()无论是有向图还是无向图在矩阵中第i行第j列的元素若为非零值则该两顶点有边相连 ()对于无向图任一顶点i的度为第i行中非零元素的个数 对于有向图任一顶点i的入度为第i列中非零元素的个数出度为第i行中非零元素的个数度为入度出度之和 当用邻接表表示时 ()对于无向图图中的边数=边表中结点总数的一半 对于有向图图中的边数=边表中结点总数 ()对于无向图任意两顶点间是否有边相连可看其中一个顶点的邻接表若表中的adjvex域有另一顶点位置的结点则表示有边相连 对于有向图则表示有出边相连 ()对于无向图任意一个顶点的度则由该顶点的边表中结点的个数来决定 对于有向图任意一个顶点的出度由该顶点的边表中结点的个数来决定入度则需遍历各顶点的边表(用逆邻接表可容易地得到其入度) n个顶点的连通图至少有几条边?强连通图呢? 答 n个顶点的连通图至少有n条边强连通图至少有(n)条边 DFS和BFS遍历各采用什么样的数据结构来暂存顶点?当要求连通图的生成树的高度最小应采用何种遍历? 答 DFS遍历采用栈来暂存顶点BFS采用队列来暂存顶点当要求连通图的生成树的高度最小时应采用BFS遍历 画出以顶点v为初始源点遍历图（下图）所示的有向图所得到的DFS 和BFS生成森林 答 按顺序输入顶点对()()()()()()()()()()()根据第节中算法CreatALGraph画出相应的邻接表并写出在该邻接表上从顶点开始搜索所得的DFS和BFS序列及DFS和BFS生成树 答 相应的邻接表如下 ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─< |
