home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

หาเส้นทางจากจุดหนึ่งไปยังจุดอื่นๆ โดยใช้ BFS ใน C++

ในปัญหานี้ เราได้รับกราฟทิศทางที่แสดงเป็น adjacency list ภารกิจของเรา คือ สร้างโปรแกรมหาเส้นทางจากจุดหนึ่งไปยังจุดอื่นๆ โดยใช้ BFS

BFS (Breadth First Search) คืออัลกอริทึมที่เดินทางผ่านกราฟในทิศทางกว้างและใช้คิวเพื่อจดจำจุดที่จะเริ่มค้นหาถัดไป เมื่อเกิดทางตันในการวนซ้ำใดๆ

มาดูตัวอย่างเพื่อเข้าใจปัญหา

อินพุต -

หาเส้นทางจากจุดหนึ่งไปยังจุดอื่นๆ โดยใช้ BFS ใน C++

เอาต์พุต

S

A <= S

B <= A <= S

C <= S

D <= C <= S

วิธีการแก้ปัญหา

เพื่อแก้ปัญหา เราจะทำการค้นหา BFS บนแต่ละองค์ประกอบของกราฟ เพื่อดำเนินการ เราจะสร้างคิวที่จะเก็บแฟล็กสำหรับการเยี่ยมชมโหนดใดๆ จากนั้น ใช้ visited array เราจะตรวจสอบว่าองค์ประกอบถูกเยี่ยมชมแล้วหรือยัง (ค่าไบนารี 0 และ 1 แสดงการเยี่ยมชม)

ตอนนี้ เราจะแก้ตัวอย่างทีละขั้นตอนเพื่อเข้าใจการทำงานของวิธีแก้ปัญหาของเรา

หาเส้นทางจากจุดหนึ่งไปยังจุดอื่นๆ โดยใช้ BFS ใน C++

เริ่มจากโหนด S,

  • เราจะเยี่ยมชมโหนด A โดยตรง

  • เพื่อไปถึงโหนด B เราจะเยี่ยมชมโหนด A ก่อนแล้วไปถึงโหนด B ผ่านโหนด A

  • เพื่อไปถึงโหนด C เราจะเยี่ยมชม C โดยตรงจาก S

  • เพื่อไปถึงโหนด D เราจะเยี่ยมชมโหนด C ก่อนแล้วจึงไปโหนด D

ตัวอย่าง

โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา

#include <bits/stdc++.h> using namespace std; void printPath(vector<int> parent, int initial, int node){ while (initial != node){ cout<<node<<" <= "; node = parent[node]; } cout<<node<<endl; } void findPathBFS(vector<vector<int> > graphAdjList, int initial, int graphSize){ vector<int> parent(graphSize, 0); vector<int> queue(graphSize, 0); int front = -1, rear = -1; vector<int> isVisited(graphSize, 0); isVisited[0] = 1; parent[0] = initial; queue[++rear] = initial; int k; while (front != rear) { k = queue[++front]; for (int j:graphAdjList[k]){ if (isVisited[j] == 0){ queue[++rear] = j; isVisited[j] = 1; parent[j] = k; } } } for (k = 0; k < graphSize; k++) printPath(parent, initial, k); } int main(){ vector<vector<int> > graphAdjList; graphAdjList.push_back({1, 3}); graphAdjList.push_back({0, 2}); graphAdjList.push_back({1}); graphAdjList.push_back({4}); graphAdjList.push_back({0}); int graphSize = graphAdjList.size(); int initial = 0; cout<<"The Path from vertex '0' to all other vertex in the graph is : \n"; findPathBFS(graphAdjList, initial, graphSize); }

เอาต์พุต

The Path from vertex '0' to all other vertex in the graph is : 0 1 <= 0 2 <= 1 <= 0 3 <= 0 4 <= 3 <= 0