图(Map)的表示和图的搜索

图的表示

  • 一般习惯使用邻接表存图
    图的邻接表存储
  • 使用ArrayList来写邻接表
  • 假设需要表示一个有n个节点的图,先创建一个大小为n+1的ArrayList对象数组,然后遍历数组的节点,创建Arraylist对象
  • 添加节点时,使用add方法直接加入,如添加u☞向v的节点graph[u].add(v)
    注意无向图两个方向都要存储
1
2
3
4
5
6
7
8
9
10
   List<Integer>[] graph=new ArrayList[n+1];
for (int i = 0; i < n+1; i++) {
graph[i]=new ArrayList<>();
}
for (int i = 0; i < m; i++) {
u=scan.nextInt();
v=scan.nextInt();
graph[u].add(v);//无向图存储两次
graph[v].add(u);
}

图的DFS

1
2
3
4
5
6
7
8
9
10
11
public static void dfs(int start) {//参数:起始点,删除点,哈希标记集合
if(出口条件) {
//Do Some Thing
return;//递归出口
}
for(int j:graph[start]) {
if(set.contains(j)||/*some condition*/) continue;//该节点已经走过||剪枝条件
set.add(j);
dfs(j, i);
}
}

连通地道危险系数_DFS

克鲁斯卡尔

迪杰斯特拉


图(Map)的表示和图的搜索
https://fireworks258.github.io/2024/05/18/Graph-DFS/
作者
Fireworks
发布于
2024年5月18日
许可协议