设计算法以实现对无向图G的深度遍历,要求:将每一个连通分量中的顶点以一个表的形,式输出。例如,下
图的输出结果为:(1,3)(2,6,7,4,5,8)(9,10)。
注:本算法中可以调用以下几个函数:firstadj(g,1,)——返回图g中顶点v的第一个邻接点的号码,若不存在,则返回0。nextadj(g,v,w)——返回图g中顶点v的邻接点中处于w之后的邻接点的号码,若不存在,则返回0。nodes(g)——返回图g中的顶点数。【合肥工业大学2000五、4(8分)】
图的输出结果为:(1,3)(2,6,7,4,5,8)(9,10)。
注:本算法中可以调用以下几个函数:firstadj(g,1,)——返回图g中顶点v的第一个邻接点的号码,若不存在,则返回0。nextadj(g,v,w)——返回图g中顶点v的邻接点中处于w之后的邻接点的号码,若不存在,则返回0。nodes(g)——返回图g中的顶点数。【合肥工业大学2000五、4(8分)】
以下图的叙述中,正确的是()。【华南理工大学2006一、1(2分)】
A.图与树的区别在于图的边数大于或等于顶点数
B.假设有图G=(V,{E)),顶点集V"∈V,E∈E,则V和{E}构成G的子图
C.无向图的连通分量指无向图中的极大连通子图
D.图的遍历就是从图中某一顶点出发访遍图中其余顶点
点序列和按广度优先搜索遍历得到的顶点序列。
试扩充深度优先搜索算法,在遍历图的过程中建立生成森林的子女-兄弟链表。算法的首部为其中,指针t指向生成森林上具有图顶点v信息的根结点。(提示:在继续按深度方向从根v的某一未访问过的邻接顶点w向下遍历之前,建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树)
已知一个无向图如下图所示,要求分别用Prim和Kruskal算法生成最小生成树(假设以①为起点,试画出构造过程)。
【哈尔滨工业大学2000九(8分)】
图的m着色问题描述如下:给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色.如果有一种着色法,使G中每条边的2个顶点着不同颜色,则称这个图是m可着色的.图的m着色问题是对于给定图G和m种颜色,找出所有不同的着色法.
算法设计:对于给定的无向连通图G和m种不同的颜色,计算图的所有不同的着色法.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n,k和m,表示给定的图G有n个项点和k条边,m种颜色.顶点编号为1,2,...,n接下来的k行中,每行有2个正整数u、v,表示图G的一条边(u,v).
结果输出:将计算的不同的着色方案数输出到文件output.txt.