电子商务网站建设教材,网站建设完工报告,安徽网站建设方案开发,net开发的网站开发网站题目#xff1a; 图的深度优先搜索 描述#xff1a; 图的深度优先搜索类似于树的先根遍历#xff0c;是树的先根遍历的推广。即从某个结点开始#xff0c;先访问该结点#xff0c;然后深度访问该结点的第一棵子树#xff0c;依次为第二顶子树。如此进行下去#xff0c;直…题目 图的深度优先搜索 描述 图的深度优先搜索类似于树的先根遍历是树的先根遍历的推广。即从某个结点开始先访问该结点然后深度访问该结点的第一棵子树依次为第二顶子树。如此进行下去直到所有的结点都访问为止。在该题中假定所有的结点以“A”至“Z”中的若干字符表示且要求结点的访问顺序根据“A”至“Z”的字典顺序进行访问。例如有如下图 如果要求从H开始进行深度优先搜索则搜索结果为H-A-K-U-E. 输入 输入只包含一个测试用例第一行为一个自然数n表示顶点的个数第二行为n个大写字母构成的字符串表示顶点接下来是为一个n*n大小的矩阵表示图的邻接关系。数字为0表示不邻接否则为相应的边的长度。 最后一行为一个字符表示要求进行深度优先搜索的起始顶点。 输出 用一行输出深度优先搜索结果起始点为给定的顶点各顶点之间用一个空格隔开(注意后面的提示)。 样例输入 5 HUEAK 0 0 2 3 0 0 0 0 7 4 2 0 0 0 0 3 7 0 0 1 0 4 0 1 0 H 样例输出 H A K U E 代码
代码与图的广度搜索差不多不同的就是将队列变为栈
以下两个代码都差不多都是利用对应的ascll码转换成0~25相应的数字理论上来说是一样的
权值在本题没有使用
需注意如图 输入 5 HUEAG 0 0 2 3 0 0 0 0 7 4 2 0 0 0 0 3 7 0 0 1 0 4 0 1 0 U 输出 U A G H E 第一个栈直接储存字符使用时换成数字
import java.util.Scanner;
import java.util.Stack;public class Xingyuxingxi {public static void main(String[] args){Scanner scnew Scanner(System.in);int asc.nextInt();String bsc.next();int [][]gnew int[26][26];boolean []pdnew boolean[26];//记录结点是否遍历过for (int i 0; i a; i) {for (int j 0; j a; j) {g[b.charAt(i)-A][b.charAt(j)-A] sc.nextInt();//把字符转换成1~25的相应下标当假设b.charAt(i)A,b.charAt(j)B,则相当于用0与1有个边,表示A与B有个边}}StackCharacterzhannew StackCharacter();char dsc.next().charAt(0);zhan.push(d);while(!zhan.isEmpty()){dzhan.pop();int yd-A;if(!pd[y])System.out.print(d );pd[y]true;for (int i 25; i 0 ; i--) {//从最后一个字母开始入栈保证了小的字母先出栈栈先进后出if(g[y][i]!0!pd[i])//非0表示有连接false表示没被标记权值在这里没有用{char zm(char)(iA);zhan.push(zm);}}}}
}第二个先全部换成数字栈储存数字最后输出转换成字符
import java.util.Scanner;
import java.util.Stack;public class Xingyuxingxi {public static void main(String[] args){Scanner scnew Scanner(System.in);int asc.nextInt();String bsc.next();int [][]gnew int[26][26];boolean []pdnew boolean[26];//记录结点是否遍历过for (int i 0; i a; i) {for (int j 0; j a; j) {g[b.charAt(i)-A][b.charAt(j)-A] sc.nextInt();//把字符转换成1~25的相应下标当假设b.charAt(i)A,b.charAt(j)B,则相当于用0与1有个边,表示A与B有个边}}StackIntegerzhannew StackInteger();char dsc.next().charAt(0);zhan.push(d-A);while(!zhan.isEmpty()){int yzhan.pop();if(!pd[y])System.out.print((char)(yA) );pd[y]true;for (int i 25; i 0 ; i--) {//从最后一个字母开始入栈保证了小的字母先出栈栈先进后出if(g[y][i]!0!pd[i])//非0表示有连接false表示没被标记权值在这里没有用{zhan.push(i);}}}}
}
