已知一个图的顶点集V和边集E分别为:V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)
已知一个图的顶点集V和边集E分别为:
V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
按照普里姆算法从顶点1出发得到最小生成树,试写出在最小生成树中依次得到的各条边。
已知一个图的顶点集V和边集E分别为:
V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
按照普里姆算法从顶点1出发得到最小生成树,试写出在最小生成树中依次得到的各条边。
第1题
A.(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20
B.(1,2)3,(4,6)4,(1,3)5,(2,3)6,(1,4)8,(3,6)9
C.(1,2)3,(1,3)5,(1,4)8,(4,6)4,(2,5)10,(4,7)20
D.(1,2)3,(1,3)5,(1,4)8,(2,5)10,(4,6)4,(4,7)20
第2题
以下图的叙述中,正确的是()。【华南理工大学2006一、1(2分)】
A.图与树的区别在于图的边数大于或等于顶点数
B.假设有图G=(V,{E)),顶点集V"∈V,E∈E,则V和{E}构成G的子图
C.无向图的连通分量指无向图中的极大连通子图
D.图的遍历就是从图中某一顶点出发访遍图中其余顶点
第3题
_________指的是从有向图G=(V,E)中得到一个顶点的线性序列,满足如果G包含边(u,v),则在该序列中,u就出现在v的前面。
A 图
B 深度优先搜索
C 广度优先搜索
D 拓扑排序
第4题
已知一具有n个顶点的有向图G=(V,E)采用邻接表存储方法。请写一算法,检查任意给定序列v1,v2,v3,…,vn(vi∈V,1≤i≤n)是否为该有向图的一个拓扑序列。 若是,算法给出信息1;否则,给出信息0。
第5题
已知一具有n个顶点的有向图G=(V,E)采用邻接表存储方法,请写一算法,检查任意给定序列v1,v2,…,vn,(vi∈V,1≤i≤n)是否为该有向图的一个拓扑序列。若是,算法给出信息是1,否则,给出信息0。【北京航空航天大学2005三(10分)】
第8题
二部图(biparite graph)G=(V,E)是一个能将其结点集V分为两个不相交子集V1和V2= V-V1的无向图,使得:V1中的任何两个结点在图G中均不相邻,V2中的任何两个结点在图G中也均不相邻。 (1)请各举一个结点个数为5的二部图和非二部图的例子。 (2)请用C或Pascal编写一个函数BIPARTITE判断一个连通无向图G是否是二部图,并分析程序的时间复杂度。设G用二维数组A来表示,大小为n*n(n为结点个数)。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【浙江大学1998