图模型

输入/输出

  1. 5 5 #几个点 几条边
  2. 1 2 #具体边的连接
  3. 1 3
  4. 1 5
  5. 2 4
  6. 3 5
  7. -----
  8. 从1进行深度遍历的结果：1-2-4-3-5
import java.util.*;
class Solution{
    boolean[] f;
    int sum = 0;
    public void solve(int[][] graph, int N, int b){
        f = new boolean[N + 1];
        f[b] = true;
        System.out.print(b+" ");
        sum++;
        dfs(graph, N, b);
    }
    public void dfs(int[][] graph, int N, int cur){
        if(sum == N) return;
        for(int i = 0; i <= N; i++){
            if(graph[cur][i] == 1 && f[i] == false){
                f[i] = true;
                System.out.print(i+" ");
                sum++;
                dfs(graph, N, i);
            }
        }
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        int[][] graph = new int[N + 1][N + 1];
        int M = cin.nextInt();
        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= N; j++){
                if(i == j) graph[i][j] = 0;
                else graph[i][j] = Integer.MAX_VALUE;
            }
        }
        for(int i = 0; i < M; i++){
            int a = cin.nextInt();
            int b = cin.nextInt();
            graph[a][b] = 1;
            graph[b][a] = 1;
        }
        new Solution().solve(graph, N, 1);
    }
}

利用图的深度遍历，求两点间的最短路

图模型

输入输出

#输入
5 8 1 5 ##5个点，7条边，想从点1到点4
1 2 2  
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3
#输出
9

import java.util.*;
class Solution{
    int res = Integer.MAX_VALUE;
    boolean[] f;
    int end;
    public int solve(int[][] graph, int begin, int end){
        f = new boolean[graph.length];
        //不加this，end始终为0
        this.end = end;
        f[begin] = true;
        dfs(graph, begin, 0);
        return res;
    }
    public void dfs(int[][] graph, int cur, int dis){
        //System.out.println(cur +" " +end+" " + dis);
        if(cur == end){
            res = Math.min(res, dis);
            return;
        }
        if(dis >= res) return;
        for(int i = 0; i < graph.length; i++){
            if(graph[cur][i] != Integer.MAX_VALUE && f[i] == false){

                f[i] = true;
                dfs(graph, i, dis + graph[cur][i]);
                f[i] = false;
            }
        }
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        int[][] graph = new int[N + 1][N + 1];
        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= N; j++){
                if(i == j) graph[i][j] = 0;
                else graph[i][j] = Integer.MAX_VALUE;
            }
        }
        int m = cin.nextInt();
        int begin = cin.nextInt();
        int end = cin.nextInt();
        for(int i = 0; i < m; i++){
            int a = cin.nextInt();
            int b = cin.nextInt();
            int c = cin.nextInt();
            graph[a][b] = c;
        }
        System.out.print(new Solution().solve(graph, begin, end));
    }
}

图模型

输入输出

#输入
5 7 1 4 #5个点，7条边，想从点1到点4
1 2
1 3
2 3
2 4
3 4
3 5
4 5
#输出
7

import java.util.*;
class Solution{
    int res = Integer.MAX_VALUE;
    boolean[] f;
    int end;
    public int solve(int[][] graph, int begin, int end){
        f = new boolean[graph.length];
        //不加this，end始终为0
        this.end = end;
        f[begin] = true;
        dfs(graph, begin, 0);
        return res;
    }
    public void dfs(int[][] graph, int cur, int dis){
        //System.out.println(cur +" " +end+" " + dis);
        if(cur == end){
            res = Math.min(res, dis);
            return;
        }
        if(dis >= res) return;
        for(int i = 0; i < graph.length; i++){
            if(graph[cur][i] != Integer.MAX_VALUE && f[i] == false){

                f[i] = true;
                dfs(graph, i, dis + graph[cur][i]);
                f[i] = false;
            }
        }
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int N = cin.nextInt();
        int[][] graph = new int[N + 1][N + 1];
        for(int i = 0; i <= N; i++){
            for(int j = 0; j <= N; j++){
                if(i == j) graph[i][j] = 0;
                else graph[i][j] = Integer.MAX_VALUE;
            }
        }
        int m = cin.nextInt();
        int begin = cin.nextInt();
        int end = cin.nextInt();
        for(int i = 0; i < m; i++){
            int a = cin.nextInt();
            int b = cin.nextInt();
            graph[a][b] = 1;
            graph[b][a] = 1;
        }
        System.out.print(new Solution().solve(graph, begin, end));
    }
}