图的遍历

发表于 分类于 ， 阅读次数： Waline： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

图一般使用邻接表或者领接矩阵来实现。

⽤邻接表和邻接矩阵的存储⽅式如下：

邻接表很直观，我把每个节点 x 的邻居都存到⼀个列表⾥，然后把 x 和这个列表关联起来，这样就可以通过 ⼀个节点 x 找到它的所有相邻节点。 邻接矩阵则是⼀个⼆维布尔数组，我们权且称为 matrix，如果节点 x 和 y 是相连的，那么就把 \(matrix[x][y]\) 设为 （上图中绿⾊的⽅格代表 ）。 如果想找节点 的邻居，去扫⼀圈 $ matrix[x][..] $ 就⾏ 了。

那么，为什么有这两种存储图的⽅式呢？肯定是因为他们各有优劣。

对于邻接表，好处是占⽤的空间少。

你看邻接矩阵⾥⾯空着那么多位置，肯定需要更多的存储空间。

但是，邻接表⽆法快速判断两个节点是否相邻。 ⽐如说我想判断节点 1 是否和节点 3 相邻，我要去邻接表⾥ 1 对应的邻居列表⾥查找 是否存在。但对于邻接矩阵来说，只要看看matrix[1][3]就知道了，效率比较高。

797. 所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例：

输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]

输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

思路：

我们可以发现输入的二维数组其实就是「邻接表」。

我们只需要，以 0 为起点遍历图，同时记录遍历过的路径，当遍历到终点时将路径记录下来即可。

既然输⼊的图是⽆环的，我们就不需要 visited 数组辅助了，直接套⽤图的遍历框架：

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
class Solution {
public:
    vector<vector<int> > res;
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        //维护递归过程中经过的路径
        vector<int> path;
        traverse(graph, 0, path);
        return res;
    }
    void traverse(vector<vector<int> >& graph, int s, vector<int>& path){
        //添加节点 s 到路径
        path.push_back(s);

        int n = graph.size();
        if(s == n - 1){
            //到达终点
            res.push_back(path);
            path.pop_back();
            return;
        }

        //递归每个相邻节点
        for(int v : graph[s]){
            traverse(graph, v, path);
        }
        path.pop_back();
    }
};