图(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 # 克鲁斯卡尔 # 迪杰斯特拉