количество путей в графе

Question

как можно рассчитать количество путей в ориентированном графе? Есть ли для этого алгоритмы?

С наилучшими пожеланиями

РЕДАКТИРОВАТЬ : график не является деревом.

Answer 1

Пусть A - матрица смежности графа G. Тогда A^n (т.е. A, умноженное n раз на себя) имеет следующее интересное свойство:

Запись в позиции (i,j) из A^n равна количеству различных путей длины n от вершины i до вершины j.

Таким образом:

• представляет график в виде матрицы смежности A
• умножьте A на себя, пока вам не надоест
• на каждом шаге: вычислить сумму всех матричных элементов и добавить ее к результату, начиная с 0

Может быть, стоит сначала проверить, содержит ли G цикл, потому что в этом случае он содержит бесконечно много путей. Чтобы обнаружить циклы, установите все веса ребер на -1 и используйте Bellman-Ford.

Answer 2

Предполагая, что граф является ациклическим (DAG), вы можете выполнить топологическую сортировку вершин и затем выполнить динамическое программирование для вычисления количества различных путей.Если вы хотите напечатать все пути, нет смысла обсуждать большие нотации O, поскольку число путей может быть экспоненциальным по отношению к числу вершин.1005 * Редактировать: Ошибка на коде

Answer 3

Вы можете использовать поиск в глубину . Однако вы не прекращаете поиск, когда вы находите путь от начала до места назначения, как обычно делает поиск в глубину. Вместо этого вы просто добавляете к числу путей и возвращаетесь с этого узла, как если бы это был тупик. Вероятно, это не самый быстрый метод, но он должен работать.

Вы также можете потенциально использовать поиск в ширину, но затем вам нужно найти способ передачи информации о счетчиках пути вперед (или назад) через дерево при его поиске. Если бы вы могли это сделать, это было бы гораздо быстрее.

Answer 4

Все поисковые запросы, которые я вижу, относятся к числу путей от данного узла к другому данному узлу. Но вот алгоритм, который должен найти общее количество путей в любом месте графика, для любого ациклического орграфа. (Если есть циклы, существует бесконечное количество путей, если вы не укажете, что исключены некоторые повторяющиеся пути.)

Маркируйте каждый узел числом путей, заканчивающихся на этом узле:

While not all nodes are labeled:
  Choose an unlabeled node with no unlabeled ancestors.
    (An implementation might here choose any node, and recursively
     process any unlabeled ancestors of that node first.)
  Label the node with one plus the sum of the labels on all ancestors.
    (If a node has no ancestors, its label is simply 1.)

Теперь просто добавьте метки на все узлы.

Если вы не хотите считать пути «нулевой длины», вычтите количество узлов.

Answer 5

admat дает длину 1 пути между вершинами;

admat^2 дает длину 2 пути между вершинами;

admat^3 дает длину 3 пути между вершинами;

Определить образец еще?

Answer 6

Если граф не дерево, пути будут бесконечными - обходите цикл в любое время.

Answer 7

Если это действительно дерево, количество путей равно числу узлов-1, если вы подсчитываете пути к внутренним узлам.Если вы считаете количество путей до листьев, количество путей равно количеству листьев.Таким образом, тот факт, что мы говорим о деревьях, упрощает подсчет узлов или листьев.Достаточно простого алгоритма BFS или DFS.

Answer 8

Я не верю, что есть что-то быстрее, чем обход графика, начиная с корня.

в псевдокоде -

visit(node) {
  node.visited = true;
  for(int i = 0; i < node.paths.length; ++i) {
    ++pathCount;
    if (!node.paths[i].visited)
      visit(node.paths[i]);
  }

}