互联网网站开发创业计划书,数字资产交易网站建设,网站怎么做多语言展示,专注WordPress网站建设开发1.深度优先理论基础(dfs)
dfs的两个关键操作
搜索方向#xff0c;是认准一个方向搜#xff0c;直到碰壁之后再换方向
换方向是撤销原路径#xff0c;改为节点链接的下一个路径#xff0c;回溯的过程。dfs解题模板
void dfs(参数) {if (终止条件) {存放结果;return;}for …1.深度优先理论基础(dfs)
dfs的两个关键操作
搜索方向是认准一个方向搜直到碰壁之后再换方向
换方向是撤销原路径改为节点链接的下一个路径回溯的过程。dfs解题模板
void dfs(参数) {if (终止条件) {存放结果;return;}for (选择本节点所连接的其他节点) {处理节点;dfs(图选择的节点); // 递归回溯撤销处理结果}
}Java代码实现
邻接矩阵表示的图
public class DFSTraversalRecursive {private int[][] adjacencyMatrix; // 邻接矩阵private boolean[] visited; // 用于标记节点是否被访问过private int numNodes; // 节点数量public DFSTraversalRecursive(int[][] matrix) {this.adjacencyMatrix matrix;this.numNodes matrix.length;this.visited new boolean[numNodes];}// 递归实现的深度优先搜索遍历public void dfsTraversalRecursive(int startNode) {visited[startNode] true; // 标记当前节点为已访问System.out.print(startNode ); // 输出当前节点for (int i 0; i numNodes; i) {// 如果存在从当前节点到节点 i 的边并且节点 i 还未被访问过if (adjacencyMatrix[startNode][i] 1 !visited[i]) {dfsTraversalRecursive(i); // 递归调用从节点 i 开始深度优先搜索}}}
}邻接表表示的图
public class DFSTraversalAdjacencyList {private ListListInteger adjacencyList; // 邻接表存储图的结构private boolean[] visited; // 标记节点是否被访问过// 构造函数初始化邻接表和visited数组public DFSTraversalAdjacencyList(int numNodes) {this.adjacencyList new ArrayList();for (int i 0; i numNodes; i) {this.adjacencyList.add(new ArrayList());}this.visited new boolean[numNodes];}// 添加边到邻接表public void addEdge(int source, int destination) {adjacencyList.get(source).add(destination);}// 递归实现的深度优先搜索遍历public void dfsTraversalRecursive(int startNode) {visited[startNode] true; // 标记当前节点为已访问System.out.print(startNode ); // 输出当前节点// 遍历当前节点的所有邻居节点for (int neighbor : adjacencyList.get(startNode)) {if (!visited[neighbor]) {dfsTraversalRecursive(neighbor); // 递归调用从邻居节点开始深度优先搜索}}}2.广度优先搜索理论基础(bfs)
使用场景
广搜的搜索方式就适合于解决两个点之间的最短路径问题。因为广搜是从起点出发以起始点为中心一圈一圈进行搜索一旦遇到终点记录之前走过的节点就是一条最短路Java代码实现
邻接矩阵表示的图
public class BFSTraversalAdjacencyMatrix {private int[][] adjacencyMatrix; // 邻接矩阵存储图的结构private boolean[] visited; // 标记节点是否被访问过public BFSTraversalAdjacencyMatrix(int numNodes) {this.adjacencyMatrix new int[numNodes][numNodes]; // 初始化邻接矩阵this.visited new boolean[numNodes]; // 初始化visited数组}// 添加边到邻接矩阵public void addEdge(int source, int destination) {adjacencyMatrix[source][destination] 1;}// 广度优先搜索遍历public void bfsTraversal(int startNode) {QueueInteger queue new LinkedList(); // 创建一个队列用于BFS遍历queue.add(startNode); // 将起始节点加入队列visited[startNode] true; // 标记起始节点为已访问while (!queue.isEmpty()) {int currentNode queue.poll(); // 出队列一个节点System.out.print(currentNode ); // 输出当前节点for (int i 0; i adjacencyMatrix.length; i) {if (adjacencyMatrix[currentNode][i] 1 !visited[i]) {queue.add(i); // 将未访问的邻居节点加入队列visited[i] true; // 标记邻居节点为已访问}}}}
}邻接表表示的图
public class BFSTraversalAdjacencyList {private LinkedListInteger[] adjacencyList; // 邻接表存储图的结构private boolean[] visited; // 标记节点是否被访问过public BFSTraversalAdjacencyList(int numNodes) {// 初始化邻接表this.adjacencyList new LinkedList[numNodes];for (int i 0; i numNodes; i) {adjacencyList[i] new LinkedListInteger();}// 初始化visited数组this.visited new boolean[numNodes];}// 添加边到邻接表public void addEdge(int source, int destination) {adjacencyList[source].add(destination);}// 广度优先搜索遍历public void bfsTraversal(int startNode) {QueueInteger queue new LinkedList(); // 创建一个队列用于BFS遍历queue.add(startNode); // 将起始节点加入队列visited[startNode] true; // 标记起始节点为已访问while (!queue.isEmpty()) {int currentNode queue.poll(); // 出队列一个节点System.out.print(currentNode ); // 输出当前节点for (int neighbor : adjacencyList[currentNode]) {if (!visited[neighbor]) {queue.add(neighbor); // 将未访问的邻居节点加入队列visited[neighbor] true; // 标记邻居节点为已访问}}}}
}
