C++ math庫與圖論算法的結合

C++的math庫提供了許多基本的數學函數和操作，而圖論算法則用于處理圖結構數據。將這兩者結合起來，可以實現更復雜的功能，例如計算圖的某些屬性、尋找最短路徑或進行網絡分析等。

以下是一些將C++ math庫與圖論算法結合的例子：

1. 計算圖的歐拉回路或路徑

歐拉回路是指一條通過圖中每條邊恰好一次的回路。歐拉路徑則是指一條通過圖中每條邊恰好一次的路徑，但不要求回路。可以使用C++的math庫來計算圖的歐拉回路或路徑。

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

using namespace std;

struct Edge {
    int to, weight;
};

vector<Edge> graph[10];

bool visited[10];

void addEdge(int from, int to, int weight) {
    graph[from].push_back({to, weight});
    graph[to].push_back({from, weight});
}

bool dfs(int node) {
    visited[node] = true;
    for (Edge edge : graph[node]) {
        if (!visited[edge.to]) {
            if (dfs(edge.to)) {
                return true;
            }
        }
    }
    cout << node << " ";
    return false;
}

void eulerPath(int start) {
    fill(visited, visited + 10, false);
    dfs(start);
    cout << endl;
}

int main() {
    addEdge(0, 1, 1);
    addEdge(1, 2, 1);
    addEdge(2, 3, 1);
    addEdge(3, 4, 1);
    addEdge(4, 0, 1);
    eulerPath(0); // Output: 0 1 2 3 4
    return 0;
}

2. 計算圖的最短路徑

Dijkstra算法是一種用于計算圖中兩點之間最短路徑的算法。可以使用C++的math庫來計算圖的鄰接矩陣或鄰接表，并使用Dijkstra算法計算最短路徑。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Edge {
    int to, weight;
};

vector<Edge> graph[10];

void addEdge(int from, int to, int weight) {
    graph[from].push_back({to, weight});
    graph[to].push_back({from, weight});
}

vector<int> dijkstra(int start) {
    vector<int> dist(10, INT_MAX);
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (d > dist[u]) continue;
        for (Edge edge : graph[u]) {
            if (dist[edge.to] > dist[u] + edge.weight) {
                dist[edge.to] = dist[u] + edge.weight;
                pq.push({dist[edge.to], edge.to});
            }
        }
    }
    return dist;
}

int main() {
    addEdge(0, 1, 4);
    addEdge(0, 2, 2);
    addEdge(1, 3, 5);
    addEdge(1, 4, 1);
    addEdge(2, 1, 1);
    addEdge(2, 3, 4);
    addEdge(2, 5, 8);
    addEdge(3, 4, 1);
    addEdge(4, 5, 2);
    vector<int> dist = dijkstra(0);
    for (int i = 0; i < 6; ++i) {
        cout << "Distance from 0 to "<< i << ": " << dist[i] << endl;
    }
    return 0;
}

這些例子展示了如何將C++的math庫與圖論算法結合起來解決實際問題。當然，還有很多其他的問題和應用場景可以通過這種方式來解決。