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;
}