Generating spanning tree from grid, determining if a grid is a spanning tree, searching for cycle in grid.

main.py

edges = [[1, 2], [0, 2], [0, 1, 3], [0, 2]] # grid
vertices = [1, 2, 3, 4]
# edges = [[2], [2], [0, 1, 3], [2]] # spanning tree
# vertices = [1, 2, 3, 4]
visited = [False] * len(vertices)

spanning_tree_edges = [[] for x in range(len(vertices))]


def is_spanning_tree_dfs(node, source, _edges):
    visited[node] = True

    for next_el in _edges[node]:
        if not visited[next_el]:
            if not is_spanning_tree_dfs(next_el, node, _edges):
                return False
        elif next_el == source:
            continue
        else:
            return False
    return True


def spanning_tree_dfs(node):
    visited[node] = True

    for next_el in edges[node]:
        if not visited[next_el]:
            spanning_tree_edges[node].append(next_el)
            spanning_tree_dfs(next_el)

def find_cycle_dfs(node, source, _edges):
    visited[node] = True

    for next_el in _edges[node]:
        if not visited[next_el]:
            result = find_cycle_dfs(next_el, node, _edges)
            if result[0]:
                return [True, [node] + result[1]]
        elif next_el != source:
            return [True, [node]]
    return [False, []]


if __name__ == '__main__':
    spanning_tree_dfs(0)
    print([[y + 1 for y in x] for x in spanning_tree_edges])
    visited = [False] * len(vertices)
    print(is_spanning_tree_dfs(0, 0, edges))
    visited = [False] * len(vertices)
    print(find_cycle_dfs(0, 0, edges))