Hướng dẫn graph algorithm with python - thuật toán đồ thị với python

Trong blog này, chúng tôi sẽ thảo luận về một vài thuật toán biểu đồ phổ biến và việc triển khai Python của chúng. Các vấn đề được thảo luận ở đây xuất hiện dưới dạng bài tập lập trình trong khóa học Coursera & nbsp; thuật toán trên biểu đồ & nbsp; và on & nbsp; rosalind. Các tuyên bố vấn đề được lấy từ chính khóa học.

Các khối xây dựng cơ bản của các thuật toán đồ thị như tính toán số lượng thành phần được kết nối, kiểm tra xem có đường dẫn giữa hai đỉnh đã cho hay không, kiểm tra xem có chu kỳ hay không, v.v. Các đường dẫn ngắn nhất trên bản đồ, phân tích mạng xã hội, phân tích dữ liệu sinh học.

Đối với tất cả các vấn đề, có thể giả định rằng biểu đồ đầu vào đã cho là đơn giản, tức là, nó không chứa các vòng lặp tự (các cạnh đi từ đỉnh đến chính nó) và các cạnh song song.

Kiểm tra xem hai đỉnh có thể truy cập được không

Cho một biểu đồ không mong muốn g = (v, e) và hai đỉnh riêng biệt 𝑢 và 𝑣, kiểm tra xem có đường dẫn giữa 𝑢 và 𝑣.

Các bước

1. Bắt đầu từ nút U, chúng ta chỉ có thể sử dụng tìm kiếm đầu tiên (BFS) hoặc tìm kiếm sâu (DFS) để khám phá các nút có thể truy cập từ u.
2. Ngay khi chúng tôi tìm thấy V, chúng tôi có thể trả lại các nút có thể truy cập được từ một người khác.
3. Nếu V không có trong các nút được khám phá, chúng ta có thể kết luận v không thể truy cập được từ u.
4. Việc triển khai sau (được chứng minh bằng cách sử dụng các hình ảnh động sau) sử dụng DFS lặp (có ngăn xếp) để kiểm tra xem hai nút (ban đầu màu hồng có màu) có thể truy cập được không.
5. Chúng tôi có thể tùy chọn triển khai & nbsp; tô màu & nbsp; của các nút w.r.t. Quy ước sau: Ban đầu các nút là tất cả & nbsp; màu trắng, khi chúng được truy cập (được đẩy lên ngăn xếp), chúng được đánh dấu là & nbsp; Gray & nbsp; và cuối cùng khi tất cả các nút liền kề (trẻ em) cho một nút đã cho được truy cập, nút có thể được đánh dấu & NBSP ;màu đen.coloring of the nodes w.r.t. the following convention: initially the nodes are all white, when they are visited (pushed onto stack) they are marked as gray and finally when all the adjacent (children) nodes for a given node are visited, the node can be marked black.
6. Chúng ta có thể lưu trữ cha mẹ của từng nút trong một mảng và chúng ta có thể trích xuất đường dẫn giữa hai nút đã cho bằng mảng cha mẹ, nếu chúng có thể truy cập được.

Một triển khai Python rất cơ bản của DFS lặp được hiển thị bên dưới (ở đây adj đại diện cho biểu diễn danh sách kề của biểu đồ đầu vào):

def reach(adj, x, y): 
 visited = [False]*len(adj)
 stack = [x]
 visited[x] = True
 while len(stack) > 0:
  u = stack.pop(-1)
  for v in adj[u]:
   if not visited[v]:
    stack.append(v)
    visited[v] = True
    if v == y:
     return 1
 return 0
Các hình ảnh động sau đây cho thấy cách thức hoạt động của thuật toán, & nbsp; stack & nbsp; cũng được hiển thị tại các thời điểm khác nhau trong quá trình thực hiện. Cuối cùng, đường dẫn giữa các nút được hiển thị nếu chúng có thể truy cập được.stack is also shown at different points in time during the execution. Finally the path between the nodes are shown if they are reachable.
Thuật toán tương tự có thể được sử dụng để tìm một lối thoát từ mê cung (kiểm tra xem có đường dẫn từ một ô nhất định đến một lối thoát nhất định).
Tìm các thành phần được kết nối trong một biểu đồ không được mong muốn
Đưa ra một biểu đồ không mong muốn với các đỉnh và cạnh, tính toán số lượng các thành phần được kết nối trong đó.
Các bước

Bắt đầu từ nút U, chúng ta chỉ có thể sử dụng tìm kiếm đầu tiên (BFS) hoặc tìm kiếm sâu (DFS) để khám phá các nút có thể truy cập từ u.
Ngay khi chúng tôi tìm thấy V, chúng tôi có thể trả lại các nút có thể truy cập được từ một người khác.
Nếu V không có trong các nút được khám phá, chúng ta có thể kết luận v không thể truy cập được từ u.
Việc triển khai sau (được chứng minh bằng cách sử dụng các hình ảnh động sau) sử dụng DFS lặp (có ngăn xếp) để kiểm tra xem hai nút (ban đầu màu hồng có màu) có thể truy cập được không.
Chúng tôi có thể tùy chọn triển khai & nbsp; tô màu & nbsp; của các nút w.r.t. Quy ước sau: Ban đầu các nút là tất cả & nbsp; màu trắng, khi chúng được truy cập (được đẩy lên ngăn xếp), chúng được đánh dấu là & nbsp; Gray & nbsp; và cuối cùng khi tất cả các nút liền kề (trẻ em) cho một nút đã cho được truy cập, nút có thể được đánh dấu & NBSP ;màu đen.
Chúng ta có thể lưu trữ cha mẹ của từng nút trong một mảng và chúng ta có thể trích xuất đường dẫn giữa hai nút đã cho bằng mảng cha mẹ, nếu chúng có thể truy cập được.
Hình ảnh được chụp từ ghi chú bài giảng này & nbsp;
Một triển khai Python rất cơ bản của DFS lặp được hiển thị bên dưới (ở đây adj đại diện cho biểu diễn danh sách kề của biểu đồ đầu vào):
The same algorithm can be used to decide that there are no dead zones in a maze, that is, that at least one exit is reachable from each cell.
Các hình ảnh động sau đây cho thấy cách thức hoạt động của thuật toán, & nbsp; stack & nbsp; cũng được hiển thị tại các thời điểm khác nhau trong quá trình thực hiện. Cuối cùng, đường dẫn giữa các nút được hiển thị nếu chúng có thể truy cập được.
Thuật toán tương tự có thể được sử dụng để tìm một lối thoát từ mê cung (kiểm tra xem có đường dẫn từ một ô nhất định đến một lối thoát nhất định).
Các bước
Bắt đầu từ nút U, chúng ta chỉ có thể sử dụng tìm kiếm đầu tiên (BFS) hoặc tìm kiếm sâu (DFS) để khám phá các nút có thể truy cập từ u.
Ngay khi chúng tôi tìm thấy V, chúng tôi có thể trả lại các nút có thể truy cập được từ một người khác.
Nếu V không có trong các nút được khám phá, chúng ta có thể kết luận v không thể truy cập được từ u.
Việc triển khai sau (được chứng minh bằng cách sử dụng các hình ảnh động sau) sử dụng DFS lặp (có ngăn xếp) để kiểm tra xem hai nút (ban đầu màu hồng có màu) có thể truy cập được không.
Chúng tôi có thể tùy chọn triển khai & nbsp; tô màu & nbsp; của các nút w.r.t. Quy ước sau: Ban đầu các nút là tất cả & nbsp; màu trắng, khi chúng được truy cập (được đẩy lên ngăn xếp), chúng được đánh dấu là & nbsp; Gray & nbsp; và cuối cùng khi tất cả các nút liền kề (trẻ em) cho một nút đã cho được truy cập, nút có thể được đánh dấu & NBSP ;màu đen.
Chúng ta có thể lưu trữ cha mẹ của từng nút trong một mảng và chúng ta có thể trích xuất đường dẫn giữa hai nút đã cho bằng mảng cha mẹ, nếu chúng có thể truy cập được.
Hình ảnh được chụp từ ghi chú bài giảng này & nbsp;path is meant to indicate tour). We shall use DFS to find Euler tour.
Hình ảnh được tạo từ video YouTube được trích dẫn bên trong hình ảnh
Các đoạn mã sau đây đại diện cho các chức năng được sử dụng để tìm tour Euler trong một biểu đồ. Ở đây, các biến N và M đại diện cho số lượng các đỉnh và cạnh của máy tính đầu vào, tương ứng, trong khi ADJ đại diện cho danh sách kề tương ứng.
Mã Python
def count_in_out_degrees(adj):
 n = len(adj)
 in_deg, out_deg = [0]*n, [0]*n
 for u in range(n):
  for v in adj[u]:
   out_deg[u] += 1
   in_deg[v] += 1
 return in_deg, out_degdef get_start_if_Euler_tour_present(in_deg, out_deg):
 start, end, tour = None, None, True
 for i in range(len(in_deg)): 
  d = out_deg[i] - in_deg[i]
  if abs(d) > 1:
   tour = False
   break
  elif d == 1:
   start = i
  elif d == -1:
   end = i
 tour = (start != None and end != None) or \
        (start == None and end == None)
 if tour and start == None: # a circuit
  start = 0
 return (tour, start)def dfs(adj, v, out_deg, tour):
 while out_deg[v] > 0:
  out_deg[v] -= 1
  dfs(adj, adj[v][out_deg[v]], out_deg, tour)
 tour[:] = [v] + tourdef compute_Euler_tour(adj):
 n, m = len(adj), sum([len(adj[i]) for i in range(len(adj))])
 in_deg, out_deg = count_in_out_degrees(adj)
 tour_present, start = get_start_if_Euler_tour_present(in_deg, \
                                                       out_deg)
 if not tour_present:
  return None
 tour = []
 dfs(adj, start, out_deg, tour)
 if len(tour) == m+1:
  return tour
return None
Các hình ảnh động sau đây cho thấy cách thức hoạt động của thuật toán.
Phát hiện chu kỳ trong biểu đồ có hướng
Kiểm tra xem một biểu đồ có hướng nhất định với các đỉnh và cạnh 𝑚 có chứa chu kỳ không.
Hình dưới đây cho thấy việc phân loại các cạnh gặp trong DFS:
Hình ảnh được chụp từ ghi chú bài giảng này & nbsp;
Có thể chỉ ra rằng liệu một biểu đồ có hướng có phải là acyclic (DAG) hay không (nghĩa là nó chứa một chu kỳ), có thể được kiểm tra bằng cách sử dụng sự hiện diện của một cạnh trong khi DFS đi ngang.
Các bước
Sử dụng triển khai DFS đệ quy (mã giả được hiển thị trong hình dưới đây)
Theo dõi nếu một nút được truy cập đã có trên ngăn xếp, nếu nó ở đó, nó tạo thành một cạnh sau.
Sử dụng mảng cha mẹ để có được chu kỳ theo hướng, nếu được tìm thấy.
Hình ảnh được chụp từ ghi chú bài giảng này & nbsp;
Có thể chỉ ra rằng liệu một biểu đồ có hướng có phải là acyclic (DAG) hay không (nghĩa là nó chứa một chu kỳ), có thể được kiểm tra bằng cách sử dụng sự hiện diện của một cạnh trong khi DFS đi ngang.
def cyclic(adj):
 n = len(adj)
 visited = [False]*n
 parents = [None]*n
 on_stack = [False]*n
 cycle = []
 
 def dfs_visit(adj, u, cycle):
  visited[u] = True
  on_stack[u] = True
  for v in adj[u]:
   if not visited[v]:
    parents[v] = u
    dfs_visit(adj, v, cycle)
   elif on_stack[v]:
    x = u
    while x != v:
     cycle.append(x)
     x = parents[x]
    cycle = [v] + cycle
    #print(cycle)    
  on_stack[u] = False
  
 for v in range(n):
  if not visited[v]:
   dfs_visit(adj, v, cycle)
 
 return int(len(cycle) > 0)


Các bước
Sử dụng triển khai DFS đệ quy (mã giả được hiển thị trong hình dưới đây)
Theo dõi nếu một nút được truy cập đã có trên ngăn xếp, nếu nó ở đó, nó tạo thành một cạnh sau.
Sử dụng mảng cha mẹ để có được chu kỳ theo hướng, nếu được tìm thấy.
Mã Python
Thuật toán trên có thể được sử dụng để kiểm tra tính nhất quán trong chương trình giảng dạy (ví dụ: không có sự phụ thuộc theo chu kỳ trong các điều kiện tiên quyết cho mỗi khóa học được liệt kê).
Đặt hàng về mặt cấu trúc một biểu đồ theo hướng
Repeat.
Tính toán một thứ tự tôpô của một biểu đồ acyclic có hướng nhất định (DAG) với các đỉnh và cạnh.
Các bước
Sử dụng triển khai DFS đệ quy (mã giả được hiển thị trong hình dưới đây)
Theo dõi nếu một nút được truy cập đã có trên ngăn xếp, nếu nó ở đó, nó tạo thành một cạnh sau.
Sử dụng mảng cha mẹ để có được chu kỳ theo hướng, nếu được tìm thấy.
Hình ảnh được chụp từ ghi chú bài giảng này & nbsp;
Có thể chỉ ra rằng liệu một biểu đồ có hướng có phải là acyclic (DAG) hay không (nghĩa là nó chứa một chu kỳ), có thể được kiểm tra bằng cách sử dụng sự hiện diện của một cạnh trong khi DFS đi ngang.
Các bước
The above algorithm can be used to determine the order of the courses in a curriculum, taking care of the pre-requisites dependencies.
Sử dụng triển khai DFS đệ quy (mã giả được hiển thị trong hình dưới đây)
Theo dõi nếu một nút được truy cập đã có trên ngăn xếp, nếu nó ở đó, nó tạo thành một cạnh sau.
Sử dụng mảng cha mẹ để có được chu kỳ theo hướng, nếu được tìm thấy.
Mã Python
Thuật toán trên có thể được sử dụng để kiểm tra tính nhất quán trong chương trình giảng dạy (ví dụ: không có sự phụ thuộc theo chu kỳ trong các điều kiện tiên quyết cho mỗi khóa học được liệt kê).
Đặt hàng về mặt cấu trúc một biểu đồ theo hướng
Tính toán một thứ tự tôpô của một biểu đồ acyclic có hướng nhất định (DAG) với các đỉnh và cạnh.
Ý tưởng sau đây có thể được sử dụng để có được một đơn đặt hàng như vậy trong Digraph G:
Tìm bồn rửa.
Đặt ở cuối trật tự.
Hình ảnh được chụp từ ghi chú bài giảng này & nbsp;
Có thể chỉ ra rằng liệu một biểu đồ có hướng có phải là acyclic (DAG) hay không (nghĩa là nó chứa một chu kỳ), có thể được kiểm tra bằng cách sử dụng sự hiện diện của một cạnh trong khi DFS đi ngang.
Các bước
Mã Python
def number_of_strongly_connected_components(adj):
 result = 0
 visited = [False]*n
 previsit = [0]*n
 postvisit = [0]*n
 
 def reverse_graph(adj):
  n = len(adj)
  new_adj = [ [] for _ in range(n)]
  for i in range(n):
   for j in adj[i]:
    new_adj[j].append(i)
  return new_adj
 
 def dfs_visit(adj, u):
  global clock
  visited[u] = True
  previsit[u] = clock
  clock += 1
  for v in adj[u]:
   if not visited[v]:
    dfs_visit(adj, v)
  postvisit[u] = clock
  clock += 1
 
 for v in range(n):
  if not visited[v]:
   dfs_visit(adj, v)
 post_v = [x for _, x in sorted(zip(postvisit, range(n)), \
                   key=lambda pair: pair[0], reverse=True)]
 rev_adj = reverse_graph(adj)
 visited = [False]*n
 for v in post_v:
  if not visited[v]:
   dfs_visit(rev_adj, v)
   result += 1return result
Sử dụng triển khai DFS đệ quy (mã giả được hiển thị trong hình dưới đây)
Theo dõi nếu một nút được truy cập đã có trên ngăn xếp, nếu nó ở đó, nó tạo thành một cạnh sau.
Sử dụng mảng cha mẹ để có được chu kỳ theo hướng, nếu được tìm thấy.
Mã Python
Thuật toán trên có thể được sử dụng để kiểm tra tính nhất quán trong chương trình giảng dạy (ví dụ: không có sự phụ thuộc theo chu kỳ trong các điều kiện tiên quyết cho mỗi khóa học được liệt kê).
Đặt hàng về mặt cấu trúc một biểu đồ theo hướng
Tính toán một thứ tự tôpô của một biểu đồ acyclic có hướng nhất định (DAG) với các đỉnh và cạnh.
Hình ảnh được chụp từ ghi chú bài giảng này & nbsp;
Có thể chỉ ra rằng liệu một biểu đồ có hướng có phải là acyclic (DAG) hay không (nghĩa là nó chứa một chu kỳ), có thể được kiểm tra bằng cách sử dụng sự hiện diện của một cạnh trong khi DFS đi ngang.
def distance(adj, s, t):
 inf = 10**9 #float('Inf')
 d = [inf]*len(adj)
 queue = [s]
 d[s] = 0
 while len(queue) > 0:
  u = queue.pop(0)
  for v in adj[u]:
   if d[v] ==  inf:
    queue.append(v)
    d[v] = d[u] + 1
    if v == t:
     return d[t]
 return -1
Các bước

Sử dụng triển khai DFS đệ quy (mã giả được hiển thị trong hình dưới đây)
Theo dõi nếu một nút được truy cập đã có trên ngăn xếp, nếu nó ở đó, nó tạo thành một cạnh sau.
Sử dụng mảng cha mẹ để có được chu kỳ theo hướng, nếu được tìm thấy.
Các bước
Sử dụng triển khai DFS đệ quy (mã giả được hiển thị trong hình dưới đây)
Theo dõi nếu một nút được truy cập đã có trên ngăn xếp, nếu nó ở đó, nó tạo thành một cạnh sau.
Nếu tại bất kỳ thời điểm nào, hai đỉnh liền kề được tìm thấy được tô màu bằng cùng một màu, thì biểu đồ không phải là 2 màu (do đó không phải là bipartite).
Nếu không có trường hợp nào xảy ra, thì biểu đồ là lưỡng cực
Đối với một biểu đồ có nhiều thành phần, hãy sử dụng BFS trên mỗi thành phần của chúng.
Ngoài ra, lưu ý rằng một biểu đồ là IFF lưỡng cực, nó chứa một chu kỳ chiều dài lẻ.
Mã Python
def bipartite(adj):
 color = [None]*len(adj)
 for vertex in range(len(adj)):
  if not color[vertex]:
   queue = [vertex]
   color[vertex] = 'red'
   while len(queue) > 0:
    u = queue.pop(0)
    for v in adj[u]:
     if color[v] ==  color[u]:
      return 0
     if not color[v]:
      queue.append(v)
      color[v] = 'red' if color[u] == 'blue' else 'blue'
 return 1
Các hình ảnh động sau đây cho thấy cách thức hoạt động của thuật toán.
Lưu ý rằng biểu đồ cuối cùng chứa chiều dài của chu kỳ 4 (chẵn chu kỳ chiều dài) và đó là biểu đồ lưỡng cực. Biểu đồ trước đây chứa một tam giác trong đó (chu kỳ có chiều dài lẻ 3), nó không phải là lưỡng cực.
Đường dẫn ngắn nhất trong một biểu đồ có trọng số với dijkstra
Cho một biểu đồ có hướng với trọng lượng cạnh dương và với các đỉnh và cạnh cũng như hai đỉnh 𝑢 và 𝑣, tính toán trọng lượng của một đường dẫn ngắn nhất giữa 𝑢 và 𝑣 (nghĩa là tổng trọng lượng tối thiểu của một đường dẫn từ 𝑢 đến 𝑣 ).
Thuộc tính cấu trúc tối ưu: Bất kỳ đường dẫn phụ của một đường dẫn tối ưu cũng là tối ưu.
Ban đầu, chúng tôi chỉ biết khoảng cách đến nguồn S và thư giãn tất cả các cạnh từ S.
Duy trì một bộ R của các đỉnh mà dist đã được đặt chính xác (vùng đã biết).
Trên mỗi lần lặp có một đỉnh bên ngoài R với giá trị dist tối thiểu, thêm nó vào R và thư giãn tất cả các cạnh hướng dẫn của nó.
Hình tiếp theo cho thấy mã giả của thuật toán.
Thuật toán hoạt động cho bất kỳ biểu đồ nào có trọng số cạnh không âm.
Thuật toán không hoạt động nếu biểu đồ đầu vào có trọng số cạnh âm (vùng đã biết có giả định rằng DIST có thể giảm hơn nữa, giả định này không giữ được nếu biểu đồ có các cạnh âm).
Hình ảnh được tạo từ ghi chú bài giảng này & nbsp;
Mã Python
import queue

def distance(adj, cost, s, t):
 inf = 10**19
 n = len(adj)
 d = [inf]*n
 d[s] = 0
 visited = [0]*n
 h = queue.PriorityQueue()
 for v in range(n):
  h.put((d[v], v))
 while not h.empty():
  u = h.get()[1]
  if visited[u]: continue
  visited[u] = True
  for i in range(len(adj[u])):
   v = adj[u][i]
   if d[v] > d[u] + cost[u][i]:
    d[v] = d[u] + cost[u][i]
    h.put((d[v], v))
 return d[t] if d[t] != inf else -1
Các hình ảnh động sau đây cho thấy cách thức hoạt động của thuật toán.
Lưu ý rằng biểu đồ cuối cùng chứa chiều dài của chu kỳ 4 (chẵn chu kỳ chiều dài) và đó là biểu đồ lưỡng cực. Biểu đồ trước đây chứa một tam giác trong đó (chu kỳ có chiều dài lẻ 3), nó không phải là lưỡng cực.
Đường dẫn ngắn nhất trong một biểu đồ có trọng số với dijkstra
Cho một biểu đồ có hướng với trọng lượng cạnh dương và với các đỉnh và cạnh cũng như hai đỉnh 𝑢 và 𝑣, tính toán trọng lượng của một đường dẫn ngắn nhất giữa 𝑢 và 𝑣 (nghĩa là tổng trọng lượng tối thiểu của một đường dẫn từ 𝑢 đến 𝑣 ).
Thuộc tính cấu trúc tối ưu: Bất kỳ đường dẫn phụ của một đường dẫn tối ưu cũng là tối ưu.
Ban đầu, chúng tôi chỉ biết khoảng cách đến nguồn S và thư giãn tất cả các cạnh từ S.
Duy trì một bộ R của các đỉnh mà dist đã được đặt chính xác (vùng đã biết).
Trên mỗi lần lặp có một đỉnh bên ngoài R với giá trị dist tối thiểu, thêm nó vào R và thư giãn tất cả các cạnh hướng dẫn của nó.
Hình ảnh được tạo từ ghi chú bài giảng này & nbsp;
Các hình ảnh động sau đây cho thấy cách thức hoạt động của thuật toán.
Thuật toán cũng hoạt động cho các biểu đồ không mong muốn là tốt. Các hình ảnh động sau đây cho thấy đường dẫn ngắn nhất có thể được tìm thấy trên các biểu đồ không mong muốn.
Phát hiện chu kỳ âm trong biểu đồ có hướng với Bellman-Ford
Cho một biểu đồ có hướng với trọng lượng cạnh có thể âm và với các cạnh và cạnh, kiểm tra xem nó có chứa một chu kỳ có trọng lượng âm hay không. Ngoài ra, được đưa ra một đỉnh 𝑠, tính toán độ dài của các đường dẫn ngắn nhất từ ​​𝑠 đến tất cả các đỉnh khác của biểu đồ.
Đối với một máy tính có n nút N (không có chu kỳ âm), độ dài đường dẫn ngắn nhất ở giữa hai nút (ví dụ: nút nguồn và bất kỳ nút nào khác) có thể là nhiều nhất & nbsp; n-1.
Thư giãn các cạnh trong khi thay đổi dist (nhiều nhất là N-1, hầu hết các lần khoảng cách sẽ ngừng thay đổi nhiều trước đó).
Thuật toán này hoạt động ngay cả đối với trọng lượng cạnh âm.
Hình dưới đây cho thấy mã giả của thuật toán.
Thuật toán trên cũng có thể được sử dụng để phát hiện một chu kỳ âm trong biểu đồ đầu vào.
Chạy N = | V | Lặp lại thuật toán BellmanTHER DEFD (tức là, chỉ cần chạy phân hủy cạnh một lần nữa, cho thời điểm n-thời kỳ).
Nếu tồn tại một đỉnh, khoảng cách vẫn giảm, nó ngụ ý rằng tồn tại một chu kỳ trọng lượng âm trong biểu đồ và đỉnh có thể tiếp cận được từ chu kỳ đó.
Mã Python
def negative_cycle(adj, cost):
 inf = 10**19 # float('Inf')
 n = len(adj)
 d = [inf]*n
 d[0] = 0
 for k in range(n-1):
  for u in range(n):
   for i in range(len(adj[u])):
    v = adj[u][i]
    if d[v] > d[u] + cost[u][i]:
     d[v] = d[u] + cost[u][i]
 for u in range(n):
  for i in range(len(adj[u])):
   v = adj[u][i]
   if d[v] > d[u] + cost[u][i]:
    d[v] = d[u] + cost[u][i]
    return 1
 return 0
Các hình ảnh động sau đây cho thấy cách thức hoạt động của thuật toán.
Lưu ý rằng biểu đồ cuối cùng chứa chiều dài của chu kỳ 4 (chẵn chu kỳ chiều dài) và đó là biểu đồ lưỡng cực. Biểu đồ trước đây chứa một tam giác trong đó (chu kỳ có chiều dài lẻ 3), nó không phải là lưỡng cực.
Đường dẫn ngắn nhất trong một biểu đồ có trọng số với dijkstra
Cho một biểu đồ có hướng với trọng lượng cạnh dương và với các đỉnh và cạnh cũng như hai đỉnh 𝑢 và 𝑣, tính toán trọng lượng của một đường dẫn ngắn nhất giữa 𝑢 và 𝑣 (nghĩa là tổng trọng lượng tối thiểu của một đường dẫn từ 𝑢 đến 𝑣 ).
Thuộc tính cấu trúc tối ưu: Bất kỳ đường dẫn phụ của một đường dẫn tối ưu cũng là tối ưu.
Ban đầu, chúng tôi chỉ biết khoảng cách đến nguồn S và thư giãn tất cả các cạnh từ S.
Duy trì một bộ R của các đỉnh mà dist đã được đặt chính xác (vùng đã biết).
Trên mỗi lần lặp có một đỉnh bên ngoài R với giá trị dist tối thiểu, thêm nó vào R và thư giãn tất cả các cạnh hướng dẫn của nó.
Hình tiếp theo cho thấy mã giả của thuật toán.
Hình ảnh được tạo từ ghi chú bài giảng này & nbsp;
Chúng ta sẽ sử dụng thuật toán Prim Prim để tìm MST trong biểu đồ. Dưới đây là các bước thuật toán:
Nó bắt đầu với một đỉnh ban đầu và được phát triển thành một cây bao gồm X.
X luôn là một cây con, phát triển theo một cạnh ở mỗi lần lặp
Thêm một cạnh nhẹ nhất giữa một đỉnh của cây và một đỉnh không ở trong cây
Rất giống với thuật toán Dijkstra từ
Mã giả được hiển thị trong hình sau.
Hình ảnh được chụp từ ghi chú bài giảng này & nbsp;
Mã Python
def number_of_components(adj):
 result = 0
 n = len(adj)
 visited = [False]*len(adj)
 for x in range(n):
  if not visited[x]:
   result += 1
   stack = [x]
   visited[x] = True
   while len(stack) > 0:
    u = stack.pop(-1)
    for v in adj[u]:
     if not visited[v]:
      stack.append(v) 
      visited[v] = True
 return result
0
Các hình ảnh động sau đây cho thấy cách thuật toán hoạt động cho một vài điểm đầu vào khác nhau trong mặt phẳng 2 chiều.
Hai hình ảnh động sau đây cho thấy các bước thuật toán trên các điểm đầu vào và biểu đồ tương ứng được hình thành, tương ứng.

Hoạt hình sau đây cho thấy cách thuật toán Prim Prim xuất ra MST cho 36 điểm đầu vào trong lưới 6 × 6.
Đúng như dự đoán, chi phí của MCST được hình thành là 35 cho 36 điểm, vì một cây bao trùm với N nút có các cạnh N-1, mỗi cạnh có chiều dài đơn vị.
Thuật toán trên có thể được sử dụng để xây dựng các con đường giữa một số cặp thành phố đã cho sao cho có một đường dẫn giữa bất kỳ hai thành phố nào và tổng chiều dài của đường được giảm thiểu.
Tìm cây bao trùm tối thiểu và phân cụm phân cấp với Kruskal
Cho 𝑛 điểm trên mặt phẳng và số nguyên, tính giá trị lớn nhất có thể của 𝑑 sao cho các điểm đã cho có thể được phân vùng thành các tập hợp không trống theo cách mà khoảng cách giữa hai điểm từ các tập hợp khác nhau ít nhất là 𝑑 .
Các bước
Chúng tôi sẽ sử dụng thuật toán Kruskal, để giải quyết vấn đề trên. Mỗi điểm có thể được nghĩ đến một nút trong biểu đồ, như trước đó, với các trọng số cạnh giữa các nút bằng khoảng cách Euclide giữa chúng.
Bắt đầu với n thành phần, mỗi nút đại diện cho một.
Chạy các lần lặp của thuật toán Kruskal, và hợp nhất các thành phần cho đến khi có chính xác các thành phần K (
Các thành phần k này sẽ là các cụm K mong muốn của các điểm và chúng ta có thể tính d là khoảng cách lớn nhất ở giữa hai điểm thuộc về các cụm khác nhau.
Dưới đây là các bước để thuật toán Kruskal từ tính toán MST:
Bắt đầu với mỗi nút trong biểu đồ dưới dạng một cây một nút trong rừng X.
Nhiều lần thêm vào x cạnh nhẹ nhất tiếp theo mà không tạo ra một chu kỳ.
Tại bất kỳ thời điểm nào, Set X là một khu rừng (tức là, một bộ sưu tập cây)
Cạnh tiếp theo kết nối hai cây khác nhau - giả sử, T1 và T2
Các cạnh E là ánh sáng nhất giữa T1 và V / T1, do đó thêm E là an toàn
Hình ảnh được chụp từ ghi chú bài giảng này & nbsp;
Mã Python
Các hình ảnh động sau đây cho thấy cách thuật toán hoạt động cho một vài điểm đầu vào khác nhau trong mặt phẳng 2 chiều.
Hai hình ảnh động sau đây cho thấy các bước thuật toán trên các điểm đầu vào và biểu đồ tương ứng được hình thành, tương ứng.
Hoạt hình sau đây cho thấy cách thuật toán Prim Prim xuất ra MST cho 36 điểm đầu vào trong lưới 6 × 6.
Đúng như dự đoán, chi phí của MCST được hình thành là 35 cho 36 điểm, vì một cây bao trùm với N nút có các cạnh N-1, mỗi cạnh có chiều dài đơn vị.
Thuật toán trên có thể được sử dụng để xây dựng các con đường giữa một số cặp thành phố đã cho sao cho có một đường dẫn giữa bất kỳ hai thành phố nào và tổng chiều dài của đường được giảm thiểu.
Hình ảnh được tạo từ ghi chú bài giảng này & nbsp;
Mã Python
def number_of_components(adj):
 result = 0
 n = len(adj)
 visited = [False]*len(adj)
 for x in range(n):
  if not visited[x]:
   result += 1
   stack = [x]
   visited[x] = True
   while len(stack) > 0:
    u = stack.pop(-1)
    for v in adj[u]:
     if not visited[v]:
      stack.append(v) 
      visited[v] = True
 return result
1
Các hình ảnh động sau đây cho thấy cách thuật toán hoạt động cho một vài điểm đầu vào khác nhau trong mặt phẳng 2 chiều.
Hai hình ảnh động sau đây cho thấy các bước thuật toán trên các điểm đầu vào và biểu đồ tương ứng được hình thành, tương ứng.
Hoạt hình sau đây cho thấy cách thuật toán Prim Prim xuất ra MST cho 36 điểm đầu vào trong lưới 6 × 6.is a fundamental problem in data mining. The goal is to partition a given set of objects into subsets (or clusters) in such a way that any two objects from the same subset are close (or similar) to each other, while any two objects from different
subsets are far apart.
Đúng như dự đoán, chi phí của MCST được hình thành là 35 cho 36 điểm, vì một cây bao trùm với N nút có các cạnh N-1, mỗi cạnh có chiều dài đơn vị.Iris dataset (can be downloaded from the UCI Machine learning repository), often used as a test dataset in Machine learning.
Thuật toán trên có thể được sử dụng để xây dựng các con đường giữa một số cặp thành phố đã cho sao cho có một đường dẫn giữa bất kỳ hai thành phố nào và tổng chiều dài của đường được giảm thiểu.
Tìm cây bao trùm tối thiểu và phân cụm phân cấp với Kruskal
Cho 𝑛 điểm trên mặt phẳng và số nguyên, tính giá trị lớn nhất có thể của 𝑑 sao cho các điểm đã cho có thể được phân vùng thành các tập hợp không trống theo cách mà khoảng cách giữa hai điểm từ các tập hợp khác nhau ít nhất là 𝑑 .
Các bước
Gợi ý bạn bè trong mạng xã hội - Dijkstra hai chiều
Tính khoảng cách giữa một số cặp nút trong mạng.
Các bước
Xây dựng biểu đồ ngược gr
Bắt đầu dijkstra từ s trong g và từ t trong gr
Thay thế giữa các bước dijkstra trong g và trong gr
Dừng khi một số đỉnh V được xử lý cả trong G và trong GR
Tính toán đường dẫn ngắn nhất giữa s và t
Meet-in-the-middle
Ý tưởng chung hơn, không chỉ cho đồ thị
Thay vì tìm kiếm tất cả các đối tượng có thể, hãy tìm kiếm một nửa đầu tiên và cho hai nửa riêng biệt
Sau đó tìm & nbsp; tương thích & nbsp; nửa
Thông thường khoảng o (√n) thay vì o (n)
Bạn bè đề xuất trong mạng xã hội
Tìm con đường ngắn nhất từ ​​Michael đến Bob qua kết nối bạn bè
Đối với hai người xa nhất của người Viking, Dijkstra phải xem qua 2 tỷ người
Nếu chúng ta chỉ xem xét bạn bè của bạn bè cho cả Michael và Bob, chúng ta sẽ tìm thấy một kết nối
Khoảng 1 triệu người bạn của bạn bè
1m + 1m = 2m người - ít hơn 1000 lần
Dijkstra đi vào & nbsp; vòng tròncircles
Ý tưởng tìm kiếm hai chiều có thể làm giảm không gian tìm kiếm
Dijkstra hai chiều có thể nhanh hơn 1000 lần so với Dijkstra cho các mạng xã hội
Hình sau đây cho thấy thuật toán
Được tạo từ ghi chú bài giảng này & nbsp;
Hàm Python sau đây thực hiện dijkstra hai chiều, các đối số & nbsp; adj & nbsp; và & nbsp; adjr & nbsp; lần lượt đại diện cho các danh sách kề cho biểu đồ gốc và biểu đồ ngược.
Mã Python
def number_of_components(adj):
 result = 0
 n = len(adj)
 visited = [False]*len(adj)
 for x in range(n):
  if not visited[x]:
   result += 1
   stack = [x]
   visited[x] = True
   while len(stack) > 0:
    u = stack.pop(-1)
    for v in adj[u]:
     if not visited[v]:
      stack.append(v) 
      visited[v] = True
 return result
2
Hoạt hình sau đây cho thấy cách thức hoạt động của thuật toán:
Khoảng cách tính toán nhanh hơn bằng cách sử dụng tọa độ với* tìm kiếm*
Tính khoảng cách giữa một số cặp nút trong mạng. Độ dài l giữa hai nút U A V V được đảm bảo để thỏa mãn 𝑙 ≥ ((𝑥 (𝑢) - 𝑥 (𝑣)) 2 + (𝑦 (𝑢) - 𝑦 (𝑣)) 2).
Hãy nói rằng chúng tôi đang gửi một truy vấn để tìm một đường dẫn ngắn nhất giữa các nút (s, t) cho một biểu đồ.
Một hàm tiềm năng 𝜋 (v) cho một nút V trong A là ước tính của d (v, t) - nó là bao xa từ đây đến T?
Nếu chúng ta có ước tính như vậy, chúng ta thường có thể tránh đi sai hướng tìm kiếm theo hướng
Lấy một số hàm tiềm năng và chạy thuật toán dijkstra với trọng số cạnh ℓ𝜋
Đối với bất kỳ cạnh nào (u, v), độ dài mới ℓ𝜋 (u, v) phải không âm, như vậy được gọi là khả thi
Thông thường 𝜋 (v) là giới hạn thấp hơn trên d (v, t)
A* là một thuật toán tìm kiếm được định hướng dựa trên dijkstra và các chức năng tiềm năng
Chạy Dijkstra với tiềm năng 𝜋 để tìm đường dẫn ngắn nhất - thuật toán kết quả là một tìm kiếm*, được mô tả trong hình dưới đây
Trên bản đồ thực, đường dẫn từ v đến t không thể ngắn hơn đoạn đường thẳng từ v đến t
Đối với mỗi V, tính toán 𝜋 (v) = de (v, t)
Nếu 𝜋 (v) cho giới hạn dưới trên d (v, t)
Trường hợp xấu nhất: 𝜋 (v) = 0 cho tất cả v giống như dijkstra
Trường hợp tốt nhất: 𝜋 (v) = d (v, t) cho tất cả v thì ℓ𝜋 (u, v) = 0 iff (u, v) trên đường dẫn ngắn nhất đến t, do đó chỉ truy cập tìm kiếm các cạnh của s ngắn nhất - ngắn nhất - t đường dẫn
Có thể chỉ ra rằng càng chặt là giới hạn thấp hơn, ít các đỉnh sẽ được quét
Các hình ảnh động sau đây cho thấy cách thuật toán A* tìm kiếm hoạt động trên mạng đường (và các biểu diễn đồ thị tương ứng). Mỗi nút trong biểu đồ có các cặp (khoảng cách, tiềm năng) tương ứng.
Các hình ảnh hoạt hình sau đây cho thấy đường dẫn ngắn nhất được tính toán giữa hai nút cho mạng đường Hoa Kỳ cho Khu vực Vịnh San Francisco (biểu đồ tương ứng chứa 321270 nút và 800172 cạnh), sử dụng dijkstra, dijkstra hai chiều và một thuật toán*, dữ liệu có thể được tải xuống từ & NBSP; Thử thách thực hiện DIMACS thứ 9 - Đường dẫn ngắn nhất. Ở đây, với dijkstra hai chiều, các nút từ hàng đợi ưu tiên tiến và ngược được xuất hiện trong cùng một lần lặp.
Trong trung bình: https://medium.com/python-in-plain-english/graph-algorithms-with-python-1fe2f29d663c