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

图的表示

• 一般习惯使用邻接表存图
  
• 使用ArrayList来写邻接表
• 假设需要表示一个有n个节点的图，先创建一个大小为n+1的ArrayList对象数组，然后遍历数组的节点，创建Arraylist对象
• 添加节点时，使用add方法直接加入，如添加u☞向v的节点graph[u].add(v)
  注意无向图两个方向都要存储

   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

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

克鲁斯卡尔

迪杰斯特拉