?作者簡介：熱愛后端語言的大學(xué)生，CSDN內(nèi)容合伙人
?精品專欄：C++面向?qū)ο?/strong>
??系列專欄：算法百煉成神
??前言
本專欄收錄的均為?？途W(wǎng)的算法題目，內(nèi)含鏈表、雙指針、遞歸、動態(tài)規(guī)劃、基本數(shù)據(jù)結(jié)構(gòu)等算法思想的具體運用。?？途W(wǎng)不僅有大量的經(jīng)典算法題目，也有大廠的面試真題，面試、找工作完全可以來這里找機會。此外，網(wǎng)站內(nèi)的編碼主題多樣化，調(diào)試功能可運用性強，可謂是非常注重用戶體驗。這么好的免費刷題網(wǎng)站還不快入手嗎，快去注冊開啟算法百煉成神之路吧！
1、AB13 【模板】拓撲排序
學(xué)會使用鄰接表解決圖論問題，巧妙利用vector容器
題目鏈接：拓樸排序
1.1、解題思路
解決拓撲排序之前要先認識什么是拓撲排序：
對一個有向無環(huán)圖(Directed Acyclic Graph簡稱
DAG)圖G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊<u,v>∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。
解決步驟：
- 使用鄰接表將頂點聯(lián)系起來，輔助數(shù)組
inDegree表示每個頂點的入度。 - 借助隊列和計數(shù)器變量來判斷該有向圖是否有環(huán)：
- 將入度為零的頂點入隊(也就是拓撲圖第一個頂點)
- 取隊首，遍歷與之相鄰的頂點，若該頂點入度減一后為零就將其入隊
- 只要隊列非空就循環(huán)操作，計算器循環(huán)加一，與頂點數(shù)比較是否相等
- 本題末尾也不能輸出空格，因此輸出拓撲序列時要加限制條件
1.2、代碼實現(xiàn)與注釋
本題源碼：
#include<iostream>
#include<vector>
#include<queue>
#define M 200001
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> adjList[M]; // 模擬鄰接表
int inDegree[M] = { 0 };// 記錄每個頂點的入度
int a, b;
for (int i = 0; i < m; i++) {
cin >> a >> b;
adjList[a].push_back(b);
inDegree[b]++;
}
queue<int> que; // 將初始入度為零的頂點入隊
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0)
que.push(i);
}
int cnt = 0; // 用來計數(shù)，判斷改圖是否有環(huán)
vector<int> res; // 用來輸出頂點序列
while (!que.empty()) {
int u = que.front();
que.pop();
res.push_back(u);
for (int i = 0; i < adjList[u].size(); i++) { // 遍歷u的相鄰頂點
int v = adjList[u][i];
if (--inDegree[v] == 0)
que.push(v);
}
cnt++;
}
// 若計數(shù)器與頂點數(shù)相同則圖無環(huán)，存在拓撲排序
if (cnt == n) {
for (int i = 0; i < res.size(); i++) {
cout << res[i];
// 限制輸出空格的條件
if (i != res.size() - 1) {
cout << " ";
}
}
} else {
cout << -1;
}
return 0;
}
重要注釋：
-
adjList數(shù)組是vector類型的，用來模擬鄰接表- 使用每個元素為一個數(shù)組的
vector容器模擬鄰接表進行建圖 -
vector[a]所對應(yīng)的數(shù)組中存儲著該頂點所指向的其他頂點 -
inDegree數(shù)組代表每一個頂點的入度情況
- 使用每個元素為一個數(shù)組的
- 使用一個隊列，初始時將所有入度為0的頂點全部入隊，之后采用
BFS的思想：- 依次取出隊頭元素并存入結(jié)果數(shù)組中，然后在鄰接表中遍歷該隊頭元素所指向的其他頂點
- 將這些頂點的入度全部減一，若減一后某頂點的入度變?yōu)?，則將該頂點進行入隊操作，
重復(fù)此步驟直至隊列為空為止。
- 設(shè)置一個用于判斷圖中是否存在環(huán)（是否可以得到拓撲序列）的計數(shù)器，在彈出隊頭元素后要將計數(shù)器加一，最后隊列為空后，若計數(shù)器的值與頂點數(shù)相同，則說明圖不存在環(huán)，可以得到拓撲序列。
2、AB14 最小生成樹
題目鏈接：最小生成樹
2.1、解題思路
本題要求在最小花費下將 n 戶人家連接起來，很顯然是最小生成樹的問題，我采用prim算法：
- 將二維數(shù)組
cost按權(quán)升序排序，那么cost[0][2]就是最小的一個權(quán)值 - 將連接這條邊的兩個頂點放入
unordered_set容器：-
unordered_set容器的元素是無序的，可以用來給頂點去重 - 內(nèi)置的
find方法也很好用
-
- 接下來遍歷
cost二維數(shù)組，直到所有頂點全部放入容器中，遍歷結(jié)束 - 將遍歷中權(quán)值的和返回，程序結(jié)束
2.2、代碼實現(xiàn)與注釋
本題源碼：
class Solution {
public:
/**
* 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
*
* 返回最小的花費代價使得這n戶人家連接起來
* @param n int n戶人家的村莊
* @param m int m條路
* @param cost intvector<vector<>> 一維3個參數(shù)，表示連接1個村莊到另外1個村莊的花費的代價
* @return int
*/
// 自定義排序規(guī)則：按權(quán)遞增
static bool cmp(vector<int>& x, vector<int>& y) {
return x[2] < y[2];
}
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
unordered_set<int> points; // 記錄不重復(fù)的點
int res = 0;
sort(cost.begin(), cost.end(), cmp);
res += cost[0][2]; // 此時res 為最小權(quán)值
// 將最小邊加入
points.insert(cost[0][0]);
points.insert(cost[0][1]);
while (1) {
if (points.size() == n)
break; // 所有的點連同后退出循環(huán)
// 遍歷剩余的邊
for (auto it = cost.begin(); it != cost.end(); it++) {
// 如果邊僅有一個點在集合內(nèi)就加入
if ((points.find((*it)[0]) != points.end() &&
points.find((*it)[1]) == points.end()) ||
(points.find((*it)[1]) != points.end() &&
points.find((*it)[0]) == points.end()))
{
res += (*it)[2];
points.insert((*it)[0]);
points.insert((*it)[1]);
cost.erase(it); // 刪除該邊
break;
}
}
}
return res;
}
};
重要注釋：
-
cmp是自定義的一個按權(quán)遞增的排序函數(shù)，配合sort函數(shù)來將cost排序- 相關(guān)知識點可以參考我的博文：自定義排序規(guī)則
-
auto關(guān)鍵字可以自動推導(dǎo)表達式類型，在這里就相當于vector<vector<int>>::iterator -
if的條件很長，但其實就是將有且僅有一個頂點在points中的邊找到：- 獲取該邊的權(quán)值并求和，將另一頂點插入到
points中 - 將該邊刪除，重新遍歷
cost，直到全部頂點被插入到points中
- 獲取該邊的權(quán)值并求和，將另一頂點插入到
- 最終的
res就是該題的結(jié)果，即最小花費。
3、AB15 單源最短路2
題目鏈接：單源最短路2
3.1、解題思路
使用Dijkstra算法（即不斷從未處理集合中找當前距離源點最近的頂點以添加到已處理集合中，直至未處理集合為空的算法思想）
- 對于無向圖，采用鄰接矩陣表示點與點的連接關(guān)系以及距離
- 使用數(shù)組
dist記錄每個頂點與源點的距離：- 本題中就是記錄頂點1與其他頂點的距離
- 用一個布爾類型的數(shù)組記錄頂點的處理情況：
- 初始狀態(tài)全部設(shè)為
false，一經(jīng)處理就設(shè)為true
- 初始狀態(tài)全部設(shè)為
- 最終
dist[n]就是頂點n到源點的最短距離
3.2、代碼實現(xiàn)與注釋
本題源碼
#include<iostream>
#include<climits> // 使用INT_MAX所需要引入的頭文件
using namespace std;
const int N = 5000; // 注意題干，圖的點數(shù)是固定值5000
int main() {
int G[N + 1][N + 1]; // 用于模擬鄰接矩陣進行建圖
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
G[i][j] = INT_MAX; // 先將鄰接矩陣全部初始化為無窮大
}
}
int n, m;
cin >> n >> m;
int u, v, w;
for (int i = 1; i <= m; i++) {
cin >> u >> v >> w;
G[u][v] = w;
G[v][u] = w; // 需要關(guān)于主對角線對稱，因此兩邊都需要存儲
}
int dist[N + 1]; // 用于存儲每個頂點當前與源點的最短距離
bool flag[N + 1]; // 用于記錄每個頂點是否已經(jīng)完成與源點最短距離的計算處理
for (int i = 1; i <= N; i++) {
dist[i] = G[1][i]; // 初始設(shè)置為鄰接矩陣中源點所在 行 的權(quán)值
flag[i] = false;
}
dist[1] = 0;
flag[1] = true; // 將源點加入已處理集合
for (int i = 2; i <= N; i++) {
int tmp = INT_MAX, index = 1;
for (int j = 1; j <= N; j++) { // 遍歷尋找與源點的最短距離
if (flag[j] == false && dist[j] < tmp) {
tmp = dist[j];
index = j;
}
}
if (index != 1) {
flag[index] = true; // 找到后將其加入已處理集合
}
for (int j = 2; j <= N; j++) {
if (flag[j] == false && G[index][j] != INT_MAX) {
if (G[index][j] + dist[index] < dist[j]) {
dist[j] = G[index][j] + dist[index]; // 更新最短路徑
}
}
}
}
if (dist[n] != INT_MAX) {
cout << dist[n];
} else {
cout << -1;
}
return 0;
}
重要注釋：文章來源：http://www.zghlxwxcb.cn/news/detail-780658.html
- 二維數(shù)組
G是具化出的鄰接矩陣，將元素值全部初始化為無窮大：INT_MAX -
u,v記錄兩個頂點，w記錄頂點間距離，全部存入G中 -
dist數(shù)組用來存放各頂點到源點的距離，flag數(shù)組記錄頂點是否被處理過 -
index代表著與源點連接且距離最短的未經(jīng)處理的頂點：- 隨后將該頂點設(shè)為已處理
- 然后
index尋找與之相連且未經(jīng)處理的頂點：-
dist[index]是index到源點的最短距離，如果加上與之相連的頂點的距離較小，那么就更新最短路徑
-
- 最終的
dist數(shù)組的值就是各點到源點的最短路徑
當自己動手去做的時候才發(fā)現(xiàn)原來我以為的難題，不過如此，將這份自信傳達給大家，奮斗下去！文章來源地址http://www.zghlxwxcb.cn/news/detail-780658.html
到了這里，關(guān)于【算法入門&圖論】【模板】拓撲排序|【模板】單源最短路2 |最小生成樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
