合并/连接两个独立的图的算法？

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. 扫描图1的顶点，找到outdegree 0的顶点。
2. 扫描图2的顶点，找到indegree 0的顶点。
3. 用圆弧连接这两个顶点。

根据图表的不同，解决方案可能是唯一的，也可能不是唯一的(在您给出的示例中是唯一的)。

Answer 3

这完全取决于您如何表示图形。例如，如果节点编号如示例中所示(第一个图为1..N，第二个图为N+1..M )，则只需创建一个新图，将两个图复制到新图中，然后向其中添加边N,N+1。