Lý Thuyết Đồ Thị - Graph Theory

Các thuật toán lý thuyết đồ thị, tìm đường với độ sâu và độ rộng, các giải thuật đồ thị nâng cao với C++.

Thuật toán Floyd - Floyd algorithm

1234567891011121314151617181920212223242526272829303132333435363738394041
#include <iostream> using namespace std; #define inf 1e9 #define maxN 100 int graph[maxN][maxN]; int numberOfNodes, numberOfEdges; void floyd(int graph[maxN][maxN], int numberOfNodes) { for (int k = 1; k <= numberOfNodes; k++) for (int i = 1; i <= numberOfNodes; i++) for (int j = 1; j <= numberOfNodes; j++) if (graph[i][j] > graph[i][k] + graph[k][j]) graph[i][j] = graph[i][k] + graph[k][j]; } void initGraph(int graph[maxN][maxN], int numberOfNodes) { memset(graph, inf, sizeof(graph)); for (int i = 1; i <= numberOfNodes; i++) graph[i][i] = 0; } int main() { cin >> numberOfNodes >> numberOfEdges; initGraph(graph, numberOfNodes); for (int i = 0; i < numberOfEdges; i++) { int source, dest, weight; cin >> source >> dest >> weight; graph[source][dest] = graph[dest][source] = weight; } floyd(graph, numberOfEdges); cout << graph[1][numberOfEdges] << endl; return 0; }

Thuật toán Dijkstra - Dijkstra algorithm

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960
#include <vector> #include <queue> #include <iostream> using namespace std; #define inf 1000000000 #define maxN 1000 typedef pair<int, int> pii; vector <pii> graph[maxN]; int numberOfNodes, numberOfEdges; int d[maxN]; void dijkstra(int start, int finish) { priority_queue<pii, vector<pii>, greater<pii> > minHeap; for (int i = 1; i <= numberOfNodes; i++) d[i] = inf; d[start] = 0; minHeap.push(make_pair(0, start)); while (minHeap.size()) { int u = minHeap.top().second; int weightU = minHeap.top().first; minHeap.pop(); if (weightU != d[u]) continue; for (int i = 0; int v = graph[u][i].second; i++) { int weight = graph[u][i].first; if (d[v] > weightU + weight) { d[v] = weightU + weight; minHeap.push(make_pair(d[v], v)); } } } } int main() { cin >> numberOfNodes >> numberOfEdges; for (int i = 0; i < numberOfEdges; i++) { int source, dest, weight; cin >> source >> dest >> weight; graph[source].push_back(make_pair(weight, dest)); graph[dest].push_back(make_pair(weight, source)); } for (int i = 1; i <= numberOfNodes; i++) graph[i].push_back(make_pair(0, 0)); dijkstra(1, 3); cout << d[3] << endl; return 0; }

Thuật toán DFS - DFS algorithm

1234567891011121314151617181920212223242526272829303132333435363738394041
#include <stdio.h> #include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; #define maxN 1000 vector <int> graph[maxN]; bool visited[maxN]; void dfs(int start) { cout << start << " "; visited[start] = true; for (int i = 0; i < graph[start].size(); i++) { int v = graph[start][i]; if (!visited[v]) dfs(v); } } int main() { int n, m; cin >> n >> m; while (m--) { int u, v; cin >> u >> v; graph[u].push_back(v); graph[v].push_back(u); } int start; cin >> start; memset(visited, false, maxN); dfs(start); return 0; }

Thuật toán BFS - BFS algorithm

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950
#include <iostream> #include <vector> #include <queue> using namespace std; #define maxN 1000 vector <int> graph[maxN]; int numberOfNodes, numberOfEdges; void bfs(int start) { bool visited[maxN]; queue <int> qu; memset(visited, false, maxN); qu.push(start); visited[start] = true; while (qu.size()) { int u = qu.front(); qu.pop(); cout << u << " "; for (unsigned int i = 0; i < graph[u].size(); i++) { int v = graph[u][i]; if (!visited[v]) { visited[v] = true; qu.push(v); } } } } int main() { cin >> numberOfNodes >> numberOfEdges; while (numberOfEdges--) { int u, v; cin >> u >> v; graph[u].push_back(v); graph[v].push_back(u); } int start; cin >> start; bfs(start); return 0; }

Thuật toán A*

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
#include <vector> #include <iostream> #include <algorithm> using namespace std; #define maxN 100 int numberOfNodes, numberOfEdges; vector<int> graph[maxN]; void dfs(int u, int p, int &visitTime, int &bridges, bool isCriticalNode[], int lowValue[], int discoveryTimes[], vector<int> graph[]) { int numChild = 0; lowValue[u] = discoveryTimes[u] = ++visitTime; for (int i = 0; int v = graph[u][i]; i++) { if (v != p) { if (discoveryTimes[v] != 0) lowValue[u] = min(lowValue[u], discoveryTimes[v]); else { dfs(v, u, visitTime, bridges, isCriticalNode, lowValue, discoveryTimes, graph); numChild++; lowValue[u] = min(lowValue[u], lowValue[v]); if (lowValue[v] >= discoveryTimes[v]) bridges++; if (u == p) if (numChild >= 2) isCriticalNode[u] = true; else if (lowValue[v] >= discoveryTimes[u]) isCriticalNode[u] = true; } } } } void findCutVerticesAndBridges(int numberOfNodes, vector<int> graph[], int &cutVertices, int& bridges) { bool isCriticalNode[maxN]; int discoveryTimes[maxN], lowValue[maxN], visitTime = 0; memset(discoveryTimes, 0, sizeof(discoveryTimes)); memset(lowValue, 0, sizeof(lowValue)); memset(isCriticalNode, false, sizeof(isCriticalNode)); for (int i = 1; i <= numberOfNodes; i++) if (!discoveryTimes[i]) dfs(i, i, visitTime, bridges, isCriticalNode, lowValue, discoveryTimes, graph); for (int i = 1; i <= numberOfNodes; i++) if (isCriticalNode[i]) cutVertices++; } int main() { cin >> numberOfNodes >> numberOfEdges; for (int i = 0; i < numberOfEdges; i++) { int source, dest; cin >> source >> dest; graph[source].push_back(dest); graph[dest].push_back(source); } for (int i = 1; i <= numberOfNodes; i++) graph[i].push_back(0); int bridges = 0; int cutVertices = 0; findCutVerticesAndBridges(numberOfNodes, graph, cutVertices, bridges); cout << cutVertices << " " << bridges << endl; return 0; }

Thuật toán Tarjan - Tarjan algorithm

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667
#include <iostream> #include <vector> #include <stack> using namespace std; #define maxN 100 vector <int> graph[maxN]; int numberOfNodes, numberOfEdges, stronglyConnectedComponents; void dfs(int start, int &visitTime, int lowValue[], int discoveryTimes[], bool mark[], vector<int> graph[], stack<int> st) { lowValue[start] = discoveryTimes[start] = ++visitTime; st.push(start); for (int i = 0; i < graph[start].size(); i++) { int v = graph[start][i]; if (mark[v] == true) if (discoveryTimes[v] == 0) { dfs(v, visitTime, lowValue, discoveryTimes, mark, graph, st); if (lowValue[start] > lowValue[v]) lowValue[start] = lowValue[v]; } else if (lowValue[start] > discoveryTimes[v]) lowValue[start] = discoveryTimes[v]; } if (lowValue[start] == discoveryTimes[start]) { int v; stronglyConnectedComponents++; do { v = st.top(); st.pop(); mark[v] = false; } while (v != start); } } void tarjan(int numberOfNodes, vector<int> graph[]) { stack <int> st; int lowValue[maxN], discoveryTimes[maxN]; int visitTime; bool mark[maxN]; memset(mark, true, sizeof(mark)); memset(lowValue, 0, sizeof(lowValue)); memset(discoveryTimes, 0, sizeof(discoveryTimes)); visitTime = 0; stronglyConnectedComponents = 0; for (int j = 1; j <= numberOfNodes; j++) if (discoveryTimes[j] == 0) dfs(j, visitTime, lowValue, discoveryTimes, mark, graph, st); } int main() { cin >> numberOfNodes >> numberOfEdges; for (int i = 1; i <= numberOfEdges; i++) { int source, dest; cin >> source >> dest; graph[source].push_back(dest); } tarjan(numberOfNodes, graph); cout << stronglyConnectedComponents << endl; return 0; }

Thuật toán Prim - Prim algorithm

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
#include <iostream> #include <vector> #include <queue> using namespace std; #define maxN 10 #define inf 1000000000 typedef pair<int, int> pii; int numberOfNodes, numberOfEdges; int d[maxN]; vector<pii> graph[maxN]; int prim(int start, int numberOfNodes, int d[], vector<pii> graph[]) { int MSTWeight = 0; priority_queue<pii> minHeap; for (int i = 1; i <= numberOfNodes; i++) d[i] = inf; minHeap.push(make_pair(0, start)); d[start] = 0; while (minHeap.size()) { int u = minHeap.top().second; int du = -minHeap.top().first; minHeap.pop(); if (du != d[u]) continue; MSTWeight += d[u]; d[u] = 0; for (int i = 0; int v = graph[u][i].second; i++) { int weight = graph[u][i].first; if (d[v] > weight) { d[v] = weight; minHeap.push(make_pair(-d[v], v)); } } } return MSTWeight; } int main() { cin >> numberOfNodes >> numberOfEdges; for (int i = 0; i < numberOfEdges; i++) { int source, dest, weight; cin >> source >> dest >> weight; graph[source].push_back(make_pair(weight, dest)); graph[dest].push_back(make_pair(weight, source)); } for (int i = 1; i <= numberOfNodes; i++) graph[i].push_back(make_pair(0, 0)); cout << prim(1, numberOfNodes, d, graph) << endl; return 0; }

Thuật toán Kruskal - Kruskal algorithm

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
#include <iostream> #include <algorithm> using namespace std; #define maxN 100001 struct graphData { int source, dest, weight; }; graphData graph[maxN]; int numberOfNodes, numberOfEdges; int root[maxN]; bool compare(graphData p, graphData q) { return p.weight < q.weight; } int getRoot(int x) { if (root[x] == 0) return x; return (root[x] = getRoot(root[x])); } int kruskal(graphData graph[], int numberOfEdges) { int MSTWeight = 0; sort(graph, graph + numberOfEdges, compare); for (int i = 0; i < numberOfEdges; i++) { int r1 = getRoot(graph[i].source); int r2 = getRoot(graph[i].dest); if (r1 != r2) { root[r2] = r1; MSTWeight += graph[i].weight; } } return MSTWeight; } int main() { cin >> numberOfNodes >> numberOfEdges; for (int i = 0; i < numberOfEdges; i++) cin >> graph[i].source >> graph[i].dest >> graph[i].weight; cout << kruskal(graph, numberOfEdges) << endl; return 0; }

Thuật toán Hamilton - Hamilton algorithm

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
#include <iostream> using namespace std; #define maxN 105 bool graph[maxN][maxN]; int numberOfNodes, numberOfEdges; void hamilton(int i, int numberOfNodes, int trace[], bool isFree[], bool graph[][maxN]) { for (int j = 1; j <= numberOfNodes; j++) { if (isFree[j] && graph[trace[i - 1]][j]) { trace[i] = j; if (i < numberOfNodes) { isFree[j] = false; hamilton(i + 1, numberOfNodes, trace, isFree, graph); isFree[j] = true; } else if (graph[j][trace[1]]) { for (int i = 1; i <= numberOfNodes; i++) cout << trace[i] << " "; cout << trace[1] << endl; } } } } void findHamiltonCycle(int numberOfNodes, bool graph[][maxN]) { int trace[maxN]; bool isFree[maxN]; memset(trace, 0, sizeof(trace)); memset(isFree, true, sizeof(isFree)); isFree[1] = false; trace[1] = 1; hamilton(2, numberOfNodes, trace, isFree, graph); } int main() { cin >> numberOfNodes >> numberOfEdges; for (int i = 0; i < numberOfEdges; i++) { int source, dest; cin >> source >> dest; graph[source][dest] = graph[dest][source] = true; } findHamiltonCycle(numberOfNodes, graph); return 0; }