lapt BlogPostsTagsGallerydemogameLeetCode
力扣算法：搜索与图论
|leetcode

搜索与图论

树和图的遍历

最短路

dijkstra算法

dijkstra 模板

  • 返回值：dis_list：dis_list[i]表示从start点到 i 节点的最短路径
  • 如果 dis_list[i]==INT_MAX 说明没办法从 start 到 i
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
   struct State {
       int id;
       // 到起始点的距离
       int dis=0;
   };
   struct cmp {
       bool operator()(const State &a, const State &b) {
       	// 距离最短的点 放在堆顶
           return a.dis > b.dis;
       }
   };

/**
* - 返回值：dis_list：`dis_list[i]`表示从start点到 i 节点的最短路径
* - 如果 `dis_list[i]==INT_MAX` 说明没办法从 start 到 i
*/
   vector<int> dijkstra(int start, vector<vector<vector<int>>> &graph) {
       vector<int> dis_list(graph.size(), INT_MAX);
       priority_queue<State, vector<State>, cmp> pq;

       // 把起始点添加入优先队列里面
       pq.push({start, 0});
       dis_list[start] = 0;

       while (!pq.empty()) {
           // 取出到起始点距离最小的点
           State cur = pq.top(); pq.pop();
           int cur_id = cur.id;
           int cur_dis = cur.dis;
           // 如果已经有了到这个cur节点更短的路径，那么就不在考虑这条路径了
		// 不能是 cur_dis >= dis_list[cur_id] 因为这样第一个点退出了 0 == dis_list[start]
           if (cur_dis > dis_list[cur_id]) continue;

           for (auto &next: graph[cur_id]) {
               int next_id = next[0];
               int next_dis = next[1] + cur_dis;
               // 如果有更短的路径到达next节点，那么就更新dis_list，并添加进pq中。
               if (next_dis < dis_list[next_id]) {
                   dis_list[next_id] = next_dis;
                   pq.push({next_id, next_dis});
               }
           }
       }
       // 最终的dis_list 保存着起始点start到所有点的最短路径，如果是INT_MAX那就说明这个节点到达不了。
       return dis_list;
   }

堆优化：
使用优先队列，主要是为了效率上的优化，每次取出的点是distFromStart最小的，这样算法较之前更容易提前return

并查集

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
28
29
30
31
   int *parent;	// 存放每个节点的根节点
   vector<int> parent_n;	// 存放每个根节点一共联结了几个节点

// 找到x的根节点
   int find(int x) {
       if (parent[x] != x) {
           parent[x] = find(parent[x]);
       }
       return parent[x];
   }
// 合并两个节点
   void merge(int a, int b) {
       int root_a = find(a);
       int root_b = find(b);

       if (root_a != root_b) {
           parent[root_a] = root_b;
           parent_n[root_b] += parent_n[root_a];
           parent_n[root_a] = 1;
       }
   }

//// 在主函数中：
parent = new int[n];
parent_n.resize(n, 1);
// 初始化parent数组，每个节点的根节点是自己，每个节点都互不相通
   for (int i = 0; i<n; i++) {
       parent[i] = i;
   }
// ...
merge(a, b);

逆向并查集：有一些题需要删除掉并查集中的边。并查集建立了之后是没办法删除边的，这个时候可以是把需要删除的边一次性全删除，然后逐个恢复，建立链接。

leetcode