Đồ thị khoa học viễn tưởng
Làm việc với đồ thị
Đồ thị là một cấu trúc dữ liệu thiết yếu.
SciPy cung cấp cho chúng ta mô-đun scipy.sparse.csgraph để làm việc với các cấu trúc dữ liệu như vậy.
Ma trận kề
Ma trận kề là ma trận nxn trong đó n là số phần tử của đồ thị.
Và các giá trị thể hiện sự kết nối giữa các phần tử.
Ví dụ:
Đối với một biểu đồ như thế này, với các phần tử A, B và C, các kết nối là:
A & B được kết nối với trọng số 1.
A & C được kết nối với trọng số 2.
C & B không được kết nối.
Ma trận điều chỉnh sẽ trông như thế này:
ABC
Đ:[0 1 2]
B:[1 0 0]
C:[2 0 0]
Dưới đây là một số phương pháp được sử dụng nhiều nhất để làm việc với ma trận kề.
Các thành phần được kết nối
Tìm tất cả các thành phần được kết nối bằng phương thứcconnected_components() .Ví dụ
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
arr = np.array([
[0, 1, 2],
[1, 0, 0],
[2, 0, 0]
])
newarr = csr_matrix(arr)
print(connected_components(newarr)) Hãy tự mình thử » Dijkstra
Sử dụng phương pháp dijkstra để tìm đường đi ngắn nhất trong biểu đồ từ phần tử này sang phần tử khác.
Phải mất các đối số sau:
- return_predecessors: boolean (Đúng để trả về toàn bộ đường đi nếu không là Sai).
- chỉ mục: chỉ mục của phần tử để trả về tất cả các đường dẫn từ phần tử đó.
- giới hạn: trọng lượng tối đa của đường dẫn.
Ví dụ
Tìm đường đi ngắn nhất từ phần tử 1 đến phần tử 2:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
arr = np.array([
[0, 1, 2],
[1, 0, 0],
[2, 0, 0]
])
newarr = csr_matrix(arr)
print(dijkstra(newarr, return_predecessors=True, indices=0)) Hãy tự mình thử »Floyd Warshall
Sử dụng phương thức floyd_warshall() để tìm đường đi ngắn nhất giữa tất cả các cặp phần tử.
Ví dụ
Tìm đường đi ngắn nhất giữa tất cả các cặp phần tử:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix
arr = np.array([
[0, 1, 2],
[1, 0, 0],
[2, 0, 0]
])
newarr = csr_matrix(arr)
print(floyd_warshall(newarr, return_predecessors=True)) Hãy tự mình thử »Bellman Ford
Phương thức bellman_ford() cũng có thể tìm đường đi ngắn nhất giữa tất cả các cặp phần tử, nhưng phương thức này cũng có thể xử lý các trọng số âm.
Ví dụ
Tìm đường đi ngắn nhất từ phần tử 1 đến phần tử 2 với đồ thị đã cho có trọng số âm:
import numpy as np
from scipy.sparse.csgraph import bellman_ford
from scipy.sparse import csr_matrix
arr = np.array([
[0, -1, 2],
[1, 0, 0],
[2, 0, 0]
])
newarr = csr_matrix(arr)
print(bellman_ford(newarr, return_predecessors=True, indices=0)) Hãy tự mình thử »Độ sâu thứ tự đầu tiên
Phương thức depth_first_order() trả về độ sâu truyền tải đầu tiên từ một nút.
Hàm này có các đối số sau:
- đồ thị.
- phần tử bắt đầu để duyệt đồ thị từ đó.
Ví dụ
Duyệt qua độ sâu của biểu đồ trước cho ma trận kề đã cho:
import numpy as np
from scipy.sparse.csgraph import depth_first_order
from scipy.sparse import csr_matrix
arr = np.array([
[0, 1, 0, 1],
[1, 1, 1, 1],
[2, 1, 1, 0],
[0, 1, 0, 1]
])
newarr = csr_matrix(arr)
print(depth_first_order(newarr, 1)) Hãy tự mình thử »Thứ tự chiều rộng đầu tiên
Phương thức breadth_first_order() trả về lần truyền tải theo chiều rộng đầu tiên từ một nút.
Hàm này có các đối số sau:
- đồ thị.
- phần tử bắt đầu để duyệt đồ thị từ đó.
Ví dụ
Duyệt qua chiều rộng đồ thị trước cho ma trận kề đã cho:
import numpy as np
from scipy.sparse.csgraph import breadth_first_order
from scipy.sparse import csr_matrix
arr = np.array([
[0, 1, 0, 1],
[1, 1, 1, 1],
[2, 1, 1, 0],
[0, 1, 0, 1]
])
newarr = csr_matrix(arr)
print(breadth_first_order(newarr, 1)) Hãy tự mình thử » 