代码随想录算法训练营第五十八天 | 图论part08

在这一题中，只需要输出一种方法。使用BFS的方法，找到入度为0的节点，将其从树中删去，重复上述步骤，直到没有入度为0的节点。如果此时没有删除所有的节点，表明这个有向图有环，输出-1.否则，正常输出。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <fstream>

using namespace std;



int main() {
	int n, m;
	int s, t;
	ifstream infile("input.txt");
	cin >> n >> m;
	unordered_map<int, vector<int>> table;
	vector<int> inDegrees(n, 0);
	while (m--) {
		cin >> s >> t;
		inDegrees[t]++;
		table[s].emplace_back(t);
	}

	queue<int> que;
	for (int i = 0; i < n; ++i) {
		if (inDegrees[i] == 0)
			que.push(i);
	}
	vector<int> result;
	while (!que.empty()) {
		int cur = que.front();
		que.pop();
		result.push_back(cur);

		for (int t : table[cur]) {
			inDegrees[t]--;
			if (inDegrees[t] == 0)
				que.push(t);
		}
	}
	if (result.size() != n) cout << -1;
	else {
		for (int i = 0; i < n - 1; ++i) 
		    cout << result[i] << " ";
        cout << result[n - 1];
	}
	
	return 0;
}

思路是三部：

1. 找到距离源点最近的节点
2. 将节点标记为已访问
3. 更新非访问节点的minDist

本算法所需要的数据结构：
存放图的临接矩阵
记录访问的一维数组
记录到源点的距离的一维数组

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <fstream>
#include <climits>
using namespace std;



int main() {
	int n, m;
	int s, e, v;
	ifstream infile("input.txt");
	cin >> n >> m;
	vector<vector<int>> graph(n + 1, vector<int>(n + 1, INT_MAX));
	
	while (m--) {
		cin >> s >> e >> v;
		graph[s][e] = v;
	}
	// 记录访问的一维数组
	vector<bool> visited(n + 1, false);
	// 记录到源点的距离的一维数组  
	vector<int> minDist(n + 1, INT_MAX);

	minDist[1] = 0;

	for (int i = 1; i <= n; ++i) {
		// 找到距离源点最近的节点
		int cur = 1;
		int minVal = INT_MAX;
		for (int v = 1; v <= n; ++v) {
			if (!visited[v] && minDist[v] < minVal) {
				cur = v;
				minVal = minDist[v];
			}
		}

		// 将节点标记为已访问
		visited[cur] = true;

		// 更新非访问节点的minDist
		for (int e = 1; e <= n; ++e) {
			if (!visited[e] && graph[cur][e] != INT_MAX && graph[cur][e] + minVal < minDist[e])
				minDist[e] = graph[cur][e] + minVal;
		}
		
	}
	if (minDist[n] == INT_MAX) cout << -1 << endl;
    else cout << minDist[n] << endl;
	return 0;
}