BFS Grafik Algoritması (C, C ++, Java ve Python kodlu)

İçindekiler

BFS algoritması
BFS örneği
BFS sözde kodu
Python, Java ve C / C ++ Örnekleri
BFS Algoritma Karmaşıklığı
BFS Algoritma Uygulamaları

Bu eğitimde, genişlikte ilk arama algoritması hakkında bilgi edineceksiniz. Ayrıca, C, C ++, Java ve Python'da bfs algoritmasının çalışan örneklerini bulacaksınız.

Geçiş, bir grafiğin tüm düğümlerini ziyaret etmek anlamına gelir. Genişlik İlk Geçiş veya Genişlik İlk Arama, bir grafiğin veya ağaç veri yapısının tüm köşelerini aramak için özyinelemeli bir algoritmadır.

BFS algoritması

Standart bir BFS uygulaması, grafiğin her köşesini iki kategoriden birine yerleştirir:

Ziyaret
Ziyaret Edilmedi

Algoritmanın amacı, döngülerden kaçınırken her bir tepe noktasını ziyaret edilmiş olarak işaretlemektir.

Algoritma şu şekilde çalışır:

Bir kuyruğun arkasına grafiğin köşelerinden herhangi birini koyarak başlayın.
Sıranın ön öğesini alın ve ziyaret edilenler listesine ekleyin.
Bu tepe noktasının bitişik düğümlerinin bir listesini oluşturun. Ziyaret edilenler listesinde olmayanları sıranın arkasına ekleyin.
Sıra boşalana kadar 2. ve 3. adımları tekrarlamaya devam edin.

Grafik iki farklı bağlantısız parçaya sahip olabilir, bu nedenle her köşeyi kapsadığımızdan emin olmak için BFS algoritmasını her düğümde çalıştırabiliriz.

BFS örneği

Önce Genişlik Arama algoritmasının nasıl çalıştığını bir örnekle görelim. 5 köşeli yönsüz bir grafik kullanıyoruz.

5 köşeli yönlendirilmemiş grafik

Tepe 0'dan başlıyoruz, BFS algoritması onu Ziyaret Edilenler listesine koyarak ve tüm bitişik köşelerini yığına koyarak başlıyor.

Başlangıç köşesini ziyaret edin ve bitişik köşelerini sıraya ekleyin

Daha sonra, sıranın önündeki elemanı, yani 1'i ziyaret ediyoruz ve bitişiğindeki düğümlere gidiyoruz. 0 zaten ziyaret edildiğinden, bunun yerine 2'yi ziyaret ediyoruz.

Başlangıç düğümü 0'ın ilk komşusu olan 1'i ziyaret edin

Vertex 2, 4'te ziyaret edilmemiş bir bitişik köşeye sahiptir, bu nedenle bunu sıranın arkasına ekliyoruz ve sıranın önündeki 3. ziyaret ediyoruz.

Komşularını eklemek için daha önce sıraya eklenen 2. ziyaret

4 sırada kalır

Sıradaki tek bitişik düğüm olan 3 yani 0 zaten ziyaret edildiğinden yalnızca 4 tanesi kuyrukta kalır. Onu ziyaret ediyoruz.

Ziyaret edilmemiş komşuları olup olmadığını kontrol etmek için yığında kalan son öğeyi ziyaret edin

Kuyruk boş olduğu için, grafiğin Genişlik İlk Geçişini tamamladık.

BFS sözde kodu

 Q işareti v'yi ziyaret edilmiş olarak oluşturun ve Q boş değilken v'yi Q'ya koyun Q işaretinin u kafasını kaldırın ve u'nun tüm (ziyaret edilmemiş) komşularını sıraya koyun

Python, Java ve C / C ++ Örnekleri

Bir örnekle Genişlik İlk Arama Algoritmasının kodu aşağıda gösterilmiştir. Kod, diğer detaylar yerine algoritmaya odaklanabilmemiz için basitleştirildi.

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