在我的项目中，我将给定的移动应用程序表示为有向图。移动应用程序的每个屏幕用作图形节点和从一个屏幕到下一个屏幕的边缘链接。边缘存储在每个父屏幕内。使用深度优先搜索，每个边缘也被分类为TREE，FORWARD，CROSS或BACK边缘。这一切现在都很好。
我的问题是我需要将两个图合并为一个图。这两个图表可能代表移动应用程序的不同构建。一个版本可能具有以下链：
Screen#1 -> Screen#2 -> Screen#3
下一个版本可能包含以下链：
Screen#1 -> Screen#X -> Screen#2 -> Screen#3
我需要能够合并这两个图，最终得到以下图表：
Screen#1 -> Screen#X -+
| |
+------------> Screen#2 -> Screen#3
我可以测试每个节点与每个其他节点的相等性。但我似乎无法设计出一种允许我将这两个图合并为一个的算法。
我已经在互联网上搜索了很多但是无法找到关于如何合并图表的单一网站或讲座或研究论文。我当前的实现（非常错误）是这样的：
1. Identify all nodes in graph A that also exist in graph B (S#1, S#2, S#3)
2. Copy all of these nodes in the final tree..
3. For each of these common nodes, recursively explore their children..
4. If the child exists in the resultant tree, add an edge between the parent and the child. Otherwise, add the child and an edge between the parent and child and repeat the algorithm on the child itself.
5. Do this till there are no unvisited nodes left.
有人能指出我在合并这些图表时应该采用的方法吗？请注意，这两个图表可能是循环的。
谢谢，Asim
由于您尚未发布Minimal, Complete, and Verifiable example，因此这里的答案可能不完全适合您的用例。希望你还可以使用它：
我建议您将图表表示为一组节点数据，其节点由字符串标签标识，旁边还有一组节点标签来表示边缘。像这样的东西：
// T represents the data type, K represents the union of node labels
class Graph<K extends string, T> {
nodes: Record<K, T>;
edges: Array<{ start: K, end: K }>;
constructor(nodes: Record<K, T>, edges: Array<{ start: K, end: K }>) {
this.nodes = Object.assign({}, nodes);
this.edges = edges.slice();
}
}
// graphOne is a Graph<"a"|"b"|"c", string>
const graphOne = new Graph(
{
a: "NodeA", b: "NodeB", c: "NodeC"
}, [
{ start: "a", end: "b" },
{ start: "b", end: "c" }
]
);
在上面，graphOne是一个简单的图形，有三个节点标记为"a"，"b"和"c"，其中一条路径从"a"到"b"，从"b"到"c"。在这种情况下，存储在每个节点中的数据只是一个string。在这里，让我们为Graph类创建一个简单的控制台日志记录方法：
print() {
console.log(this.nodes)
console.log(this.edges.map(e => e.start + "➡" + e.end));
}
并使用它：
graphOne.print();
// Object { a: "NodeA", b: "NodeB", c: "NodeC" }
// Array [ "a➡b", "b➡c" ]
此时你可能会反对这种表示并不能自然地表达你如何使用图表，其中每个节点都有数据和一些子节点，你可以通过递归迭代子节点来遍历图形（并且可能陷入循环中），等等，你可能会想到这样的事情：
interface TraversableGraph<T> {
nodes: Array<TraversableNode<T>>;
}
interface TraversableNode<T> {
data: T,
children: Array<TraversableNode<T>>;
}
幸运的是，你可以很容易地将Graph转换为TraversableGraph。这是一种方法。让我们为asTraversableGraph()添加一个Graph方法：
asTraversableGraph(): TraversableGraph<T> {
return {
nodes: (Object.keys(this.nodes) as K[]).map(
k => this.asTraverableNode(k))
};
}
private asTraverableNode(k: K): TraversableNode<T> {
const graph = this;
return {
get data() {
return graph.nodes[k];
},
get children() {
return graph.edges.filter(e => e.start === k).map(
e => graph.asTraverableNode(e.end));
}
}
}
我选择使用getters，以便可遍历的图形（可能，可能）反映图形的突变（例如，你向Graph添加一个新的边缘，如果你走过它，TraversableGraph也会有新的边缘） 。但你不必这样做。
让我们确保它的行为合理：
graphOne.asTraversableGraph().nodes[0].data; // "NodeA"
graphOne.asTraversableGraph().nodes[0].children[0].data; // "NodeB"
最后，我们现在进行合并。使用Graph表示，这不再是一些奇怪的毛茸茸/循环/递归的东西。您只需合并节点并合并边缘然后回家。这是一种可行的方法，通过向merge()添加Graph方法：
merge<L extends string, U, V>(
otherGraph: Graph<L, U>,
dataMerge: (x: T | undefined, y: U | undefined) => V
): Graph<K | L, V> {
const thisGraph = this as Graph<K | L, T | undefined>;
const thatGraph = otherGraph as Graph<K | L, U | undefined>;
// merge nodes
const nodes = {} as Record<K | L, V>;
(Object.keys(thisGraph.nodes) as (K | L)[]).forEach(
k => nodes[k] = dataMerge(thisGraph.nodes[k], thatGraph.nodes[k]));
(Object.keys(thatGraph.nodes) as (K | L)[]).filter(k => !(k in nodes)).forEach(
k => nodes[k] = dataMerge(thisGraph.nodes[k], thatGraph.nodes[k]));
// merge edges
const edges: Record<string, { start: K | L, end: K | L }> = {};
thisGraph.edges.forEach(e => edges[JSON.stringify(e)] = e);
thatGraph.edges.forEach(e => edges[JSON.stringify(e)] = e);
return new Graph(nodes, Object.keys(edges).map(k => edges[k]));
}
请注意，merge()需要两个参数：另一个图形和一个dataMerge()回调，其作用是将第一个图形上的节点（如果存在）中的数据与来自第二个图形上相同标记节点的数据合并（如果是存在）并生成您想要在合并图中看到的数据。
通过遍历每个图的节点列表并在每个图的相同标记节点上运行dataMerge()来合并节点。通过合并两个边缘列表并确保没有重复来合并边缘（我通过在边缘使用JSON.stringify()作为唯一键来实现）。
让我们通过引入另一个图来看它是否有效：
// graphTwo is a Graph<"b" | "c" | "d", string>
const graphTwo = new Graph(
{
b: "NodeB", c: "Node C", d: "NodeD"
}, [
{ start: "b", end: "d" },
{ start: "b", end: "c" },
{ start: "d", end: "c" }
]
);
graphTwo.print();
// Object { b: "NodeB", c: "Node C", d: "NodeD" }
// Array(3) [ "b➡d", "b➡c", "d➡c" ]
合并它，注意到dataMerge()处理存储在graphOne中的字符串数据与存储在graphTwo中的字符串数据之间可能存在的冲突有点复杂：
// graphMerged is a Graph<"a" | "b" | "c" | "d", string>
const graphMerged = graphOne.merge(graphTwo,
(x, y) => typeof x === 'undefined' ?
(typeof y === 'undefined' ? "??" : y) :
((x === y || typeof y === 'undefined') ? x : x + "/" + y)
);
graphMerged.print();
// Object { a: "NodeA", b: "NodeB", c: "NodeC/Node C", d: "NodeD" }
// Array(4) [ "a➡b", "b➡c", "b➡d", "d➡c" ]
它的工作原理！合并的图形具有单个b➡c边缘，即使graphOne和graphTwo都具有相同的边缘。在c（graphOne）和"NodeC"（graphTwo）中标记为"Node C"的节点的名称不同，所以dataMerge()加入了它们（"NodeC/Node C"）。
这是上面所有代码的Playground link。
希望有所帮助。祝好运！