DFS,BFS 练习（深搜，广搜，图，leetcode）

https://leetcode-cn.com/problems/route-between-nodes-lcci/

节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。

示例1:

输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
输出：true
示例2:

输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
输出 true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/route-between-nodes-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

DFS 深度优先搜索：（使用dfs函数递归）

class Solution {

public:

    void dfs(vector<vector<int>>& neighbor,vector<int>& visit, int node, int target, int& mark)

    {

        //cout<<"node:"<<node<<endl;

        if(mark==1)

        return ;

        visit[node] = 1;

        for(auto& i:neighbor[node])

        {

            if(i==target)

            {

                mark=1;

                return;

            }

            else

            dfs(neighbor,visit, i, target, mark);

        }

        visit[node] = 0;

        return ;

    }

    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {

        vector<vector<int>> neighbor(n);

        for(auto& i:graph)

        neighbor[i[0]].push_back(i[1]);

        vector<int> visit(n,0);

        int mark = 0;

        dfs(neighbor,visit, start, target, mark);

        if(mark==1)

        return true;

        else

        return false;

    }

};

BFS广度优先搜索：（使用队列queue）

class Solution {

public:

    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {

        vector<vector<int>> neighbor(n);

        for(auto& i:graph)

        neighbor[i[0]].push_back(i[1]);

        vector<int> visit(n,0);

        int mark = 0;

        queue<int> q;

        q.push(start);

        while(!q.empty() && mark==0)

        {

            int node = q.front();

            q.pop();

            for(auto& i:neighbor[node])

            {

                if(i==target)

                {

                    mark=1;

                    break;

                }

                else

                q.push(i);

            }

        }

        if(mark==1)

        return true;

        else

        return false;

    }

};

巴特西

DFS,BFS 练习（深搜，广搜，图，leetcode）

最新文章

热门文章