减少访问图边次数的优化方案
查看原帖
减少访问图边次数的优化方案
455777
algo_h楼主2025/1/6 21:27

如题,设正向图中每个节点的出度为 outord,类似“拓扑排序”的思想,可以在从 t 点出发,广度优先搜索反向图的过程中,在搜索未访问过的相邻节点的同时,把每个相邻节点的出度减一。这样反向图搜索完成后,在反向图中,所有可以从 t 点出发访问到,且 outord 为 0 的节点,都是符合题目要求的节点。从 t 点出发,再次遍历反向图即可求出答案。该方案相比“遍历反向图 \to 求可用节点 \to 再次遍历正向或反向图”的方案大约减少 1/3 的图边访问量,预计可提速 ×1.5\times 1.5

2025/1/6 21:27
加载中...