我要评论
|
💖the begin💖点点关注，收藏不迷路💖
|
1、实现思想
通过递归或队列方式依次访问图中的节点，并使用辅助数组记录已访问节点，以实现遍历整个图的目的。实现深度优先搜索和广度优先搜索两种遍历算法。
dfs通过递归地深入图中的每个分支，直到无法再继续深入为止，然后回溯到上一个分支；
而bfs则通过逐层访问图中的节点，从起始节点开始向外扩展，直到访问到所有可达节点。
在实现中，dfs使用递归方式遍历节点，而bfs则利用队列实现节点的逐层访问。通过辅助数组记录已经访问的节点，避免重复访问，并最终完成整个图的遍历。
2、代码实现
package csdn;
public class graphtraversal { // 定义类graphtraversal
static int[][] graph = new int[][]{{0, 1, 1, 0, 0, 0}, // 定义邻接矩阵表示的图，每行代表一个顶点的相邻顶点情况
{0, 0, 0, 1, 0, 0},
{0, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0}};
static int[] help = new int[graph.length]; // 用来记录已经遍历过的元素
// dfs(深度优先遍历)
public static void dfstraversing(int node, int[][] graph) { // 定义dfs遍历方法，参数为起始节点和图的邻接矩阵
help[node] = 1; // 标记当前节点已经遍历过
system.out.println(node); // 打印当前节点
for (int i = 0; i < graph[node].length; ++i) { // 遍历当前节点的所有相邻节点
if (help[i] == 0 && i != node && graph[node][i] == 1) { // 如果相邻节点未被遍历且与当前节点相连
dfstraversing(i, graph); // 递归调用dfs遍历相邻节点
}
}
}
// bfs(广度优先遍历)
public static void bfstraversing(int[][] graph) { // 定义bfs遍历方法，参数为图的邻接矩阵
int[] queue = new int[graph.length]; // 创建队列用于存储待访问的节点
int cnt = 1; // 记录队列中元素个数
queue[0] = 0; // 将第一个顶点加入队列作为起始顶点
help[0] = 1; // 标记起始顶点已经被访问
system.out.println(0); // 打印起始顶点
for (int i = 0; i < cnt; ++i) { // 遍历队列中的节点
for (int j = 0; j < graph[queue[i]].length; ++j) { // 遍历当前节点的相邻节点
if (queue[i] != j && graph[queue[i]][j] == 1 && help[j] == 0) { // 如果相邻节点未被遍历且与当前节点相连
help[j] = 1; // 标记相邻节点已经被访问
queue[cnt++] = j; // 将相邻节点加入队列
system.out.println(j); // 打印相邻节点
}
}
}
}
public static void main(string[] args) { // 主方法
system.out.println("深度优先遍历："); // 打印dfs遍历提示
dfstraversing(0, graph); // 调用dfs遍历方法
resethelparray(); // 重置help数组
system.out.println("广度优先遍历："); // 打印bfs遍历提示
bfstraversing(graph); // 调用bfs遍历方法
}
// 重置help数组，以便重新运行遍历算法
private static void resethelparray() { // 定义重置help数组的方法
for (int i = 0; i < help.length; i++) { // 遍历help数组
help[i] = 0; // 将元素值重置为0
}
}
}
dfs遍历:
bfs遍历:
|
💖the end💖点点关注，收藏不迷路💖
|
发表评论