Как найти наибольшую связанную область графика или матрицы в Python?

Question

Я боролся с этим в течение нескольких дней, и в Python нет способа сделать «int [] []» для матрицы в JAVA. Моя первая мысль - использовать метод DFS для исчерпания пути. В программе я установил путь для рекурсии. Тем не менее, не существует способа всегда иметь путь, это означает, что я должен перебрать все остальные узлы в представленном графе. Я новичок в программировании, код может быть WET.

Моя идея такова:

1. Если текущая вершина равна 1, используйте DFS, чтобы исчерпать путь и считать его, если есть путь.
2. Если текущая вершина равна 0, найдите следующий узел и повторите первый шаг.

Вот мой код (неполный)

def dfs_explore(graph, current_vertex, visited_x= None, visited_y = None):
if visited_x is None:
    visited_x = []
if visited_x is None:
    visited_y = []

stack_x = []
stack_y = []

rows = len(graph)
cols = len(graph[0]) if rows else 0

if not (visited_x and visted_y):
    for x in range(cols):
        for y in range(rows):
            if graph[x][y] != 0:
                stack_x.append(x) # the column neighbours
                stack_y.append(y)
                visited.append(x)
                visited.append(y)
                path = dfs_explore(graph, graph[x][y], visited_x, visited_y)
                if path:
                    return path
                else not path:
                    stack_x.pop()
                    stack_y.pop()

Answer 1

Если вы просто хотите преобразовать код Java из примера, можно использовать Numpy:

import numpy as np

dim_x = 5
dim_y = 4

#initialize with zeros
visited = np.zeros((dim_y, dim_x))

visited[3][3] = 1

print(visited)

Другой вариант - использовать простой вложенный список («2d список») :

dim_x = 5
dim_y = 4

#initialize with zeros
visited = [[0 for _x in range(dim_x)] for _y in range(dim_y)]

visited[3][3] = 1

print(visited)

Вы можете взглянуть на NetworkX. Есть функции, которые, кажется, делают то, что вам нужно, например, connected_component_subgraphs ( Пример 1 , Пример 2 )

Вам может понадобиться функция для рассчитать выпуклую оболочку узлов, есть несколько доступных, но я не уверен, есть ли в NetworkX такой.