-
Notifications
You must be signed in to change notification settings - Fork 0
/
Bipartiteness_Graph.py
45 lines (35 loc) · 1.27 KB
/
Bipartiteness_Graph.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from collections import deque
def is_bipartite(graph, start, color):
queue = deque()
color[start] = 1
queue.append(start)
while queue:
current_vertex = queue.popleft()
for neighbor in range(len(graph)):
if graph[current_vertex][neighbor] == 1:
if neighbor not in color:
color[neighbor] = 3 - color[current_vertex] # Gán màu khác với đỉnh hiện tại
queue.append(neighbor)
elif color[neighbor] == color[current_vertex]:
return False # Đồ thị không là đồ thị hai phía
return True # Đồ thị là đồ thị hai phía
def is_bipartite_graph(adj_matrix, start):
n = len(adj_matrix)
color = {} # Màu của mỗi đỉnh: 1 hoặc 2
if start not in color:
if not is_bipartite(adj_matrix, start, color):
return False
return True
# Example usage:
n = 6 # Số đỉnh
adj_matrix = [
[0, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 1, 0],
[0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 1],
[0, 0, 0, 1, 1, 0]
]
start_vertex = 0 # Đỉnh bắt đầu
result = is_bipartite_graph(adj_matrix, start_vertex)
print("Is the graph bipartite?", result)