차례
문제 정책
“연결이 끊긴 그래프에 대한 BFS”문제는 연결이 끊긴 방향성 그래프가 주어지고 그래프의 BFS 순회를 인쇄한다는 것을 나타냅니다.
예
위 그래프의 BFS 순회는 다음과 같습니다. 0 1 2 5 3 4 6
접근
Disconnected Directed Graph에 대한 BFS (Breadth First Search) 순회는 다음과 약간 다릅니다. BFS 순회 연결된 무 방향 그래프의 경우. 연결된 무 방향 그래프에서 모든 소스 노드에서 순회를 시작합니다. S 순회 중에 전체 그래프 네트워크를 방문합니다. 그러나 Disconnected Directed Graph에 대한 BFS 순회에는 방문하지 않은 각 노드를 방문하고 해당 노드에서 시작하는 BFS 순회를 수행하는 것이 포함됩니다. 모든 노드가 방문되었음을 확인하면 순회를 종료합니다.
아래에 주어진 연결된 무 방향 그래프를 고려하면 그래프의 모든 노드에서 BFS 순회를 시작하면 그래프의 모든 노드를 방문합니다. 한 번.
아래의 방향 연결 그래프를 고려하면 이미지에서 알 수 있으므로 그래프의 모든 노드를 방문하려면 노드에서 반복적으로 BFS 순회를 수행해야합니다. 0, 1, 3.
암호알고리즘
- 고려해보십시오. V 주어진 그래프의 노드.
- 0에서 V까지 각 노드를 반복하고 방문하지 않은 첫 번째 노드를 찾습니다.
- 이 노드에서 시작하여 BFS 순회를 시작하고 이후 순회되는 모든 노드를 방문한 것으로 표시합니다.
- 그래프의 모든 노드를 방문하면 종료합니다.
암호
연결이 끊긴 그래프를위한 BFS 용 C ++ 프로그램
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Add Edge from node u to v
void addEdge(vector <int> graph[], int u, int v)
{
graph[u].push_back(v);
}
// BFS traversal function
void BFS(vector <int> graph[], int n)
{
// vector to mark nodes as visited
vector <bool> vis(n,false);
// Process each node from 0 to n-1
for(int i=0;i<n;i++)
{
// If not visited node is found
if(vis[i] == false)
{
// BFS queue
queue <int> q;
// add not visited node to queue
q.push(i);
// BFS traversal
while(!q.empty())
{
int front = q.front();
q.pop();
cout<<front<<" ";
vis[front] = true;
for(auto node : graph[front])
{
if(vis[node] == false)
q.push(node);
}
}
}
}
cout<<endl;
}
int main()
{
// Construct the graph
int n = 7;
vector <int> graph[n];
vector<pair<int,int>> edges = {{1,0},{1,2},{2,5},{3,4},{4,6}};
for(auto e : edges)
addEdge(graph,e.first,e.second);
// Display the BFS traversal
cout<<"BFS traversal of the given graph : ";
BFS(graph,n);
return 0;
}
BFS traversal of the given graph : 0 1 2 5 3 4 6
연결이 끊긴 그래프를위한 BFS 용 Java 프로그램
import java.util.*;
import java.io.*;
class TutorialCup
{
// Add Edge from node u to v
static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v)
{
graph.get(u).add(v);
}
// BFS traversal function
static void BFS(ArrayList<ArrayList<Integer>> graph, int n)
{
// array to mark nodes as visited
boolean [] vis = new boolean[n];
// Process each node from 0 to n-1
for(int i=0;i<n;i++)
{
// If not visited node is found
if(vis[i] == false)
{
// BFS queue
Queue <Integer> q = new LinkedList<>();
// add not visited node to queue
q.add(i);
// BFS traversal
while(!q.isEmpty())
{
int front = q.poll();
System.out.print(front+" ");
vis[front] = true;
Iterator itr = graph.get(front).iterator();
while(itr.hasNext())
{
int node = (Integer)itr.next();
if(vis[node] == false)
q.add(node);
}
}
}
}
System.out.println();
}
public static void main (String[] args)
{
// Construct the graph
int n = 7;
ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<n;i++)
graph.add(new ArrayList<Integer>());
int [][] edges = {{1,0},{1,2},{2,5},{3,4},{4,6}};
for(int i=0;i<edges.length;i++)
addEdge(graph,edges[i][0],edges[i][1]);
// Display the BFS traversal
System.out.print("BFS traversal of the given graph : ");
BFS(graph,n);
}
}
BFS traversal of the given graph : 0 1 2 5 3 4 6
복잡성 분석
우리가 공간을 사용했기 때문에 복잡성은 선형이됩니다. 따라서 알고리즘은 공간에서 선형이됩니다. 그리고 그래프의 모든 노드를 방문했을 때 시간 복잡성에 대해. 알고리즘도 선형 시간이 걸립니다.
V = 노드 수.
E = 모서리 수.
