第十一章：圖論part01
圖論理論基礎(chǔ)
注意
- 圖的構(gòu)造：鄰接矩陣和鄰接表
深搜理論基礎(chǔ)
- 注意一下回溯的過程播掷，使用遞歸最方便。
- 深搜三部曲：
- 確認(rèn)遞歸函數(shù)劝篷，參數(shù)
一般情況肃续，深搜需要 二維數(shù)組數(shù)組結(jié)構(gòu)保存所有路徑肴颊，需要一維數(shù)組保存單一路徑，這種保存結(jié)果的數(shù)組，我們可以定義一個(gè)全局變量未檩，避免讓我們的函數(shù)參數(shù)過多蕾总。
例如這樣：
List<List<Integer>> result = new ArrayList<>(); // 保存符合條件的所有路徑
List<Integer> path = new ArrayList<>(); // 起點(diǎn)到終點(diǎn)的路徑
void dfs(int[][] graph, int currentNode) {}
- 確認(rèn)終止條件
if (終止條件) {
存放結(jié)果;
return;
}
另外粥航，其實(shí)很多dfs寫法，沒有寫終止條件生百，其實(shí)終止條件寫在了递雀， 下面dfs遞歸的邏輯里了，也就是不符合條件蚀浆，直接不會向下遞歸缀程。
- 處理目前搜索節(jié)點(diǎn)出發(fā)的路徑
一般這里就是一個(gè)for循環(huán)的操作，去遍歷 目前搜索節(jié)點(diǎn) 所能到的所有節(jié)點(diǎn)市俊。
for (選擇：本節(jié)點(diǎn)所連接的其他節(jié)點(diǎn)) {
處理節(jié)點(diǎn);
dfs(圖杨凑，選擇的節(jié)點(diǎn)); // 遞歸
回溯，撤銷處理結(jié)果
}
98. 所有可達(dá)路徑
圖的儲存
鄰接矩陣
鄰接矩陣 使用 二維數(shù)組來表示圖結(jié)構(gòu)摆昧。 鄰接矩陣是從節(jié)點(diǎn)的角度來表示圖撩满，有多少節(jié)點(diǎn)就申請多大的二維數(shù)組。
本題我們會有n 個(gè)節(jié)點(diǎn)据忘，因?yàn)楣?jié)點(diǎn)標(biāo)號是從1開始的鹦牛，為了節(jié)點(diǎn)標(biāo)號和下標(biāo)對齊，我們申請 n + 1 * n + 1 這么大的二維數(shù)組勇吊。
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 節(jié)點(diǎn)數(shù)
int[][] graph = new int[n + 1][n + 1]; // 鄰接矩陣曼追，初始化為0
輸入m個(gè)邊，構(gòu)造方式如下：
int m = scanner.nextInt(); // 邊數(shù)
while (m-- > 0) {
int s = scanner.nextInt();
int t = scanner.nextInt();
graph[s][t] = 1; // 表示節(jié)點(diǎn)s指向節(jié)點(diǎn)t
}
鄰接表
List<List<Integer>> graph = new ArrayList<>(n + 1); // 初始化鄰接表
for (int i = 0; i <= n; i++) {
graph.add(new LinkedList<>());
}
while (m-- > 0) {
int s = scanner.nextInt();
int t = scanner.nextInt();
graph.get(s).add(t); // 表示s -> t是相連的
}
本題我們使用鄰接表 或者 鄰接矩陣都可以汉规，因?yàn)楹笈_數(shù)據(jù)并沒有對圖的大小以及稠密度做很大的區(qū)分礼殊。
深搜三部曲
- 確認(rèn)遞歸函數(shù)驹吮，參數(shù)
首先我們dfs函數(shù)一定要存一個(gè)圖，用來遍歷的晶伦，需要存一個(gè)目前我們遍歷的節(jié)點(diǎn)碟狞，定義為x。
還需要存一個(gè)n婚陪，表示終點(diǎn)族沃，我們遍歷的時(shí)候，用來判斷當(dāng) x==n 時(shí)候 標(biāo)明找到了終點(diǎn)泌参。
（其實(shí)在遞歸函數(shù)的參數(shù) 不容易一開始就確定了脆淹，一般是在寫函數(shù)體的時(shí)候發(fā)現(xiàn)缺什么，參加就補(bǔ)什么）
至于 單一路徑 和 路徑集合 可以放在全局變量
List<List<Integer>> result = new ArrayList<>(); // 收集符合條件的路徑
List<Integer> path = new ArrayList<>(); // 1節(jié)點(diǎn)到終點(diǎn)的路徑
// x：目前遍歷的節(jié)點(diǎn)
// graph：存當(dāng)前的圖
// n：終點(diǎn)
void dfs(List<List<Integer>> graph, int x, int n) {}
- 確認(rèn)終止條件
什么時(shí)候我們就找到一條路徑了沽一？
當(dāng)目前遍歷的節(jié)點(diǎn) 為 最后一個(gè)節(jié)點(diǎn) n 的時(shí)候 就找到了一條 從出發(fā)點(diǎn)到終止點(diǎn)的路徑盖溺。
if (x == n) { // 找到符合條件的一條路徑
result.add(new ArrayList<>(path));
return;
}
- 處理目前搜索節(jié)點(diǎn)出發(fā)的路徑
接下來是走 當(dāng)前遍歷節(jié)點(diǎn)x的下一個(gè)節(jié)點(diǎn)。
首先是要找到 x節(jié)點(diǎn)指向了哪些節(jié)點(diǎn)呢铣缠？ 遍歷方式是這樣的：
for (int i : graph.get(x))
接下來就是將 選中的x所指向的節(jié)點(diǎn)烘嘱，加入到 單一路徑來。
在使用鄰接矩陣表示圖的結(jié)構(gòu)時(shí)蝗蛙，graph[x][i]表示從節(jié)點(diǎn) x 到節(jié)點(diǎn) i 是否存在一條邊蝇庭。鄰接矩陣是一種二維數(shù)組，假設(shè)有 n 個(gè)節(jié)點(diǎn)歼郭，那么這個(gè)矩陣的大小就是 n x n遗契。矩陣中的每個(gè)元素 graph[x][i] 的含義如下：
- 如果 graph[x][i] 為 1，表示節(jié)點(diǎn) x 和節(jié)點(diǎn) i 之間存在一條邊。
- 如果 graph[x][i] 為 0，表示節(jié)點(diǎn) x 和節(jié)點(diǎn) i 之間不存在一條邊陷虎。
if (graph[x][i] == 1) { // 找到 x鏈接的節(jié)點(diǎn)
path.add(i); // 遍歷到的節(jié)點(diǎn)加入到路徑中來
}
進(jìn)入下一層遞歸
dfs(graph, i, n); // 進(jìn)入下一層遞歸
最后就是回溯的過程，撤銷本次添加節(jié)點(diǎn)的操作鲫竞。
path.remove(path.size() - 1);
該過程整體代碼：
for (int i = 1; i <= n; i++) { // 遍歷節(jié)點(diǎn)x鏈接的所有節(jié)點(diǎn)
if (graph[x][i] == 1) { // 找到 x鏈接的節(jié)點(diǎn)
path.add(i); // 遍歷到的節(jié)點(diǎn)加入到路徑中來
dfs(graph, i, n); // 進(jìn)入下一層遞歸
path.remove(path.size() - 1); // 回溯，撤銷本節(jié)點(diǎn)
}
}
打印結(jié)果
例如示例輸出是：
[1 3 5]而不是 [1 3 5 ]
即 5 的后面沒有空格逼蒙！
if (result.size() == 0) {
System.out.println(-1);
} else {
for (List<Integer> pa : result) {
for (int i = 0; i < pa.size() - 1; i++) {
System.out.print(pa.get(i) + " ");
}
System.out.println(pa.get(pa.size() - 1));
}
}
}
鄰接矩陣寫法
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main{
static List<List<Integer>> result = new ArrayList<>();
static List<Integer> path = new ArrayList<>();
public static void dfs(int[][] graph, int x, int n){
if(x == n){
result.add(new ArrayList<>(path));
return;
}
for(int i = 1; i <= n; i++){
if(graph[x][i] == 1){
path.add(i);
dfs(graph, i, n);
path.remove(path.size() - 1);
}
}
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] graph = new int[n + 1][n + 1];
for(int i = 0; i < m; i++){
int s = sc.nextInt();
int t = sc.nextInt();;
graph[s][t] = 1;
}
path.add(1); // 無論什么路徑已經(jīng)是從1節(jié)點(diǎn)出發(fā)
dfs(graph, 1, n); // 開始遍歷
// 輸出結(jié)果
if(result.size() == 0) System.out.println(-1);
for(List<Integer> pa : result){
for(int i = 0; i < pa.size() - 1; i++){
System.out.print(pa.get(i) + " ");
}
System.out.println(pa.get(pa.size() - 1));
}
}
}
鄰接表寫法
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main{
static List<List<Integer>> result = new ArrayList<>();
static List<Integer> path = new ArrayList<>();
public static void dfs(List<LinkedList<Integer>> graph, int x, int n){
if(x == n){
result.add(new ArrayList<>(path));
return;
}
for(int i : graph.get(x)){
path.add(i); // 遍歷到的節(jié)點(diǎn)加入到路徑中來
dfs(graph, i, n); // 進(jìn)入下一層遞歸
path.remove(path.size() - 1); // 回溯从绘，撤銷本節(jié)點(diǎn)
}
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
List<LinkedList<Integer>> graph = new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
graph.add(new LinkedList<>());
}
while(m-- > 0){
int s = sc.nextInt();
int t = sc.nextInt();
graph.get(s).add(t);
}
path.add(1); // 無論什么路徑已經(jīng)是從1節(jié)點(diǎn)出發(fā)
dfs(graph, 1, n); // 開始遍歷
// 輸出結(jié)果
if(result.isEmpty()) System.out.println(-1);
for(List<Integer> pa : result){
for(int i = 0; i < pa.size() - 1; i++){
System.out.print(pa.get(i) + " ");
}
System.out.println(pa.get(pa.size() - 1));
}
}
}
廣搜理論基礎(chǔ)
使用場景：適合于解決兩個(gè)點(diǎn)之間的最短路徑問題。因?yàn)閺V搜是從起點(diǎn)出發(fā)是牢，以起始點(diǎn)為中心一圈一圈進(jìn)行搜索僵井，一旦遇到終點(diǎn)，記錄之前走過的節(jié)點(diǎn)就是一條最短路驳棱。
也有一些問題是廣搜 和 深搜都可以解決的批什，例如島嶼問題，這類問題的特征就是不涉及具體的遍歷方式社搅，只要能把相鄰且相同屬性的節(jié)點(diǎn)標(biāo)記上就行驻债。
代碼框架
其實(shí)乳规，我們僅僅需要一個(gè)容器，能保存我們要遍歷過的元素就可以合呐，那么用隊(duì)列暮的，還是用棧，甚至用數(shù)組淌实，都是可以的冻辩。
用隊(duì)列的話，就是保證每一圈都是一個(gè)方向去轉(zhuǎn)翩伪，例如統(tǒng)一順時(shí)針或者逆時(shí)針微猖。
因?yàn)殛?duì)列是先進(jìn)先出谈息，加入元素和彈出元素的順序是沒有改變的缘屹。
如果用棧的話，就是第一圈順時(shí)針遍歷侠仇，第二圈逆時(shí)針遍歷轻姿，第三圈有順時(shí)針遍歷。
因?yàn)闂Ｊ窍冗M(jìn)后出逻炊，加入元素和彈出元素的順序改變了互亮。
那么廣搜需要注意 轉(zhuǎn)圈搜索的順序嗎？ 不需要余素！
模板代碼
以這個(gè)圖為例
image.png
import java.util.LinkedList;
import java.util.Queue;
public class BFS {
static int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 表示四個(gè)方向
public static void bfs(char[][] grid, boolean[][] visited, int x, int y) {
Queue<int[]> queue = new LinkedList<>(); // 定義隊(duì)列
queue.offer(new int[]{x, y}); // 起始節(jié)點(diǎn)加入隊(duì)列
visited[x][y] = true; // 只要加入隊(duì)列豹休，立刻標(biāo)記為訪問過的節(jié)點(diǎn)
while (!queue.isEmpty()) { // 開始遍歷隊(duì)列里的元素
int[] cur = queue.poll(); // 從隊(duì)列取元素
int curx = cur[0];
int cury = cur[1]; // 當(dāng)前節(jié)點(diǎn)坐標(biāo)
for (int i = 0; i < 4; i++) { // 開始向當(dāng)前節(jié)點(diǎn)的四個(gè)方向左右上下去遍歷
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1]; // 獲取周邊四個(gè)方向的坐標(biāo)
// 坐標(biāo)越界了，直接跳過
if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;
// 如果節(jié)點(diǎn)沒被訪問過
if (!visited[nextx][nexty]) {
queue.offer(new int[]{nextx, nexty}); // 隊(duì)列添加該節(jié)點(diǎn)為下一輪要遍歷的節(jié)點(diǎn)
visited[nextx][nexty] = true; // 只要加入隊(duì)列立刻標(biāo)記桨吊，避免重復(fù)訪問
}
}
}
}
public static void main(String[] args) {
char[][] grid = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}
};
boolean[][] visited = new boolean[grid.length][grid[0].length];
bfs(grid, visited, 0, 0);
// 輸出 visited 數(shù)組查看結(jié)果
for (int i = 0; i < visited.length; i++) {
for (int j = 0; j < visited[0].length; j++) {
System.out.print(visited[i][j] ? "T " : "F ");
}
System.out.println();
}
}
}
