BFS (Breadth-First Search)

A graph traversal algorithm that search breadth-first.
インプリメンテーション
こうぞう
ナビゲーションロジック以外のコード

#include <queue>
#include <vector>

using namespace std;

// by Queue 
void BFS(int root = 0, int nodes_size, vector<int> from, vector<int> to)
{
	
    vector<bool> visited(nodes_size, false);  // is the node visited?
    vector<vector<int>> graph(nodes_size, vector<int>());
    queue<int> q;
    
    // init vector<vector<int>> graph
    for(int i = 0; i < from.size(); i++)
    {
        graph[from[i]].push_back(to[i]);
        graph[to[i]].push_back(from[i]);
    }

	// init queue<int> q
    q.push(root);
    visited[root] = true;

	/*
    	search
    */
}

探索する
Example I
通常BFSストリームによるコード

	// search
    while (!q.empty())
    {
        int curr = q.front();
        q.pop();
        
        if (!visited[curr]/*necessary_conditions*/) 
        {
            visited[curr] = true;
			// printf("%d ", curr); // print the process

            for (int i = 0; i < graph[curr].size(); i++)
            {
                int next = graph[curr][i];  // adjacent node
                if (!visited[next])
                    q.push(next);
            }
        }
    }

Example II
//pre-checkがアクセスしたコードを改善し、キュー演算を低減し、コードを簡素化

    // search
    while (!q.empty())
    {
        int curr = q.front();
        q.pop();
		// printf("%d ", curr); // print the process
        
        for (int i = 0; i < graph[curr].size(); i++)
        {
            int next = graph[curr][i]; // adjacent node

            if (!visited[next]/*necessary_conditions*/)  
            {
                visited[next] = true;
                q.push(next);
            }
        }
    }

活用する
Example - Shortest Path
すべての幹線の長さが1であると仮定すると、最短距離を求めるのに用いられる

#include <queue>
#include <vector>

using namespace std;


// assume each length of an edge is 1
void BFS(int start = 0, int nodes_size,  vector<int> from, vector<int> to)
{
    vector<vector<int>> graph(nodes_size, vector<int>());
    vector<bool> visited(nodes_size, false);
    vector<int> dist(nodes_size, -1); // distance from start node
    queue<int> q;
    
    for(int i = 0; i < from.size(); i++)
    {
        graph[from[i]].push_back(to[i]);
        graph[to[i]].push_back(from[i]);
    }

    q.push(start);
    visited[start] = true;
    dist[start] = 0; //

    while (!q.empty())
    {
        int curr = q.front();
        q.pop();
        
        for (int i = 0; i < graph[curr].size(); i++)
        {
            int next = graph[curr][i];

            if (!visited[next])  
            {
                visited[next] = true;
                dist[next] = dist[curr] + 1; // 
                q.push(next);
            }
        }
    }
}