Статья Автор: Дубинин Дмитрий

Функция, которая преобразует любое представление в список смежности

def to_adjacency_list(n, m, representation, data):
    """
    representation: "edges", "matrix", "incidence"
    data: входные данные в соответствующем формате
    """
    graph = [[] for _ in range(n + 1)]
    
    if representation == "edges":
        # data - список рёбер
        for a, b in data:
            graph[a].append(b)
            graph[b].append(a)
    
    elif representation == "matrix":
        # data - матрица смежности
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if data[i][j] == 1:
                    graph[i].append(j)
    
    elif representation == "incidence":
        # data - матрица инцидентности
        for j in range(m):
            edges = []
            for i in range(1, n + 1):
                if data[i][j] == 1:
                    edges.append(i)
            if len(edges) == 2:
                a, b = edges[0], edges[1]
                graph[a].append(b)
                graph[b].append(a)
    
    return graph

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать