算法图算法

DAG判定

字数统计: 1k字   |   阅读时长: 4分
,

摘要: DAG 判定算法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们给出 DAG 的判定算法，并解决 1059. 从始点到终点的所有路径。

DAG 的判定

给定有向图 $D$，判定 $D$ 是否为 DAG。

分析

等价于判定有向图 D 中有没有环，因此判定 DAG 的算法与有向图判定环的算法相同，可以参考文章 有向图的环。以下为复习。

1. BFS (拓扑排序)

如果拓扑排序后的排序列表长度小于 $n$，则无法拓扑排序，即 $D$ 不是 DAG。

代码 (C++, 模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class DAGChecker_bfs
{
public:
    bool operator()(const vector<vector<int>>& g, vector<int> indegrees)
    {
        int n = g.size();
        queue<int> q;
        for(int i = 0; i < n; ++i)
            if(indegrees[i] == 0)
                q.push(i);

        while(!q.empty())
        {
            int cur = q.front();
            q.pop();
            --n;
            for(int son: g[cur])
            {
                --indegrees[son];
                if(indegrees[son] == 0)
                    q.push(son);
            }
        }
        return n == 0;
    }
};

2. DFS

1
2
3
visited[i] = 0 未考查过
visited[i] = 1 在当前搜索路径中
visited[i] = 2 已经考查过

当前点为 u，如果在 for(int v: g[u]) 中发现 visited[v] == 1 则找到环。

点 u 在回溯之前加上 list.add(u) 可得拓扑排序后的列表。

代码 (C++, 模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class DAGChecker_dfs
{
    bool dfs(const vector<vector<int> >& g, int node, vector<int>& visited)
    {
        if(visited[node] == 2)
            return true;
        if(visited[node] == 1) // 环
            return false;
        visited[node] = 1;
        for(int son: g[node])
            if(!dfs(g, son, visited))
                return false;
        visited[node] = 2;
        return true;
    }

public:
    bool operator()(const vector<vector<int>>& g) 
    {
        int n = g.size();
        vector<int> visited(n, 0);
        for(int i = 0; i < n; ++i)
        {
            if(visited[i] != 0) continue;
            if(!dfs(g, i, visited))
                return false;
        }
        return true;
    }
};

$2 题目：1059. 从始点到终点的所有路径

给定有向图的边 edges，以及该图的始点 source 和目标终点 destination，确定从始点 source 出发的所有路径是否最终结束于目标终点 destination，即：

  • 从始点 source 到目标终点 destination 存在至少一条路径
  • 如果存在从始点 source 到没有出边的节点的路径，则该节点就是路径终点。
  • 从始点source到目标终点 destination 可能路径数是有限数字

当从始点 source 出发的所有路径都可以到达目标终点 destination 时返回 true，否则返回 false。

提示：

1
2
3
4
5
6
7
1 <= n <= 1e4
0 <= edges.length <= 1e4
edges.length == 2
0 <= ai, bi <= n - 1
0 <= source <= n - 1
0 <= destination <= n - 1
给定的图中可能带有自环和平行边。

示例 1：
输入：n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
输出：false
说明：节点 1 和节点 2 都可以到达，但也会卡在那里。

示例 2：
输入：n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3
输出：false
说明：有两种可能：在节点 3 处结束，或是在节点 1 和节点 2 之间无限循环。

示例 3：
输入：n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3
输出：true

算法：DAG 判定

首先判定图 D 是否是一个DAG。在 DAG 的基础上判断其终点是否均为 t。

如果判定环的过程用 DFS，则判定 DAG 和判定终点为 t 可以放到一起。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> g(n);
        for(vector<int> &e: edges)
            g[e[0]].push_back(e[1]);
        vector<int> visited(n, 0);
        visited[source] = 1;
        return dfs(g, source, destination, visited);
    }

private:
    bool dfs(const vector<vector<int>>& g, int u, const int t, vector<int>& visited)
    {
        if(g[u].empty())
        {
            visited[u] = 2;
            return u == t;
        }
        for(int v: g[u])
        {
            if(visited[v] == 1)
                return false;
            if(visited[v] == 2)
                continue;
            visited[v] = 1;
            if(!dfs(g, v, t, visited))
                return false;
        }
        visited[u] = 2;
        return true;
    }
};
Share