15、图的遍历的实现

83 阅读 0 评论 55 点赞

我是靠谱客的博主传统毛巾，最近开发中收集的这篇文章主要介绍15、图的遍历的实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

目的：通过本项目的实训，掌握如下内容：

（1）理解图的深度优先和广度优先遍历的思想；

（2）掌握邻接矩阵存储图的深度优先和广度优先遍历的实现；

（3）掌握邻接表存储图的深度优先和广度优先遍历的实现；；

要求一:

图的深度优先搜索类似于树的先根遍历，是树的先根遍历的推广。即从某个结点开始，先访问该结点，然后深度访问该结点的第一棵子树，依次为第二顶子树。如此进行下去，直到所有的结点都访问为止。在该题中，假定所有的结点以“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

算法提示：首先根据图的邻接矩阵创建邻接表（采用后插法，即每个边结点都插入到最后一个位置），然后结合栈结构完成图的深度优先遍历

要求二：

图的广度优先搜索
描述：
图的广度优先搜索类似于树的按层次遍历，即从某个结点开始，先访问该结点，然后访问该结点的所有邻接点，再依次访问各邻接点的邻接点。如此进行下去，直到所有的结点都访问为止。在该题中，假定所有的结点以“A”--“Z”中的若干字符表示，且要求结点的访问顺序要求根据由“A”至“Z”的字典顺序进行访问。例如有如下图：

如果要求从H开始进行广度优先搜索，则搜索结果为：H->A->E->K->U.
输入：
输入只包含一个测试用例，第一行为一个自然数n，表示顶点的个数，第二行为n个大写字母构成的字符串，表示顶点，接下来是为一个n*n大小的矩阵，表示图的邻接关系。数字为0表示不邻接，否则为相应的边的长度。
最后一行为一个字符，表示要求进行广度优先搜索的起始顶点。
输出：
用一行输出广度优先搜索结果，起始点为给定的顶点，各顶点之间用一个空格隔开。要求同一顶点的邻接点的访问顺序按“A”---“Z”的字典顺序。

样例输入：
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 E K U

要求一：

// 图的深度优先搜索
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入顶点个数
int vexnum = sc.nextInt();
// 输入顶点
String s = sc.next();
// 输入图
int[][] ver = new int[vexnum][vexnum];
for (int i = 0; i < vexnum; i++) {
for (int j = 0; j < vexnum; j++) {
ver[i][j] = sc.nextInt();
}
}
// 输入起点
char first = sc.next().charAt(0);
String dfs = "";
// 找到起点
int root = 0;
for (int i = 0; i < vexnum; i++) {
if (s.charAt(i) == first) {
root = i;
break;
}
}
// 利用栈遍历图
Stack<Integer> st = new Stack<>();
st.add(root);
boolean[] vi = new boolean[vexnum];
vi[root] = true;
while (!st.isEmpty()) {
int top = st.pop();
dfs += s.charAt(top);
for (int i = 0; i < vexnum; i++) {
if (ver[top][i] != 0 && vi[i] == false) {
vi[i] = true;
st.add(i);
}
}
}
// 输出图的深度优先搜索
for (int i = 0; i < dfs.length(); i++) {
if (i > 0) System.out.print(" ");
System.out.print(dfs.charAt(i));
}
System.out.println();
}
}

要求二：

// 图的广度优先搜索
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入顶点个数
int vexnum = sc.nextInt();
// 输入顶点
String s = sc.next();
// 输入图
int[][] ver = new int[vexnum][vexnum];
for (int i = 0; i < vexnum; i++) {
for (int j = 0; j < vexnum; j++) {
ver[i][j] = sc.nextInt();
}
}
// 输入起点
char first = sc.next().charAt(0);
String bfs = "";
// 找到起点
int root = 0;
for (int i = 0; i < vexnum; i++) {
if (s.charAt(i) == first) {
root = i;
break;
}
}
// 利用队列遍历图
Queue<Integer> q = new LinkedList<>();
q.add(root);
boolean[] vi = new boolean[vexnum];
vi[root] = true;
while (!q.isEmpty()) {
int top = q.poll();
bfs += s.charAt(top);
for (int i = vexnum - 1; i >= 0; i--) {
if (ver[top][i] != 0 && vi[i] == false) {
vi[i] = true;
q.add(i);
}
}
}
// 输出图的广度优先搜索
for (int i = 0; i < bfs.length(); i++) {
if (i > 0) System.out.print(" ");
System.out.print(bfs.charAt(i));
}
System.out.println();
}
}