bô ghép cực dại đồ thị hai phía
ChatGPT
Bộ ghép cực đại trong đồ thị hai phía (Bipartite Graph Maximum Matching) là một bài toán trong lý thuyết đồ thị. Giải thuật Hopcroft-Karp là một trong những phương pháp hiệu quả để tìm bộ ghép cực đại trong đồ thị hai phía. Dưới đây là cách triển khai giải thuật này bằng Python và C++.
Python Code:
python
Sao chép mã
from collections import deque, defaultdict
class BipartiteGraph:
def __init__(self, n, m):
self.n = n # Number of vertices in set U
self.m = m # Number of vertices in set V
self.graph = defaultdict(list)
self.matching = [-1] * (n + m)
self.dist = [-1] * (n + m)
def add_edge(self, u, v):
self.graph[u].append(v + self.n) # Shift v's index to the second part of the bipartite graph
self.graph[v + self.n].append(u)
def bfs(self):
queue = deque()
for u in range(self.n):
if self.matching[u] == -1:
self.dist[u] = 0
queue.append(u)
else:
self.dist[u] = float('inf')
self.dist[-1] = float('inf')
while queue:
u = queue.popleft()
if self.dist[u] < self.dist[-1]:
for v in self.graph[u]:
if self.dist[self.matching[v]] == float('inf'):
self.dist[self.matching[v]] = self.dist[u] + 1
queue.append(self.matching[v])
return self.dist[-1] != float('inf')
def dfs(self, u):
if u != -1:
for v in self.graph[u]:
if self.dist[self.matching[v]] == self.dist[u] + 1 and self.dfs(self.matching[v]):
self.matching[v] = u
self.matching[u] = v
return True
self.dist[u] = float('inf')
return False
return True
def hopcroft_karp(self):
matching_size = 0
while self.bfs():
for u in range(self.n):
if self.matching[u] == -1 and self.dfs(u):
matching_size += 1
return matching_size
# Driver code
n, m = 4, 4 # Number of vertices in set U and V
g = BipartiteGraph(n, m)
g.add_edge(0, 0)
g.add_edge(0, 1)
g.add_edge(1, 1)
g.add_edge(1, 2)
g.add_edge(2, 2)
g.add_edge(2, 3)
g.add_edge(3, 0)
g.add_edge(3, 3)
print("Maximum matching size:", g.hopcroft_karp())
C++ Code:
cpp
Sao chép mã
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAX = 1000;
vector<int> graph[MAX];
int pairU[MAX], pairV[MAX], dist[MAX];
int n, m; // Number of vertices in set U and V
bool bfs() {
queue<int> q;
for (int u = 0; u < n; u++) {
if (pairU[u] == -1) {
dist[u] = 0;
q.push(u);
} else {
dist[u] = INT_MAX;
}
}
dist[-1] = INT_MAX;
while (!q.empty()) {
int u = q.front();
q.pop();
if (dist[u] < dist[-1]) {
for (int v : graph[u]) {
if (dist[pairV[v]] == INT_MAX) {
dist[pairV[v]] = dist[u] + 1;
q.push(pairV[v]);
}
}
}
}
return dist[-1] != INT_MAX;
}
bool dfs(int u) {
if (u != -1) {
for (int v : graph[u]) {
if (dist[pairV[v]] == dist[u] + 1 && dfs(pairV[v])) {
pairV[v] = u;
pairU[u] = v;
return true;
}
}
dist[u] = INT_MAX;
return false;
}
return true;
}
int hopcroftKarp() {
memset(pairU, -1, sizeof(pairU));
memset(pairV, -1, sizeof(pairV));
int matching = 0;
while (bfs()) {
for (int u = 0; u < n; u++) {
if (pairU[u] == -1 && dfs(u)) {
matching++;
}
}
}
return matching;
}
int main() {
n = 4;
m = 4;
graph[0].push_back(0);
graph[0].push_back(1);
graph[1].push_back(1);
graph[1].push_back(2);
graph[2].push
tiep
ChatGPT
Tiếp theo là phần còn lại của mã C++:
cpp
Sao chép mã
graph[2].push_back(2);
graph[2].push_back(3);
graph[3].push_back(0);
graph[3].push_back(3);
cout << "Maximum matching size: " << hopcroftKarp() << endl;
return 0;
}
Giải thích mã
Python Code:
Class BipartiteGraph: Tạo đồ thị hai phía với các đỉnh từ tập hợp U và V.
add_edge method: Thêm cạnh giữa các đỉnh trong đồ thị hai phía.
bfs method: Sử dụng BFS để tìm tất cả các đường ngắn nhất từ nguồn đến đích và cập nhật khoảng cách của các đỉnh.
dfs method: Sử dụng DFS để tìm đường tăng trong đồ thị mức (level graph) và cập nhật các cạnh.
hopcroft_karp method: Áp dụng giải thuật Hopcroft-Karp để tìm bộ ghép cực đại.
C++ Code:
**Các biến toàn cục và
giải thuật bộ ghép cực đại
ChatGPT
Giải thuật tìm bộ ghép cực đại trong đồ thị hai phía (Maximum Bipartite Matching) là một trong những bài toán quan trọng trong lý thuyết đồ thị. Giải thuật Hopcroft-Karp là một trong những phương pháp hiệu quả để giải quyết bài toán này. Dưới đây là giải thích chi tiết và cách triển khai giải thuật này bằng Python và C++.
Giải Thuật Hopcroft-Karp
Giải thuật Hopcroft-Karp hoạt động theo các bước chính sau:
Tìm tất cả các đường ngắn nhất từ các đỉnh chưa được ghép nối trong tập U đến các đỉnh chưa được ghép nối trong tập V sử dụng BFS.
Sử dụng DFS để tìm và tăng cường các đường ghép (augmenting paths) dựa trên đồ thị mức (level graph) đã tìm được.
Lặp lại quá trình trên cho đến khi không còn đường tăng cường nào nữa.
Python Code
python
Sao chép mã
from collections import deque, defaultdict
class BipartiteGraph:
def __init__(self, n, m):
self.n = n # Number of vertices in set U
self.m = m # Number of vertices in set V
self.graph = defaultdict(list)
self.matching = [-1] * (n + m)
self.dist = [-1] * (n + m)
def add_edge(self, u, v):
self.graph[u].append(v + self.n) # Shift v's index to the second part of the bipartite graph
self.graph[v + self.n].append(u)
def bfs(self):
queue = deque()
for u in range(self.n):
if self.matching[u] == -1:
self.dist[u] = 0
queue.append(u)
else:
self.dist[u] = float('inf')
self.dist[-1] = float('inf')
while queue:
u = queue.popleft()
if self.dist[u] < self.dist[-1]:
for v in self.graph[u]:
if self.dist[self.matching[v]] == float('inf'):
self.dist[self.matching[v]] = self.dist[u] + 1
queue.append(self.matching[v])
return self.dist[-1] != float('inf')
def dfs(self, u):
if u != -1:
for v in self.graph[u]:
if self.dist[self.matching[v]] == self.dist[u] + 1 and self.dfs(self.matching[v]):
self.matching[v] = u
self.matching[u] = v
return True
self.dist[u] = float('inf')
return False
return True
def hopcroft_karp(self):
matching_size = 0
while self.bfs():
for u in range(self.n):
if self.matching[u] == -1 and self.dfs(u):
matching_size += 1
return matching_size
# Driver code
n, m = 4, 4 # Number of vertices in set U and V
g = BipartiteGraph(n, m)
g.add_edge(0, 0)
g.add_edge(0, 1)
g.add_edge(1, 1)
g.add_edge(1, 2)
g.add_edge(2, 2)
g.add_edge(2, 3)
g.add_edge(3, 0)
g.add_edge(3, 3)
print("Maximum matching size:", g.hopcroft_karp())
C++ Code
cpp
Sao chép mã
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAX = 1000;
vector<int> graph[MAX];
int pairU[MAX], pairV[MAX], dist[MAX];
int n, m; // Number of vertices in set U and V
bool bfs() {
queue<int> q;
for (int u = 0; u < n; u++) {
if (pairU[u] == -1) {
dist[u] = 0;
q.push(u);
} else {
dist[u] = INT_MAX;
}
}
dist[-1] = INT_MAX;
while (!q.empty()) {
int u = q.front();
q.pop();
if (dist[u] < dist[-1]) {
for (int v : graph[u]) {
if (dist[pairV[v]] == INT_MAX) {
dist[pairV[v]] = dist[u] + 1;
q.push(pairV[v]);
}
}
}
}
return dist[-1] != INT_MAX;
}
bool dfs(int u) {
if (u != -1) {
for (int v : graph[u]) {
if (dist[pairV[v]] == dist[u] + 1 && dfs(pairV[v])) {
pairV[v] = u;
pairU[u] = v;
return true;
}
}
dist[u] = INT_MAX;
return false;
}
return true;
}
int hopcroftKarp() {
memset(pairU, -1, sizeof(pairU));
memset(pairV, -1, sizeof(pairV));
int matching = 0;
while (bfs()) {
for (int u = 0; u < n; u++) {
if (pairU[u] == -1 && dfs(u)) {
matching++;
}
}
}
return matching;
}
int main() {
n = 4;
m = 4;
graph[0].push_back(0);
graph[0].push_back(1);
graph[1].push_back(1);
graph[1].push_back(2);
graph[2].push_back(2);
graph[2].push_back(3);
graph[3].push_back(0);
graph[3].push_back(3);
cout << "Maximum matching size: " << hopcroftKarp() << endl;
return 0;
}
Giải thích mã
Python Code:
Class BipartiteGraph: Định nghĩa đồ thị hai phía với các đỉnh từ tập hợp U và V.
add_edge method: Thêm cạnh giữa các đỉnh trong đồ thị hai phía.
bfs method: Sử dụng BFS để tìm tất cả các đường ngắn nhất từ nguồn đến đích và cập nhật khoảng cách của các đỉnh.
dfs method: Sử dụng DFS để tìm đường tăng trong đồ thị mức (level graph) và cập nhật các cạnh.
hopcroft_karp method: Áp dụng giải thuật Hopcroft-Karp để tìm bộ ghép cực đại.
C++ Code:
Các biến toàn cục và hằng số: Khởi tạo các biến.
bfs function: Sử dụng BFS để tìm các đường ngắn nhất từ nguồn đến đích.
dfs function: Sử dụng DFS để tìm và tăng cường các đường ghép.
hopcroftKarp function: Áp dụng giải thuật Hopcroft-Karp để tìm bộ ghép cực đại.
main function: Khởi tạo đồ thị và tìm bộ ghép cực đại.