Giải thuật tìm cầu (bridge) trong đồ thị nhằm xác định các cạnh mà khi loại bỏ chúng, đồ thị sẽ bị phân tách thành hai thành phần liên thông. Một cầu trong đồ thị vô hướng là một cạnh mà khi loại bỏ nó sẽ làm tăng số lượng thành phần liên thông của đồ thị.
Giải thuật tìm cầu sử dụng DFS (Depth-First Search)
Dưới đây là một giải thuật sử dụng DFS để tìm cầu trong đồ thị:
Khởi tạo các mảng disc (discovery time), low (lowest discovery time reachable), parent, và visited.
Thực hiện DFS để cập nhật giá trị của disc và low.
Trong quá trình DFS, kiểm tra các điều kiện để xác định cầu.
Mã giả
python
Sao chép mã
def find_bridges(graph):
def dfs(u):
nonlocal time
visited[u] = True
disc[u] = low[u] = time
time += 1
for v in graph[u]:
if not visited[v]:
parent[v] = u
dfs(v)
low[u] = min(low[u], low[v])
if low[v] > disc[u]:
bridges.append((u, v))
elif v != parent[u]:
low[u] = min(low[u], disc[v])
n = len(graph)
visited = [False] * n
disc = [float('Inf')] * n
low = [float('Inf')] * n
parent = [-1] * n
bridges = []
time = 0
for i in range(n):
if not visited[i]:
dfs(i)
return bridges
# Example usage:
# graph = {
# 0: [1, 2],
# 1: [0, 2],
# 2: [0, 1, 3],
# 3: [2]
# }
# print(find_bridges(graph)) # Output: [(2, 3)]
Giải thích
disc[u]: Thời điểm khi đỉnh u được khám phá lần đầu tiên.
low[u]: Giá trị nhỏ nhất trong các đỉnh mà u có thể truy cập được thông qua các cạnh ngược.
parent[u]: Đỉnh cha của u trong cây DFS.
visited[u]: Trạng thái đã thăm hay chưa của đỉnh u.
bridges: Danh sách các cạnh cầu.
Trong DFS, nếu low[v] > disc[u], điều đó có nghĩa là không có đường nào từ v hoặc từ các con cháu của v quay lại đỉnh tổ tiên của u, ngoại trừ thông qua cạnh (u, v). Do đó, cạnh (u, v) là một cầu.
Độ phức tạp
Thời gian: O(V + E), với V là số đỉnh và E là số cạnh.
Không gian: O(V) cho các mảng lưu trữ thông tin.
Nếu cần thêm chi tiết hoặc hỗ trợ về giải thuật này, hãy cho tôi biết!
code python c++
ChatGPT
Mã Python
Dưới đây là mã Python hoàn chỉnh cho giải thuật tìm cầu trong đồ thị:
python
Sao chép mã
def find_bridges(graph):
def dfs(u):
nonlocal time
visited[u] = True
disc[u] = low[u] = time
time += 1
for v in graph[u]:
if not visited[v]:
parent[v] = u
dfs(v)
low[u] = min(low[u], low[v])
if low[v] > disc[u]:
bridges.append((u, v))
elif v != parent[u]:
low[u] = min(low[u], disc[v])
n = len(graph)
visited = [False] * n
disc = [float('Inf')] * n
low = [float('Inf')] * n
parent = [-1] * n
bridges = []
time = 0
for i in range(n):
if not visited[i]:
dfs(i)
return bridges
# Example usage:
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2]
}
print(find_bridges(graph)) # Output: [(2, 3)]
Mã C++
Dưới đây là mã C++ tương đương:
cpp
Sao chép mã
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
void dfs(int u, vector<vector<int>>& graph, vector<bool>& visited, vector<int>& disc, vector<int>& low, vector<int>& parent, vector<pair<int, int>>& bridges, int& time) {
visited[u] = true;
disc[u] = low[u] = ++time;
for (int v : graph[u]) {
if (!visited[v]) {
parent[v] = u;
dfs(v, graph, visited, disc, low, parent, bridges, time);
low[u] = min(low[u], low[v]);
if (low[v] > disc[u]) {
bridges.push_back({u, v});
}
} else if (v != parent[u]) {
low[u] = min(low[u], disc[v]);
}
}
}
vector<pair<int, int>> findBridges(vector<vector<int>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
vector<int> disc(n, INT_MAX);
vector<int> low(n, INT_MAX);
vector<int> parent(n, -1);
vector<pair<int, int>> bridges;
int time = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, graph, visited, disc, low, parent, bridges, time);
}
}
return bridges;
}
int main() {
vector<vector<int>> graph = {
{1, 2},
{0, 2},
{0, 1, 3},
{2}
};
vector<pair<int, int>> bridges = findBridges(graph);
for (auto bridge : bridges) {
cout << "(" << bridge.first << ", " << bridge.second << ")" << endl;
}
return 0;
}
Giải thích
Mã Python: Định nghĩa hàm find_bridges để tìm cầu trong đồ thị và hàm dfs để thực hiện DFS và cập nhật các giá trị disc, low, và kiểm tra điều kiện cầu.
Mã C++: Tương tự, định nghĩa hàm dfs và findBridges. Sử dụng vector để lưu đồ thị, trạng thái đã thăm, thời gian khám phá, giá trị low, đỉnh cha, và danh sách các cầu. Mã này sử dụng pair để lưu các cạnh cầu.
Cả hai mã đều thực hiện cùng một giải thuật để tìm cầu trong đồ thị vô hướng.
Giải thuật tìm khớp đồ thị
ChatGPT
Giải thuật tìm đỉnh khớp (articulation points) trong đồ thị nhằm xác định các đỉnh mà khi loại bỏ chúng, đồ thị sẽ bị phân tách thành nhiều thành phần liên thông hơn. Một đỉnh khớp trong đồ thị vô hướng là một đỉnh mà khi loại bỏ nó sẽ làm tăng số lượng thành phần liên thông của đồ thị.
Giải thuật tìm đỉnh khớp sử dụng DFS (Depth-First Search)
Dưới đây là một giải thuật sử dụng DFS để tìm đỉnh khớp trong đồ thị:
Khởi tạo các mảng disc (discovery time), low (lowest discovery time reachable), parent, visited và ap (articulation points).
Thực hiện DFS để cập nhật giá trị của disc và low.
Trong quá trình DFS, kiểm tra các điều kiện để xác định đỉnh khớp.
Mã giả
python
Sao chép mã
def find_articulation_points(graph):
def dfs(u):
nonlocal time
children = 0
visited[u] = True
disc[u] = low[u] = time
time += 1
for v in graph[u]:
if not visited[v]:
parent[v] = u
children += 1
dfs(v)
low[u] = min(low[u], low[v])
if parent[u] == -1 and children > 1:
ap[u] = True
if parent[u] != -1 and low[v] >= disc[u]:
ap[u] = True
elif v != parent[u]:
low[u] = min(low[u], disc[v])
n = len(graph)
visited = [False] * n
disc = [float('Inf')] * n
low = [float('Inf')] * n
parent = [-1] * n
ap = [False] * n
time = 0
for i in range(n):
if not visited[i]:
dfs(i)
articulation_points = [i for i, is_ap in enumerate(ap) if is_ap]
return articulation_points
# Example usage:
# graph = {
# 0: [1, 2],
# 1: [0, 2],
# 2: [0, 1, 3],
# 3: [2]
# }
# print(find_articulation_points(graph)) # Output: [2]
Giải thích
disc[u]: Thời điểm khi đỉnh u được khám phá lần đầu tiên.
low[u]: Giá trị nhỏ nhất trong các đỉnh mà u có thể truy cập được thông qua các cạnh ngược.
parent[u]: Đỉnh cha của u trong cây DFS.
visited[u]: Trạng thái đã thăm hay chưa của đỉnh u.
ap[u]: Mảng boolean để đánh dấu đỉnh khớp.
Trong DFS:
Nếu u là gốc của DFS và có ít nhất hai con, thì u là đỉnh khớp.
Nếu u không phải là gốc của DFS và có một đỉnh con v sao cho không có đỉnh nào trong cây con của v có thể quay lại tổ tiên của u thông qua cạnh ngược, thì u là đỉnh khớp.
Mã C++
Dưới đây là mã C++ tương đương:
cpp
Sao chép mã
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
void dfs(int u, vector<vector<int>>& graph, vector<bool>& visited, vector<int>& disc, vector<int>& low, vector<int>& parent, vector<bool>& ap, int& time) {
int children = 0;
visited[u] = true;
disc[u] = low[u] = ++time;
for (int v : graph[u]) {
if (!visited[v]) {
parent[v] = u;
children++;
dfs(v, graph, visited, disc, low, parent, ap, time);
low[u] = min(low[u], low[v]);
if (parent[u] == -1 && children > 1)
ap[u] = true;
if (parent[u] != -1 && low[v] >= disc[u])
ap[u] = true;
} else if (v != parent[u]) {
low[u] = min(low[u], disc[v]);
}
}
}
vector<int> findArticulationPoints(vector<vector<int>>& graph) {
int n = graph.size();
vector<bool> visited(n, false);
vector<int> disc(n, INT_MAX);
vector<int> low(n, INT_MAX);
vector<int> parent(n, -1);
vector<bool> ap(n, false);
int time = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, graph, visited, disc, low, parent, ap, time);
}
}
vector<int> articulationPoints;
for (int i = 0; i < n; i++) {
if (ap[i]) {
articulationPoints.push_back(i);
}
}
return articulationPoints;
}
int main() {
vector<vector<int>> graph = {
{1, 2},
{0, 2},
{0, 1, 3},
{2}
};
vector<int> articulationPoints = findArticulationPoints(graph);
for (int ap : articulationPoints) {
cout << ap << " ";
}
return 0;
}
Giải thích
Mã Python: Định nghĩa hàm find_articulation_points để tìm đỉnh khớp trong đồ thị và hàm dfs để thực hiện DFS và cập nhật các giá trị disc, low, và kiểm tra điều kiện đỉnh khớp.
Mã C++: Tương tự, định nghĩa hàm dfs và findArticulationPoints. Sử dụng vector để lưu đồ thị, trạng thái đã thăm, thời gian khám phá, giá trị low, đỉnh cha, và mảng boolean để đánh dấu đỉnh khớp.
Cả hai mã đều thực hiện cùng một giải thuật để tìm đỉnh khớp trong đồ thị vô hướng.
giai thuat dem canh do thi
ChatGPT
Để đếm số cạnh trong một đồ thị, ta có thể sử dụng một trong các cách sau tùy vào kiểu biểu diễn đồ thị: danh sách kề hoặc ma trận kề.
Sử dụng Danh Sách Kề
Với danh sách kề, mỗi đỉnh sẽ lưu trữ các đỉnh kề với nó. Để đếm số cạnh, ta chỉ cần đếm số lượng phần tử trong các danh sách kề. Tuy nhiên, do mỗi cạnh được đếm hai lần (một lần cho mỗi đỉnh kề), ta cần chia tổng số đỉnh kề cho 2.
Mã Python
python
Sao chép mã
def count_edges(graph):
edge_count = sum(len(neighbors) for neighbors in graph.values())
return edge_count // 2
# Ví dụ sử dụng:
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3],
3: [2]
}
print(count_edges(graph)) # Output: 4
Sử dụng Ma Trận Kề
Với ma trận kề, mỗi phần tử (i, j) của ma trận sẽ là 1 nếu có cạnh nối từ đỉnh i đến đỉnh j, và là 0 nếu không có cạnh. Để đếm số cạnh, ta chỉ cần đếm số lượng phần tử 1 trong ma trận và chia cho 2.
Mã Python
python
Sao chép mã
def count_edges(matrix):
edge_count = sum(sum(row) for row in matrix)
return edge_count // 2
# Ví dụ sử dụng:
matrix = [
[0, 1, 1, 0],
[1, 0, 1, 0],
[1, 1, 0, 1],
[0, 0, 1, 0]
]
print(count_edges(matrix)) # Output: 4
Mã C++ Sử Dụng Danh Sách Kề
cpp
Sao chép mã
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int countEdges(const unordered_map<int, vector<int>>& graph) {
int edgeCount = 0;
for (const auto& pair : graph) {
edgeCount += pair.second.size();
}
return edgeCount / 2;
}
int main() {
unordered_map<int, vector<int>> graph = {
{0, {1, 2}},
{1, {0, 2}},
{2, {0, 1, 3}},
{3, {2}}
};
cout << countEdges(graph) << endl; // Output: 4
return 0;
}
Mã C++ Sử Dụng Ma Trận Kề
cpp
Sao chép mã
#include <iostream>
#include <vector>
using namespace std;
int countEdges(const vector<vector<int>>& matrix) {
int edgeCount = 0;
int n = matrix.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
edgeCount += matrix[i][j];
}
}
return edgeCount / 2;
}
int main() {
vector<vector<int>> matrix = {
{0, 1, 1, 0},
{1, 0, 1, 0},
{1, 1, 0, 1},
{0, 0, 1, 0}
};
cout << countEdges(matrix) << endl; // Output: 4
return 0;
}
Giải thích
Với danh sách kề, tổng số đỉnh kề trong tất cả các danh sách sẽ là gấp đôi số lượng cạnh (vì mỗi cạnh xuất hiện hai lần). Do đó, ta chia tổng số đỉnh kề cho 2 để có số lượng cạnh thực sự.
Với ma trận kề, mỗi cạnh sẽ được đếm hai lần (một lần cho mỗi hướng của cạnh). Do đó, ta chia tổng số 1 trong ma trận cho 2 để có số lượng cạnh thực sự.