网站定制开发上海,网站返利程序,网站建设技术招聘,新能源汽车价格一览表这里写目录标题 基于深度优先搜索的无向图遍历算法流程图Python实现Java实现 基于深度优先搜索的有向图遍历Python实现 基于深度优先搜索的无向图遍历
使用深度优先搜索遍历无向图#xff0c;将无向图用邻接表存储#xff1a;
算法流程图
初始化起点 source#xff0c;当… 这里写目录标题 基于深度优先搜索的无向图遍历算法流程图Python实现Java实现 基于深度优先搜索的有向图遍历Python实现 基于深度优先搜索的无向图遍历
使用深度优先搜索遍历无向图将无向图用邻接表存储
算法流程图
初始化起点 source当前节点v为起点终点 target路径path为空路径集合 paths 为空将当前节点v添加到 path 中判断当前节点v是否为终点是转step4否转step5保存 path 至 paths 中转step7获取当前节点的所有邻接点用集合N表示遍历N若 N_i 不在 path 中令vN_i 转step2若N_i 在path 中i 1。删除 path 中最后一个节点,令vpath中最后一个节点转step5以上步骤遍历了所有每一个点的邻接点算法结束输出起点到终点的所有路径paths
Python实现
from typing import Listdef dfs(adjacent_list, source, target)::param adjacent_list: 邻接表:param source: 起点:param target: 终点:return: 起点-终点的所有路径def dfs_helper(adjacent_list, source, current_node, target):path.append(current_node) # 压栈if current_node target:paths.append(path.copy())else:neighbors adjacent_list[current_node]for neighbor in neighbors:if neighbor not in path:dfs_helper(adjacent_list, source, neighbor, target)path.pop() # 弹栈paths []path []dfs_helper(adjacent_list, source, source, target)return pathsif __name__ __main__:# 邻接表adjacent_list {1: [2, 3],2: [1, 4, 5],3: [1, 4, 7],4: [2, 3, 5, 6, 7],5: [2, 4, 6],6: [4, 5],7: [3, 4]}# 深搜paths: List[List] dfs(adjacent_list, 1, 6)[print(path) for path in paths]
Java实现
package org.example;import java.util.*;public class DepthFirstSearch {// ListInteger path new ArrayList();StackInteger path new Stack();ListListInteger paths new ArrayList();void dfs(MapInteger, ListInteger adjacent_list, int source, int current_node, int target) {path.push(current_node);if (current_node target) {paths.add(new ArrayList(path));path.remove(path.size() - 1);} else {ListInteger neighbors adjacent_list.get(current_node);for (Integer neighbor : neighbors) {if (!path.contains(neighbor)) {dfs(adjacent_list, source, neighbor, target);}}path.pop();}}public static void main(String[] args) {MapInteger, ListInteger adjacent_list new HashMap();adjacent_list.put(1, Arrays.asList(2, 3));adjacent_list.put(2, Arrays.asList(1, 4, 5));adjacent_list.put(3, Arrays.asList(1, 4, 7));adjacent_list.put(4, Arrays.asList(2, 3, 5, 6, 7));adjacent_list.put(5, Arrays.asList(2, 4, 6));adjacent_list.put(6, Arrays.asList(4, 5));adjacent_list.put(7, Arrays.asList(3, 4));System.out.println(adjacent_list);DepthFirstSearch dfs new DepthFirstSearch();dfs.dfs(adjacent_list, 1, 1, 6);for (ListInteger path : dfs.paths) {System.out.println(path);}}
}
基于深度优先搜索的有向图遍历
和无向图遍历一样建立邻接矩阵即可。
Python实现
from typing import List, Tuple, Any, Dict
import networkx
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from typing import Listdef paint_topological_graph(nodes,edges: List[Tuple],coordinates: Dict[Any, Tuple] None,directedFalse):print(nodes)print(edges)print(coordinates)graph networkx.DiGraph() if directed else networkx.Graph() # 全连通 有向图graph.add_nodes_from(nodes)graph.add_edges_from(edges)networkx.draw(graph, poscoordinates, with_labelsTrue, node_colorred, )plt.show()print(networkx.has_path(graph, 1, 12))return graphdef dfs(adjacent_list, source, target)::param adjacent_list: 邻接表:param source: 起点:param target: 终点:return: 起点-终点的所有路径def dfs_helper(adjacent_list, source, current_node, target):path.append(current_node)if current_node target:paths.append(path.copy())path.pop()else:neighbors adjacent_list[current_node]for neighbor in neighbors:if neighbor not in path:dfs_helper(adjacent_list, source, neighbor, target)path.pop()paths []path []dfs_helper(adjacent_list, source, source, target)return pathsif __name__ __main__:# 点坐标node_coord {1: (1, 0), 2: (1, 3), 3: (2.5, 3), 4: (2, 2.5), 5: (3, 2), 6: (2, 1.5), 7: (3, 0), 8: (6, 0), 9: (5.5, 2),10: (5.5, 3), 11: (6, 4), 12: (0, 0), 13: (0, 1), 14: (5.5, 0.5), 15: (4.5, 0.5), 16: (5, 5),}edges [(13, 12), (1, 2), (2, 4), (2, 3), (4, 3), (4, 5), (1, 6), (1, 7), (6, 7), (6, 5), (7, 8), (5, 9), (5, 10),(3, 11), (11, 10), (9, 8), (10, 9), (8, 11), (14, 15), (8, 14), (12, 1), (11, 16),]# 画图paint_topological_graph(nodesnp.arange(1, 17, 1),edgesedges,directedTrue,coordinatesnode_coord)# 邻接表adjacent_list {1: [2, 6, 7],2: [3, 4],3: [11],4: [3, 5],5: [9, 10],6: [5, 7],7: [8],8: [11, 14],9: [8],10: [9],11: [10, 16],12: [1],13: [12],14: [15],15: [],16: [],}# 深搜paths: List[List] dfs(adjacent_list, 1, 11)[print(path) for path in paths]
