from collections import deque
# use deque instead of [] in python to implement queue
edges = [[0,1],[0,2],[1,2],[1,3],[1,4],[4,5],[6,7]]
Copyright By PowCoder代写 加微信 powcoder
# create adjacency list
adj_list = [[] for j in range(n)]
for edge in edges:
adj_list[edge[0]].append(edge[1])
adj_list[edge[1]].append(edge[0])
# create CSR
offset = [0]*(n+1);
csr_edges = [];
for i in range(n):
offset[i] = len(csr_edges)
csr_edges.extend(adj_list[i])
offset[n] = len(csr_edges)
def BFS(u):
visited = [False] * n
# initialize an boolean array / bitmap
queue = deque()
queue.append(u)
visited[u] = True
while queue:
s = queue.popleft()
# time complexity is expected to be O(1), [].pop(0) takes O(n) in the worst case
# 99% scenarios, never user [].pop(0)
for i in range(offset[s],offset[s+1]):
nbr_of_s = csr_edges[i]
if visited[nbr_of_s]: continue
queue.append(nbr_of_s)
visited[nbr_of_s] = True
# DFS recursive
visited = [False] * n
def DFS_recursive(u):
visited[u] = True
for i in range(offset[u],offset[u+1]):
nbr_of_u = csr_edges[i]
if visited[nbr_of_u]: continue
DFS_recursive(nbr_of_u)
# DFS_recursive(0)
# DFS iterative / stack-based
def DFS_iterative(u):
visited = [False] * n
# initialize an boolean array / bitmap
stack = []
stack.append(u)
visited[u] = True
while stack:
s = stack.pop()
for i in range(offset[s],offset[s+1]):
nbr_of_s = csr_edges[i]
if visited[nbr_of_s]: continue
stack.append(nbr_of_s)
visited[nbr_of_s] = True
# DFS_iterative(0)
# naive method to compute all connected components
def naive_cc():
unvisited = [i for i in range(n)]
# id form 0 to n-1
result = []
while unvisited:
u = unvisited.pop()
current_cc = []
queue = deque()
queue.append(u)
while queue:
s = queue.popleft()
current_cc.append(s)
for i in range(offset[s],offset[s+1]):
nbr_of_s = csr_edges[i]
if nbr_of_s in unvisited:
# scan the whole list to find the item: O(n)
queue.append(nbr_of_s)
unvisited.remove(nbr_of_s)
# O(n) like pop(0)
result.append(current_cc)
return result
# print(naive_cc())
# an improved algorithm to computed connected components, time complexity: O(m)
result = []
visited = [False]*n
for i in range(n):
if visited[i]: continue
current_cc = []
queue = deque()
queue.append(i)
visited[i] = True
current_cc.append(i)
while queue:
s = queue.popleft()
for j in range(offset[s],offset[s+1]):
nbr_of_s = csr_edges[j]
if visited[nbr_of_s]: continue
queue.append(nbr_of_s)
visited[nbr_of_s] = True
current_cc.append(nbr_of_s)
result.append(current_cc)
return result
# print(cc())
### disjoint set data structure for n items
parent = [i for i in range(n)]
size = [1 for i in range(n)]
def find(x):
# path compression
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x,y):
x = find(x)
y = find(y)
# union by tree size
if size[x] < size[y]:
size[y] += size[x]
parent[x] = y
size[x] += size[y]
parent[y] = x
### using disjoint set to compute all connected components
def ds_cc():
for edge in edges:
union(edge[0],edge[1])
# print(find(1) == find(2))
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com