这是一个创建于 2193 天前的主题，其中的信息可能已经有所发展或是发生改变。
我手头有张森林的图，一个节点很多孩子，到另 n 个节点，保存为数据 a。现在别人编辑修改后，保存为数据 b。
现在问题是，如何高亮显示 a 和 b 的差异部分？有个算法吗？
每个节点或者方向线都有唯一标识。我的想法是遍历 a 的每个节点和方向线，看 b 里存不存在，不存在的都标记更改。最后 b 里剩下的是多出来的。也不知对不对？
没学过图论，非程序员科班出身，求大大们指点一二。
现在问题是，如何高亮显示 a 和 b 的差异部分？有个算法吗？
每个节点或者方向线都有唯一标识。我的想法是遍历 a 的每个节点和方向线，看 b 里存不存在，不存在的都标记更改。最后 b 里剩下的是多出来的。也不知对不对？
没学过图论，非程序员科班出身，求大大们指点一二。
 | 1 starqoq 2019-10-17 08:00:55 +08:00 你可以先比较节点，节点有三种修改情况， 不变（在修改前和修改后都出现），新增（在修改的时候新增），删除（类似）。 对于没有变化的节点，这个节点可能在修改中被换了位置，检查一下他的直接父节点是不是变化了 按照你具体的比较要求处理子树整体移动的情况。 对于没有变化也没有修改父节点，检查他的在兄弟中的顺序有没有变化。 |
 | 2 taogen 2019-10-17 08:04:26 +08:00 via Android 同一顶点出发，两个图同时 BFS 放队列中，比较两个图的每一层的差集，存储所有差集的指针到 vector 中，高亮所有差集节点。 |
 | 3 tt67wq 2019-10-17 08:23:04 +08:00 ``` bool cmpTree(struct TreeNode *node1, struct TreeNode *node2) { if (node1 == NULL && node2 == NULL) return true; if (node1 == NULL && node2 != NULL) return false; if (node1 != NULL && node2 == NULL) return false; if (node1->val != node2->val) // 按楼主的意思，这里给改个颜色 return false; return cmpTree(node1->left, node2->left) && cmpTree(node1->right, node2->right); } ``` 这样行不行？ 我随手写的 |
 | 4 BiteTheDust 2019-10-17 15:30:17 +08:00 可以同时在两边跑 dfs，这样可以跑出相同的部分 剩下的就都是不同的了 |
 | 5 ourleven OP @BiteTheDust 感谢！我去科普了下 dfs，收益匪浅。但是感觉没法套用这个场景啊！ 举例，dfs 第一个树结果 a 到 b 到 c 到 e。dfs 第二个树结果，a 到 b 到 d 到 c 到 e。 结果我能得到 ab 相同，剩下的都不同。但 c 到 e 其实是相同的 |
| 6 ourleven OP @tt67wq 感谢！ 好像简单了点？这样应该是有漏的。到后面不相同了就停了。然而是想要所有的不同 |
| 9 BiteTheDust 2019-10-17 20:07:04 +08:00 那你得准确地规定什么样算是相同 什么样算是不同了 如果仅仅是需要标记相同的父子关系 那只要枚举两个树每个节点，取他们孩子的交集就可以了 |
| 10 taogen 2019-10-17 21:11:52 +08:00 via iPhone 初始状态：定义一个指针 levelPtr 表示指向每一层最后一个节点指针。让第一个节点根节点入队，level 指向根节点。 循环操作：队首元素出队，并把它所有子节点入队。判断当前出队节点是不是 levelptr 指向的，如果是则更换 levelptr 指向为最后一个入队的子节点，即为下一层的最后一个节点。 |
Select Language