Algoritma Grafik BFS (Dengan kod dalam C, C ++, Java dan Python)

Isi kandungan

Algoritma BFS
Contoh BFS
Pseudokod BFS
Contoh Python, Java dan C / C ++
Kerumitan Algoritma BFS
Aplikasi Algoritma BFS

Dalam tutorial ini, anda akan belajar mengenai algoritma carian pertama yang luas. Anda juga akan mendapat contoh algoritma bfs yang berfungsi di C, C ++, Java dan Python.

Traversal bermaksud melawat semua nod graf. Breadth First Traversal atau Breadth First Search adalah algoritma rekursif untuk mencari semua bucu graf atau struktur data pokok.

Algoritma BFS

Pelaksanaan BFS standard meletakkan setiap bucu grafik menjadi salah satu daripada dua kategori:

Dikunjungi
Tidak Dikunjungi

Tujuan algoritma adalah untuk menandakan setiap bucu sebagai dikunjungi sambil mengelakkan pusingan.

Algoritma berfungsi seperti berikut:

Mulakan dengan meletakkan salah satu bucu grafik di bahagian belakang barisan.
Ambil item depan barisan dan tambahkan ke senarai yang dikunjungi.
Buat senarai nod bersebelahan bucu itu. Tambahkan yang tidak ada dalam senarai yang dikunjungi ke bahagian belakang barisan.
Terus ulangi langkah 2 dan 3 sehingga barisan kosong.

Grafik mungkin mempunyai dua bahagian yang terputus yang berbeza sehingga untuk memastikan bahawa kita merangkumi setiap bucu, kita juga dapat menjalankan algoritma BFS pada setiap simpul

Contoh BFS

Mari lihat bagaimana algoritma Breadth First Search berfungsi dengan contoh. Kami menggunakan graf tidak terarah dengan 5 bucu.

Graf tak tentu dengan 5 bucu

Kami bermula dari bucu 0, algoritma BFS bermula dengan memasukkannya ke dalam senarai Dikunjungi dan meletakkan semua bucu bersebelahan di dalam timbunan.

Lawati bucu permulaan dan tambahkan bucu bersebelahan untuk beratur

Seterusnya, kami mengunjungi elemen di bahagian hadapan barisan iaitu 1 dan menuju ke simpul yang berdekatan. Oleh kerana 0 telah dilawati, kami hanya mengunjungi 2 orang.

Lawati jiran pertama simpul permulaan 0, yang merupakan 1

Vertex 2 mempunyai bucu bersebelahan yang tidak dikunjungi dalam 4, jadi kami menambahkannya di bahagian belakang barisan dan mengunjungi 3, yang berada di bahagian depan barisan.

Lawati 2 yang ditambahkan ke barisan sebelumnya untuk menambah

4 jirannya yang masih berada dalam barisan

Hanya 4 yang kekal dalam barisan kerana satu-satunya simpul bersebelahan 3 iaitu 0 sudah dikunjungi. Kami mengunjunginya.

Lawati item terakhir yang tersisa di timbunan untuk memeriksa sama ada item itu mempunyai jiran yang tidak dilawati

Oleh kerana barisan kosong, kami telah melengkapkan Breadth First Traversal grafik.

Pseudokod BFS

 buat tanda Q tanda giliran v seperti yang dikunjungi dan masukkan v ke dalam Q sementara Q tidak kosong keluarkan kepala u tanda Q dan masukkan semua jiran u (tidak dilawati)

Contoh Python, Java dan C / C ++

Kod untuk Algoritma Pencarian Pertama Breadth dengan contoh ditunjukkan di bawah. Kodnya telah dipermudahkan sehingga kita dapat memfokuskan pada algoritma daripada perincian lain.

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; )