LeetCode 547. 朋友圈（图的遍历BFS & DFS）

1. 题目

问有几个连通网络

2. 解题

2.1 BFS 广度优先

参考图的数据结构

代码语言：javascript复制

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size(), groups = 0, i;
        bool visited[n] = {false};
        for(i = 0; i < n;   i)
        {
        	if(!visited[i])
        	{
        		bfs(M, visited, n, i);
        		  groups;
        	}
        }
        return groups;
    }
    void bfs(vector<vector<int>>& M, bool *visited, int &n, int idx) 
    {
    	queue<int> q;
    	q.push(idx);
    	visited[idx] = true;
    	int i, j;
    	while(!q.empty())
    	{
    		i = q.front();
            q.pop();
    		for(j = 0; j < n;   j)
    		{
    			if(M[i][j] && !visited[j])
    			{
    				visited[j] = true;
    				q.push(j);
    			}
    		}
    	}
    }
};

2.2 DFS 深度优先

参考图的DFS，还可以不用递归的写法，见前面链接。

代码语言：javascript复制

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size(), groups = 0, i;
        bool visited[n] = {false};
        for(i = 0; i < n;   i)
        {
        	if(!visited[i])
        	{
        		dfs(M, visited, n, i);
        		  groups;
        	}
        }
        return groups;
    }
    void dfs(vector<vector<int>>& M, bool *visited, int &n, int idx) 
    {
    	visited[idx] = true;
		for(int j = 0; j < n;   j)
		{
			if(M[idx][j] && !visited[j])
			{
				dfs(M, visited, n, j);
			}
		}
    }
};

数据结构 dfs 递归 网络

0 人点赞