количество возможных путей в графе

Question

Я должен рассчитать количество возможных путей в неориентированном графе Пример: у меня есть ненаправленный граф с 4 узлами. Вершины: 1-> 2; 2> 3; 2-> 4 . Таким образом, число возможных путей составляет 12

(1->2;  1->2->3;  1->2->4;  2->1;  2->3;  2->4;  3->2;  3->2->4...and so on);

Answer 1

Поскольку я не знаю точно, как вы написали свой код, все, что я могу вам дать, это своего рода объяснение псевдокода:

function getPathsFromNode(node)
    mark node
    c = 0;

    foreach neighbour in adjacent nodes of node
        if neighbour is not marked
            c += getPathsFromNode(neighbour) + 1

    return c


function main()
    n = 0
    foreach node in graph
        n += getPathsFromNode(node)

    print("paths = ", n)

По сути это просто DFS для каждого узла графа.