V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ourleven
V2EX  ›  程序员

万能的 V2,求问两颗树林的比较差异问题

  •  
  •   ourleven · 2019-10-17 07:37:46 +08:00 via iPhone · 1886 次点击
    这是一个创建于 1624 天前的主题,其中的信息可能已经有所发展或是发生改变。
    我手头有张森林的图,一个节点很多孩子,到另 n 个节点,保存为数据 a。现在别人编辑修改后,保存为数据 b。

    现在问题是,如何高亮显示 a 和 b 的差异部分?有个算法吗?

    每个节点或者方向线都有唯一标识。我的想法是遍历 a 的每个节点和方向线,看 b 里存不存在,不存在的都标记更改。最后 b 里剩下的是多出来的。也不知对不对?

    没学过图论,非程序员科班出身,求大大们指点一二。
    10 条回复    2019-10-17 21:11:52 +08:00
    starqoq
        1
    starqoq  
       2019-10-17 08:00:55 +08:00
    你可以先比较节点,节点有三种修改情况,
    不变(在修改前和修改后都出现),新增(在修改的时候新增),删除(类似)。

    对于没有变化的节点,这个节点可能在修改中被换了位置,检查一下他的直接父节点是不是变化了
    按照你具体的比较要求处理子树整体移动的情况。

    对于没有变化也没有修改父节点,检查他的在兄弟中的顺序有没有变化。
    taogen
        2
    taogen  
       2019-10-17 08:04:26 +08:00 via Android
    同一顶点出发,两个图同时 BFS 放队列中,比较两个图的每一层的差集,存储所有差集的指针到 vector 中,高亮所有差集节点。
    tt67wq
        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);
    }

    ```
    这样行不行? 我随手写的
    BiteTheDust
        4
    BiteTheDust  
       2019-10-17 15:30:17 +08:00
    可以同时在两边跑 dfs,这样可以跑出相同的部分 剩下的就都是不同的了
    ourleven
        5
    ourleven  
    OP
       2019-10-17 19:56:25 +08:00 via iPhone
    @BiteTheDust 感谢!我去科普了下 dfs,收益匪浅。但是感觉没法套用这个场景啊!
    举例,dfs 第一个树结果 a 到 b 到 c 到 e。dfs 第二个树结果,a 到 b 到 d 到 c 到 e。

    结果我能得到 ab 相同,剩下的都不同。但 c 到 e 其实是相同的
    ourleven
        6
    ourleven  
    OP
       2019-10-17 20:04:10 +08:00 via iPhone
    @tt67wq 感谢!
    好像简单了点?这样应该是有漏的。到后面不相同了就停了。然而是想要所有的不同
    ourleven
        7
    ourleven  
    OP
       2019-10-17 20:05:13 +08:00 via iPhone
    @taogen 谢谢!
    但问题是。。。怎么区分每一层呢?
    ourleven
        8
    ourleven  
    OP
       2019-10-17 20:06:09 +08:00 via iPhone
    @starqoq 多谢!目前看起来倾向于这么比对了😂😂
    BiteTheDust
        9
    BiteTheDust  
       2019-10-17 20:07:04 +08:00
    那你得准确地规定什么样算是相同 什么样算是不同了
    如果仅仅是需要标记相同的父子关系 那只要枚举两个树每个节点,取他们孩子的交集就可以了
    taogen
        10
    taogen  
       2019-10-17 21:11:52 +08:00 via iPhone
    初始状态:定义一个指针 levelPtr 表示指向每一层最后一个节点指针。让第一个节点根节点入队,level 指向根节点。
    循环操作:队首元素出队,并把它所有子节点入队。判断当前出队节点是不是 levelptr 指向的,如果是则更换 levelptr 指向为最后一个入队的子节点,即为下一层的最后一个节点。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1068 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 19:04 · PVG 03:04 · LAX 12:04 · JFK 15:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.