|
在图(下图)所示的各无向图中 ()找出所有的简单环 ()哪些图是连通图?对非连通图给出其连通分量 ()哪些图是自由树(或森林)? 在图所示(下图)的有向图中 () 该图是强连通的吗? 若不是则给出其强连通分量 () 请给出所有的简单路径及有向环 () 请给出每个顶点的度入度和出度 () 请给出其邻接表邻接矩阵及逆邻接表 假设图的顶点是AB请根据下述的邻接矩阵画出相应的无向图或有向图 ┌┓ ┌ ┓ | | | | | | | | | | | | | | | | | | ┕ ┙ ┕ ┙ (a) (b) 假设一棵完全二叉树包括ABC等七个结点写出其邻接表和邻接矩阵 对n个顶点的无向图和有向图采用邻接矩阵和邻接表表示时如何判别下列有关问题? () 图中有多少条边? () 任意两个顶点i和j是否有边相连? () 任意一个顶点的度是多少? n个顶点的连通图至少有几条边?强连通图呢? DFS和BFS遍历各采用什么样的数据结构来暂存顶点?当要求连通图的生成树的高度最小应采用何种遍历? 画出以顶点v为初始源点遍历图(下图)所示的有向图所得到的DFS 和BFS生成森林 按顺序输入顶点对()()()()()()()()()()()根据第节中算法CreatALGraph画出相应的邻接表并写出在该邻接表上从顶点开始搜索所得的DFS和BFS序列及DFS和BFS生成树 什么样的图其最小生成树是唯一的?用PRIM 和Kruskal求最小生成树的时间各为多少?它们分别适合于哪类图? 对图（下图）所示的连通图请分别用Prim和Kruskal算法构造其最小生成树 对图（下图）所示的有向图试利用Dijkstra算法求出从源点到其它各顶点的最短路径并写出执行算法过程中扩充红点集的每次循环状态(见表) 试写出图（下图）所示有向图的所有拓扑序列并指出就用节给出的NonPreFirstTopSort算法求得的是哪个序列设邻接表的边表结点中的邻接点序号是递增有序的 什么样的DAG的拓扑序列是唯一的? 请以V为源点给出用DFS搜索图（上图）得到的逆拓扑序列 |
