输入:一个有向带环图 输出:图中每个节点的dom集合 在课堂上我们讨论的算法是先对每个节点的dom集合进行初始化,即全部置为N(节点个数是N个),把所有的节点都放到节点i的dom集中。然后再依次查询节点i的每条路径,将前驱结点的dom集合求交集形成新的集合,如果与i的dom集合不同就替换,如此循环,直到每个节点的dom集合都不在变化为止。考虑到这样可能要循环很多次,而且每次都会求解从第一个节点到当前节点的所有路径,对于有向带环图来说比较麻烦。
2022-01-09 14:33:24 25KB 有向带环图的必经节点
1