breadth first search c program traverse graph
이 자습서에서는 그래프 또는 트리가 광범위하게 탐색되는 C ++의 Breadth First Search를 다룹니다. BFS 알고리즘 및 구현도 배우게됩니다.
이 명시적인 C ++ 자습서는 트리 또는 그래프에서 수행 할 수있는 순회 기술에 대한 자세한 설명을 제공합니다.
순회는 그래프 또는 트리의 모든 노드를 방문하는 데 사용하는 기술입니다. 순회에는 두 가지 표준 방법이 있습니다.
- 너비 우선 검색 (BFS)
- 깊이 우선 검색 (DFS)
=> 전체 C ++ 자습서 목록을 탐색하려면 여기를 참조하십시오.
시스코 네트워킹 인터뷰 질문 및 답변 pdf
학습 내용 :
C ++의 BFS (Breadth First Search) 기술
이 자습서에서는 폭 우선 검색 기술에 대해 자세히 설명합니다.
너비 우선 순회 기법에서 그래프 또는 트리는 너비별로 순회됩니다. 이 기술은 큐 데이터 구조를 사용하여 정점 또는 노드를 저장하고 다음에 사용할 정점 / 노드를 결정합니다.
Breadth-first 알고리즘은 루트 노드에서 시작한 다음 모든 인접 노드를 순회합니다. 그런 다음 가장 가까운 노드를 선택하고 방문하지 않은 다른 모든 노드를 탐색합니다. 이 프로세스는 그래프의 모든 노드를 탐색 할 때까지 반복됩니다.
폭 우선 검색 알고리즘
다음은 BFS 기술에 대한 알고리즘입니다.
BFS 알고리즘을 사용하여 순회 할 그래프로 G를 고려하십시오.
S를 그래프의 루트 / 시작 노드라고합니다.
- 1 단계: 노드 S로 시작하여 대기열에 넣습니다.
- 2 단계: 그래프의 모든 노드에 대해 다음 단계를 반복합니다.
- 3 단계 : S를 대기열에서 빼고 처리합니다.
- 4 단계 : S의 모든 인접 노드를 대기열에 넣고 처리합니다.
- (루프 끝)
- 6 단계 : 출구
의사 코드
BFS 기술에 대한 의사 코드는 다음과 같습니다.
Procedure BFS (G, s) G is the graph and s is the source node begin let q be queue to store nodes q.enqueue(s) //insert source node in the queue mark s as visited. while (q is not empty) //remove the element from the queue whose adjacent nodes are to be processed n = q.dequeue( ) //processing all the adjacent nodes of n for all neighbors m of n in Graph G if w is not visited q.enqueue (m) //Stores m in Q to in turn visit its adjacent nodes mark m as visited. end삽화가있는 순회
0을 시작 노드 또는 소스 노드로 지정합니다. 먼저, 방문한 큐와 큐의 모든 인접 노드에 큐에 넣습니다.
다음으로, 처리 할 인접 노드 중 하나를 가져옵니다. 즉, 1. 대기열에서 제거하여 방문한 것으로 표시하고 인접한 노드를 대기열에 넣습니다 (이미 대기열에있는 2와 3). 0이 이미 방문되었으므로 무시합니다.
오라클 SOA 인터뷰 질문과 경험에 대한 답변
다음으로 노드 2를 대기열에서 빼고 방문한 것으로 표시합니다. 그런 다음 인접한 노드 4가 대기열에 추가됩니다.
다음으로 대기열에서 3을 빼고 방문한 것으로 표시합니다. 노드 3에는 인접한 노드가 하나만 있습니다. 즉, 이미 방문한 0입니다. 따라서 우리는 그것을 무시합니다.
이 단계에서는 노드 4 만 대기열에 있습니다. 인접한 노드 2는 이미 방문되었으므로 무시합니다. 이제 4를 방문으로 표시합니다.
다음으로 방문 목록에있는 시퀀스는 주어진 그래프의 너비 우선 순회입니다.
주어진 그래프와 순회 시퀀스를 관찰하면 BFS 알고리즘의 경우 실제로 그래프를 폭으로 순회 한 다음 다음 레벨로 이동한다는 것을 알 수 있습니다.
BFS 구현
#include #include using namespace std; // a directed graph class class DiGraph { int V; // No. of vertices // Pointer to an array containing adjacency lists list *adjList; public: DiGraph(int V); // Constructor // add an edge from vertex v to w void addEdge(int v, int w); // BFS traversal sequence starting with s ->starting node void BFS(int s); }; DiGraph::DiGraph(int V) { this->V = V; adjList = new list (V); } void DiGraph::addEdge(int v, int w) { adjList(v).push_back(w); // Add w to v’s list. } void DiGraph::BFS(int s) { // initially none of the vertices is visited bool *visited = new bool(V); for(int i = 0; i queue; // Mark the current node as visited and enqueue it visited(s) = true; queue.push_back(s); // iterator 'i' to get all adjacent vertices list ::iterator i; while(!queue.empty()) { // dequeue the vertex s = queue.front(); cout << s << ' '; queue.pop_front(); // get all adjacent vertices of popped vertex and process each if not already visited for (i = adjList(s).begin(); i != adjList(s).end(); ++i) { if (!visited(*i)) { visited(*i) = true; queue.push_back(*i); } } } } // main program int main() { // create a graph DiGraph dg(5); dg.addEdge(0, 1); dg.addEdge(0, 2); dg.addEdge(0, 3); dg.addEdge(1, 2); dg.addEdge(2, 4); dg.addEdge(3, 3); dg.addEdge(4, 4); cout << 'Breadth First Traversal for given graph (with 0 as starting node): '< 산출:
소프트웨어 테스트의 버그 유형
주어진 그래프에 대한 폭 우선 순회 (0을 시작 노드로 사용) :
012 34
위의 프로그램에서 BFS를 구현했습니다. 그래프는 인접 목록 형식이며 반복자를 사용하여 목록을 반복하고 BFS를 수행합니다.
순회 시퀀스를 비교하기 위해 프로그램에 대한 입력으로 설명 목적으로 사용한 것과 동일한 그래프를 사용했습니다.
런타임 분석
V가 꼭지점의 수이고 E가 그래프의 간선 수이면 BFS의 시간 복잡도는 다음과 같이 표현할 수 있습니다. O (| V | + | E |) . 이것은 또한 그래프를 표현하는 데 사용하는 데이터 구조에 따라 달라집니다.
구현에서와 같이 인접 목록을 사용하면 시간 복잡성은 다음과 같습니다. O (| V | + | E |).
인접 행렬을 사용하면 시간 복잡도는 다음과 같습니다. O (V ^ 2) .
사용 된 데이터 구조 외에도 그래프가 밀집된 지 또는 드물게 채워지는지에 대한 요소도 있습니다.
정점 수가 가장자리 수를 초과하면 연결이 끊어진 정점이 많기 때문에 그래프가 드물게 연결되었다고합니다. 이 경우 그래프의 시간 복잡도는 O (V)가됩니다.
반면에 때때로 그래프는 정점 수보다 더 많은 모서리를 가질 수 있습니다. 이 경우 그래프는 밀집되어 있다고합니다. 이러한 그래프의 시간 복잡도는 O (E)입니다.
결론적으로 O (| V | + | E |)라는 표현이 의미하는 것은 그래프가 조밀한지 또는 드물게 채워져 있는지에 따라 달라지며, 지배적 인 요소, 즉 모서리 또는 꼭지점이 그에 따라 그래프의 시간 복잡도를 결정합니다.
BFS 탐색의 응용
- 가비지 컬렉션 : 가비지 콜렉션 기술인 'Cheney의 알고리즘'은 가비지 콜렉션을 복사하기 위해 폭 우선 순회를 사용합니다.
- 네트워크에서 방송 : 패킷은 브로드 캐스트 네트워크에서 BFS 기술을 사용하여 한 노드에서 다른 노드로 이동하여 모든 노드에 도달합니다.
- GPS 내비게이션 : GPS 내비게이션에서 BFS를 사용하여 모든 인접 또는 인접 위치 노드를 찾을 수 있습니다.
- 소셜 네트워킹 웹 사이트 : 사람 'P'가 주어지면, 우리는 BFS를 사용하여 p에서 d 레벨까지 거리에있는 모든 사람을 찾을 수 있습니다.
- 피어 투 피어 네트워크 : 다시 BFS는 모든 인접 노드를 찾기 위해 피어 투 피어 네트워크에서 사용할 수 있습니다.
- 비가 중 그래프에서 최단 경로 및 최소 스패닝 트리 : BFS 기술은 가장 짧은 경로, 즉 가중치가 적용되지 않은 그래프에서 가장자리 수가 가장 적은 경로를 찾는 데 사용됩니다. 마찬가지로 가중치가 적용되지 않은 그래프에서 BFS를 사용하여 최소 스패닝 트리를 찾을 수도 있습니다.
결론
너비 우선 검색 기술은 그래프 또는 트리의 모든 노드를 너비 방식으로 탐색하는 데 사용되는 방법입니다.
이 기술은 주로 그래프의 노드 사이의 최단 경로를 찾는 데 사용되거나 네트워크에서와 같이 모든 인접 노드를 방문해야하는 애플리케이션에서 사용됩니다.
=> 무료 C ++ 과정을 보려면 여기를 클릭하십시오.
추천 도서