Алгоритм объединения / объединения двух отдельных графиков?

Question

Мне нужен алгоритм для объединения или объединения в графы, под этим я подразумеваю, что последний узел графа 1 должен быть предшественником первого узла графа 2. График 1:

1->2->3
   \ /
    4->5

График 2:

6->7
   | \
   8->9

Вот что мне нужно:

1->2->3
   \ /
    4->5->6->7
             | \
             8->9

Answer 1

createNewGraph повторить график 1 и добавить новый график итерационный график 1 для каждого узла повторяется получатель для каждого ребра между этими узлами добавьте в новый граф

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

добавить ребро от последнего узла графа 1 к первому узлу графа 2

Answer 2

Это полностью зависит от того, как вы представляете графики.Например, если узлы пронумерованы, как в вашем примере (1..N для первого графика, N+1..M для второго графика), все, что вам нужно сделать, это создать новый график, скопировать оба ваших графика в новый,и добавьте ребро N,N+1 к нему.

Answer 3

1. Сканирование вершин графа 1 и поиск вершины outdegree ноль.
2. Сканирование вершин графа 2 и поиск вершины indegree ноль.
3. Соедините две вершины дугой.

В зависимости от графиков решение может быть или не быть уникальным (оно уникально в приведенном вами примере).