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

Michael阿明

发布于 2021-02-20 14:41:10

8440

发布于 2021-02-20 14:41:10

文章被收录于专栏：Michael阿明学习之路

1. 题目

问有几个连通网络

2. 解题

2.1 BFS 广度优先

参考图的数据结构

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，还可以不用递归的写法，见前面链接。

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);
			}
		}
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/09/13 ，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构