六图练习题

图练习题（六）习题2010-06-1110:18:57阅读27评论0字号：大中小1.对下列图G：(1)从顶点A出发，求图G的一棵深度优先生成树；(2)从顶点B出发，求图G的一棵广度优先生成树；(3)求图G的一棵最小生成树。2.一棵非空的有向树中恰有一个顶点入度为0，其他顶点入度为l。但一个恰有一个顶点入度为0，其他顶点入度为l的有向图却不一定是一棵有向树。试举例说明之。3.有4个顶点A、B、C、D的无向连通图。按广度优先和深度优先搜索遍历结果都为A、B、C、D，画出所有可能的结构图。4.已知带权连通图G（V，E）的邻接表，如图所示，请画出该图，并分别以深度优先和广度优先遍历之，写出遍历中结点的序列，并画出该图的一棵最小生成树，其中表结点的3个域各为：5.已知一个无向图，如图所示，要求分别用普里姆和克鲁斯卡尔算法生成最小生成树（假设以V1为起点，试画出构造过程）。6.[选做]试写出把有向图的邻接矩阵表示转换为邻接表表示的算法。voidGraph_Conversion(MGraphMG,ALGraphAG){