图论相关代码 (C++ & Python)
如题, 有 Dijkstra 和 Floyd 算法
/*
* @Author: wangzhiyu
* @Date: 2023-09-03 02:29:26
* @Last Modified by: wangzhiyu
* @Last Modified time: 2024-07-30 22:47:07
*/
#include <cmath>
#include <cstring>
#include <time.h>
#include <iostream>
#include <vector>
#include <unistd.h> // for linux
// #include <windows.h> // for windows
using namespace std;
using ll = long long;
constexpr int LIM1 = 205; // 预分配阙值
constexpr int INF = 0x3f3f3f3f; // 近似无限大
/// @brief 图论相关
namespace graph {
int n;
/// @brief 节点数据结构
struct Node {
int nxt;
int w;
};
vector<Node> edges[LIM1];
/// @brief 增加一条边
/// @param from
/// @param to
/// @param w 权值
void addedge(int from, int to, int w) { edges[from].push_back({to, w}); }
/// @brief 删除某边
/// @param from
/// @param to
void deledge(int from, int to) { // delete an edge
for (auto i = edges[from].begin(); i != edges[from].end();) {
if ((*i).nxt == to) {
i = edges[from].erase(i);
} else {
i++;
}
}
}
/// @brief 查询某边的权值
/// @param from
/// @param to
/// @return 权值
int queryedge(int from, int to) { // to query an edge's weight
if (from == to)
return 0;
for (auto i = edges[from].begin(); i != edges[from].end(); i++) {
if ((*i).nxt == to) {
return (*i).w;
}
}
return INF;
}
/*
void dfs_launcher(){
for(int i = 1; i <= n; i++){
dfs(i);
}
}
void dfs(int begin, ){
cerr << "Access: " << begin;
dfs(edges[begin].nxt);
}
*/
/// @brief Floyd 最短路算法
/// @param spec 待展示的点标号
void sp_f(int spec) { // Floyd algorithm
int sp[LIM1][LIM1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sp[i][j] = queryedge(i, j);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
sp[i][j] = min(sp[i][j], sp[i][k] + sp[k][j]);
}
}
}
for (int i = 1; i <= n; i++) {
string dist = to_string(sp[spec][i]);
if (dist == to_string(INF))
dist = "∞"; // unable to reach
cerr << spec << " -[" << dist << "]-> " << i << " (floyd)" << endl;
}
}
/// @brief 输出某点详情
/// @param idx 特定点索引
void print(int idx) { // to print a particular vertex's detail information
cout << "Print: " << idx << endl << " > ";
for (auto &i : edges[idx]) {
cout << i.nxt << "(" << i.w << ")"
<< " ";
}
for (int i = 1; i <= idx ; i++){
}
cout << endl;
}
/// @brief Dijkstra 单源最短路径算法
/// @param begin 源点标号
void sp_dij(int begin) { // Dijkstra algorithm
bool vis[LIM1]; // visiting status
fill(vis + 1, vis + n + 1, 0); // clear status
int sp[LIM1]; // shortest path's distance
for (int i = 1; i <= n; i++) { // initalize distance
sp[i] = queryedge(begin, i);
}
vis[begin] = 1; // mark beginner's visit
for (int k = 1; k <= n - 1; k++) { // this loop makes every vertex
// successfully marked (except beginner)
int best_transfer; // best transfer vertex
int mindistance = INF; // temp min distance
for (int i = 1; i <= n; i++) { // calc best_transfer
if (queryedge(begin, i) < mindistance && vis[i] != 1) {
mindistance = queryedge(begin, i);
best_transfer = i;
}
}
// once best_transfer confirmed, mark its visit
vis[best_transfer] = 1;
for (int i = 1; i <= n; i++) { // recalc transferred distance
if (vis[i] != 1) {
if (queryedge(begin, best_transfer) +
queryedge(best_transfer, i) <
queryedge(begin, i)) {
sp[i] = queryedge(begin, best_transfer) +
queryedge(best_transfer, i);
}
}
}
}
// print result
for (int i = 1; i <= n; i++) {
string dist = to_string(sp[i]);
if (dist == to_string(INF))
dist = "∞"; // unable to reach
cerr << begin << " -[" << dist << "]-> " << i << " (dijkstra)" << endl;
}
}
/// @brief 自然地初始化图
/// @param data 格式化的图数据, 参照 https://csacademy.com/app/graph_editor/,
/// 第一行和最后一行必须是换行符
void naturally_init(string data) {
// raw string feature required, last line must be \n;
bool flag = 0; // dotmode/edgemode
string formatted[3];
int k = 0;
while (*(data.begin()) != '\n')
data.erase(data.begin()); // erase beginner
data.erase(data.begin());
for (char i : data) {
if (!flag) {
if (i != '\n')
formatted[0].push_back(i);
else {
n++;
formatted[0] = "";
}
}
if (i == ' ') flag = 1;
if (flag) {
if (i != ' ' && i != '\n')
formatted[k % 3].push_back(i);
else
k++;
if (i == '\n') {
addedge(stoi(formatted[0]), stoi(formatted[1]),
stoi(formatted[2]));
formatted[0] = "";
formatted[1] = "";
formatted[2] = "";
}
}
}
cerr << "Automatically initialization finished" << endl;
cerr << "Node number: " << n << endl;
}
} // namespace graph
/// @brief 实用函数与性能分析
namespace utils {
/// @brief 输出分割符
void spilt() { cerr << "------------------------" << endl; }
time_t lasttime = INF, currtime = 0;
/// @brief 自动计时器
void autoclock() {
cerr << clock();
cerr << fixed << endl;
cerr << "\033[31m";
if(lasttime == INF){
cerr << "[TIMG GAP] INIT\033[0m" << endl;
lasttime = clock();
return;
}
currtime = clock();
double dur;
dur = (double)(currtime - lasttime);
cerr << "[TIME GAP] "<< dur/CLOCKS_PER_SEC << endl;
lasttime = clock();
cerr << "\033[0m";
}
} // namespace utils
int main() {
string original_graph = R"( 格式化的图数据:
1
2
3
4
5
6
7
8
9
10
6 2 9
2 4 3
4 5 2
1 4 2
1 5 9
2 3 2
2 7 6
1 9 8
1 3 4
9 10 4
4 6 3
2 5 8
2 8 2
2 10 2
8 9 7
3 7 6
)";
graph::naturally_init(original_graph);
cout << fixed; // 禁用科学计数法输出
cout << graph::queryedge(1, 3) << endl;
cout << graph::queryedge(1, 3) << endl;
cout << graph::queryedge(4, 9) << endl;
graph::print(1);
graph::print(2);
utils::spilt();
utils::autoclock();
graph::sp_f(2);
utils::autoclock();
graph::sp_dij(2);
utils::autoclock();
utils::spilt();
graph::sp_f(3);
graph::sp_dij(3);
return 0;
}