BFS grafikų algoritmas (su kodu C, C ++, Java ir Python)

Turinys

BFS algoritmas
BFS pavyzdys
BFS pseudokodas
„Python“, „Java“ ir „C / C ++“ pavyzdžiai
BFS algoritmų sudėtingumas
BFS algoritmo programos

Šioje pamokoje sužinosite apie pirmosios paieškos algoritmą. Taip pat rasite veikiančių bfs algoritmo pavyzdžių C, C ++, Java ir Python.

Perėjimas reiškia aplankyti visus grafiko mazgus. Pirmojo „Platumo“ peržiūra arba „Pirmojo platumo paieška“ yra rekursyvus algoritmas, skirtas ieškoti visose grafiko ar medžio duomenų struktūros viršūnėse.

BFS algoritmas

Standartinis BFS diegimas kiekvieną grafiko viršūnę priskiria vienai iš dviejų kategorijų:

Aplankyta
Nesilankė

Algoritmo tikslas yra pažymėti kiekvieną viršūnę kaip aplankytą, vengiant ciklų.

Algoritmas veikia taip:

Pradėkite uždėdami bet kurią iš grafiko viršūnių eilės gale.
Paimkite priekinį eilės elementą ir įtraukite jį į aplankytą sąrašą.
Sukurkite tos viršūnės gretimų mazgų sąrašą. Į eilės galą įtraukite tuos, kurie nėra aplankytų sąraše.
Kartokite 2 ir 3 veiksmus, kol eilė bus tuščia.

Grafike gali būti dvi skirtingos atjungtos dalys, todėl, norėdami įsitikinti, kad padengiame kiekvieną viršūnę, mes taip pat galime paleisti BFS algoritmą kiekviename mazge

BFS pavyzdys

Pažiūrėkime, kaip veikia „Breadth First Search“ algoritmas su pavyzdžiu. Mes naudojame nenukreiptą grafiką su 5 viršūnėmis.

Nenukreiptas grafikas su 5 viršūnėmis

Pradedame nuo 0 viršūnės, BFS algoritmas prasideda įtraukiant jį į aplankytą sąrašą ir visas gretimas viršūnes dedant į kaminą.

Apsilankykite pradžios viršūnėje ir pridėkite šalia esančias viršūnes prie eilės

Tada aplankysime eilės priekyje esantį elementą, ty 1 ir eisime prie jo gretimų mazgų. Kadangi 0 jau aplankyta, vietoj to aplankome 2.

Aplankykite pirmąjį pradinio mazgo 0 kaimyną, kuris yra 1

2 viršūnėje yra neaplankyta gretima 4 viršūnė, todėl mes ją įtraukiame į eilės galą ir aplankome 3, kuris yra eilės priekyje.

Apsilankykite 2, kuris buvo įtrauktas į eilę anksčiau

, kad eilėje liktų 4 kaimynai

Eilėje lieka tik 4, nes vienintelis gretimas mazgas 3, ty 0, jau aplankytas. Mes jį aplankome.

Apsilankykite paskutiniame kamino elemente ir patikrinkite, ar jis neaplankytų kaimynų

Kadangi eilė tuščia, mes užbaigėme grafiko pirmąjį platumą.

BFS pseudokodas

 sukurkite eilę Q ženklas v, kai lankėtės, ir įdėkite v į Q, kol Q yra tuščias, nuimkite Q ženklo galvutę u ir surinkite visus (nelankytus) kaimynus

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

Žemiau parodytas „Platumo pirmosios paieškos“ algoritmo kodas su pavyzdžiu. Kodas buvo supaprastintas, kad galėtume sutelkti dėmesį į algoritmą, o ne į kitas detales.

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