Dalam tutorial ini, Anda akan belajar tentang algoritma pencarian pertama yang luas. Selain itu, Anda akan menemukan contoh kerja dari algoritma bfs di C, C ++, Java dan Python.
Traversal berarti mengunjungi semua node dari sebuah grafik. Breadth First Traversal atau Breadth First Search adalah algoritma rekursif untuk mencari semua simpul dari suatu grafik atau struktur data pohon.
Algoritma BFS
Implementasi BFS standar menempatkan setiap simpul grafik ke dalam salah satu dari dua kategori:
- Dikunjungi
- Tidak Dikunjungi
Tujuan dari algoritma ini adalah untuk menandai setiap simpul sebagai telah dikunjungi sambil menghindari siklus.
Algoritme bekerja sebagai berikut:
- Mulailah dengan meletakkan salah satu simpul grafik di belakang antrian.
- Ambil item depan antrian dan tambahkan ke daftar yang dikunjungi.
- Buat daftar simpul yang berdekatan pada simpul itu. Tambahkan yang tidak ada dalam daftar yang dikunjungi ke belakang antrian.
- Terus ulangi langkah 2 dan 3 hingga antrian kosong.
Grafik mungkin memiliki dua bagian terputus yang berbeda sehingga untuk memastikan bahwa kita mencakup setiap simpul, kita juga dapat menjalankan algoritma BFS pada setiap simpul
Contoh BFS
Mari kita lihat bagaimana algoritma Breadth First Search bekerja dengan sebuah contoh. Kami menggunakan grafik tidak berarah dengan 5 simpul.
Grafik tidak berarah dengan 5 simpul
Kita mulai dari simpul 0, algoritma BFS dimulai dengan meletakkannya di daftar yang Dikunjungi dan meletakkan semua simpul yang berdekatan di tumpukan.
Kunjungi start vertex dan tambahkan vertex yang berdekatan ke antrian
Selanjutnya, kita mengunjungi elemen di depan antrian yaitu 1 dan pergi ke node yang berdekatan. Karena 0 telah dikunjungi, kami mengunjungi 2 sebagai gantinya.
Kunjungi tetangga pertama dari simpul awal 0, yaitu 1
Simpul 2 memiliki simpul bersebelahan yang belum dikunjungi di 4, jadi kami menambahkannya ke belakang antrian dan mengunjungi 3, yang berada di depan antrian.
Kunjungan 2 yang telah ditambahkan ke antrian sebelumnya untuk menambahkan tetangganya 
4 tetap dalam antrian
Hanya 4 yang tersisa dalam antrian karena satu-satunya simpul yang berdekatan dari 3 yaitu 0 sudah dikunjungi. Kami mengunjunginya.
Kunjungi item terakhir yang tersisa di tumpukan untuk memeriksa apakah memiliki tetangga yang belum dikunjungi
Karena antrian kosong, kami telah menyelesaikan Traversal Pertama Breadth dari grafik.
Pseudocode BFS
buat antrian tanda Q v sebagai telah dikunjungi dan masukkan v ke Q sementara Q tidak kosong lepaskan kepala tanda Q dan antrekan semua (belum dikunjungi) tetangga u
Contoh Python, Java dan C / C ++
Kode untuk Breadth First Search Algorithm dengan contoh ditampilkan di bawah ini. Kode tersebut telah disederhanakan sehingga kita dapat fokus pada algoritme daripada detail lainnya.
Python Java C C + # BFS algorithm in Python import collections # BFS algorithm def bfs(graph, root): visited, queue = set(), collections.deque((root)) visited.add(root) while queue: # Dequeue a vertex from queue vertex = queue.popleft() print(str(vertex) + " ", end="") # If not visited, mark it as visited, and # enqueue it for neighbour in graph(vertex): if neighbour not in visited: visited.add(neighbour) queue.append(neighbour) if __name__ == '__main__': graph = (0: (1, 2), 1: (2), 2: (3), 3: (1, 2)) print("Following is Breadth First Traversal: ") bfs(graph, 0)
// BFS algorithm in Java import java.util.*; public class Graph ( private int V; private LinkedList adj(); // Create a graph Graph(int v) ( V = v; adj = new LinkedList(v); for (int i = 0; i < v; ++i) adj(i) = new LinkedList(); ) // Add edges to the graph void addEdge(int v, int w) ( adj(v).add(w); ) // BFS algorithm void BFS(int s) ( boolean visited() = new boolean(V); LinkedList queue = new LinkedList(); visited(s) = true; queue.add(s); while (queue.size() != 0) ( s = queue.poll(); System.out.print(s + " "); Iterator i = adj(s).listIterator(); while (i.hasNext()) ( int n = i.next(); if (!visited(n)) ( visited(n) = true; queue.add(n); ) ) ) ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)"); g.BFS(2); ) )
// BFS algorithm in C #include #include #define SIZE 40 struct queue ( int items(SIZE); int front; int rear; ); struct queue* createQueue(); void enqueue(struct queue* q, int); int dequeue(struct queue* q); void display(struct queue* q); int isEmpty(struct queue* q); void printQueue(struct queue* q); struct node ( int vertex; struct node* next; ); struct node* createNode(int); struct Graph ( int numVertices; struct node** adjLists; int* visited; ); // BFS algorithm void bfs(struct Graph* graph, int startVertex) ( struct queue* q = createQueue(); graph->visited(startVertex) = 1; enqueue(q, startVertex); while (!isEmpty(q)) ( printQueue(q); int currentVertex = dequeue(q); printf("Visited %d", currentVertex); struct node* temp = graph->adjLists(currentVertex); while (temp) ( int adjVertex = temp->vertex; if (graph->visited(adjVertex) == 0) ( graph->visited(adjVertex) = 1; enqueue(q, adjVertex); ) temp = temp->next; ) ) ) // Creating a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Creating a graph struct Graph* createGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i adjLists(i) = NULL; graph->visited(i) = 0; ) return graph; ) // Add edge void addEdge(struct Graph* graph, int src, int dest) ( // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists(src); graph->adjLists(src) = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists(dest); graph->adjLists(dest) = newNode; ) // Create a queue struct queue* createQueue() ( struct queue* q = malloc(sizeof(struct queue)); q->front = -1; q->rear = -1; return q; ) // Check if the queue is empty int isEmpty(struct queue* q) ( if (q->rear == -1) return 1; else return 0; ) // Adding elements into queue void enqueue(struct queue* q, int value) ( if (q->rear == SIZE - 1) printf("Queue is Full!!"); else ( if (q->front == -1) q->front = 0; q->rear++; q->items(q->rear) = value; ) ) // Removing elements from queue int dequeue(struct queue* q) ( int item; if (isEmpty(q)) ( printf("Queue is empty"); item = -1; ) else ( item = q->items(q->front); q->front++; if (q->front> q->rear) ( printf("Resetting queue "); q->front = q->rear = -1; ) ) return item; ) // Print the queue void printQueue(struct queue* q) ( int i = q->front; if (isEmpty(q)) ( printf("Queue is empty"); ) else ( printf("Queue contains "); for (i = q->front; i rear + 1; i++) ( printf("%d ", q->items(i)); ) ) ) int main() ( struct Graph* graph = createGraph(6); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 1, 4); addEdge(graph, 1, 3); addEdge(graph, 2, 4); addEdge(graph, 3, 4); bfs(graph, 0); return 0; )
// BFS algorithm in C++ #include #include using namespace std; class Graph ( int numVertices; list* adjLists; bool* visited; public: Graph(int vertices); void addEdge(int src, int dest); void BFS(int startVertex); ); // Create a graph with given vertices, // and maintain an adjacency list Graph::Graph(int vertices) ( numVertices = vertices; adjLists = new list(vertices); ) // Add edges to the graph void Graph::addEdge(int src, int dest) ( adjLists(src).push_back(dest); adjLists(dest).push_back(src); ) // BFS algorithm void Graph::BFS(int startVertex) ( visited = new bool(numVertices); for (int i = 0; i < numVertices; i++) visited(i) = false; list queue; visited(startVertex) = true; queue.push_back(startVertex); list::iterator i; while (!queue.empty()) ( int currVertex = queue.front(); cout << "Visited " << currVertex << " "; queue.pop_front(); for (i = adjLists(currVertex).begin(); i != adjLists(currVertex).end(); ++i) ( int adjVertex = *i; if (!visited(adjVertex)) ( visited(adjVertex) = true; queue.push_back(adjVertex); ) ) ) ) int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); g.BFS(2); return 0; )
Kompleksitas Algoritma BFS
Kompleksitas waktu dari algoritma BFS direpresentasikan dalam bentuk O(V + E), dimana V adalah jumlah node dan E adalah jumlah edge.
Kompleksitas ruang dari algoritme adalah O(V).
Aplikasi Algoritma BFS
- Untuk membangun indeks dengan indeks pencarian
- Untuk navigasi GPS
- Algoritme pencarian jalan
- Dalam algoritma Ford-Fulkerson untuk menemukan aliran maksimum dalam suatu jaringan
- Deteksi siklus dalam grafik yang tidak diarahkan
- Dalam pohon rentang minimum
