图

发布： 分类： 评论： 阅读：

图，最多的遇到的面试题就是深度优先搜索和广度优先搜索，这也是最基础的。
图的一个最重要的点：设置一个 visit[] 数组，用来表示图中的每个节点是否已经被访问过。

图的深度优先搜索和广度优先搜索

  • 图分为邻接矩阵和邻接表。

  • 邻接矩阵：

  • 邻接表：

  • 不管是 DFS 还是 BFS，都要设置一个 visit 变量，表示当前 node 是否已经被访问过，使用递归遍历所有的节点。

深度优先搜索 DFS

  • 访问顶点v；
  • 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
  • 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
1
2
3
4
5
6
7
8
9
10
public void DFS(int[][] graph, int[] visit, int node) {
    visit[node] = 1;
    // 访问node节点要执行的操作
    System.out.println(node);
    //DFS遍历其他节点
    for(int i=0;i<graph[node].length;i++) {
        if(graph[node][i]==1 && visit[i]==0)
            DFS(graph, visit, i);
    }
}

广度优先搜索 BFS

  • 首先将根节点放入队列中;
  • 从队列中取出第一个节点, 将它所有尚未检验过的直接子节点加入队列中;
  • 若队列为空，表示整张图都检查过了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void BFS(int[][] graph, int[] visit, int node) {
    visit[node] = 1;
    Queue<Integer> que = new LinkedList();
    que.add(node);
    while(!que.isEmpty()) {
        int new_node = que.poll();
        // 访问node节点要执行的操作
        System.out.println(new_node);
        // 将new_node相连的节点放入队列
        for(int i=0;i<graph[new_node].length;i++) {
            if(graph[new_node][i]==1 && visit[i]==0) {
                visit[i] = 1;
                que.add(i);
            }
        }
    }
}

经典题

leetcode 200. 岛屿的数量

1
2
3
4
5
6
7
Input:
11000
11000
00100
00011

Output: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void islandDFS(char[][] grid, int[][] visit, int i, int j) {
    if(i<0 || i>=grid.length || j<0 || j>=grid[0].length)
        return;
    if(grid[i][j]=='1' && visit[i][j]==0){
        visit[i][j] = 1;
        islandDFS(grid, visit, i, j-1);
        islandDFS(grid, visit, i, j+1);
        islandDFS(grid, visit, i+1, j);
        islandDFS(grid, visit, i-1, j);
    }
}

public int numIslands(char[][] grid) {
    if(grid.length==0)  return 0;
    int number = 0;
    int[][] visit = new int[grid.length][grid[0].length];
    for(int i=0;i<grid.length;i++) {
        for(int j=0;j<grid[0].length;j++) {
            if(grid[i][j]=='1' && visit[i][j]==0) {
                // 把和grid[i][j]相连接的位置都标记为1，记作一块岛屿
                islandDFS(grid, visit, i, j);
                number += 1;
            }
        }
    }
    return number;
}

leetcode 463. 确定岛屿的周长

  • 题目中只有一个岛屿，确定岛屿的周长
  • 就是确定每个1周围有几个0，或者在边界位置。
  • 这道题跟图没什么关系。遍历一遍就行了。
1
2
3
4
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int islandPerimeter(int[][] grid) {
    //从头到尾遍历，查看每个1周围几个0，上下左右。
    int number = 0;
    for(int i=0;i<grid.length;i++) {
        for(int j=0;j<grid[0].length;j++) {
            if(grid[i][j]==1) {
                if(i==0 || grid[i-1][j]==0) number += 1;
                if(j==0 || grid[i][j-1]==0) number += 1;
                if(i==grid.length-1 || grid[i+1][j]==0) number += 1;
                if(j==grid[0].length-1 || grid[i][j+1]==0) number += 1;
            }
        }
    }
    return number;
}

leetcode. 787 从src飞到dst的最小花销

  • 方法一：递归调用，但leetcode会超时。
  • 优化：对于遍历到的结点，首先判断如果当前结点已经访问过了，直接跳过。或者是当前价格out加上到达这个结点需要的价格之和大于结果res的话，那么直接跳过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int min = Integer.MAX_VALUE;
     
public void DFS(int [][] flights, int src, int dst, int K, int v, int[] visit) {
    if(src==dst && v<min) {
        min = v;
        return;
    }
    if(K<0||v>min) return;
    for(int i=0;i<flights.length;i++) {
        if(visit[src]==0 && flights[i][0]==src) {
            visit[src] = 1;
            DFS(flights, flights[i][1], dst, K-1, v+flights[i][2], visit);    
            visit[src] = 0;
        }
    }
}

public int findCheapestPrice(int n, int[][] f, int src, int dst, int K) {
    int[] visit = new int[n];
    DFS(f, src, dst, K, 0, visit);
    if(min == Integer.MAX_VALUE) return -1;
    return min;
}

leetcode 529. 扫雷游戏

  • 题太复杂了。。之后再做。
    1

拓扑排序

图片来源： https://www.cnblogs.com/XMU-hcq/p/6065057.html