BFS grafika algoritms (ar kodu C, C ++, Java un Python)

Satura rādītājs

BFS algoritms
BFS piemērs
BFS pseidokods
Python, Java un C / C ++ piemēri
BFS algoritmu sarežģītība
BFS algoritmu lietojumi

Šajā apmācībā jūs uzzināsit par pirmās meklēšanas algoritmu. Jūs atradīsit arī bfs algoritma piemērus C, C ++, Java un Python.

Traversāls nozīmē visu grafa mezglu apmeklēšanu. Breadth First Traversal jeb Breadth First Search ir rekursīvs algoritms, lai meklētu visas diagrammas vai koka datu struktūras virsotnes.

BFS algoritms

Standarta BFS ieviešana katru diagrammas virsotni iedala vienā no divām kategorijām:

Apmeklēja
Nav apmeklēts

Algoritma mērķis ir atzīmēt katru virsotni kā apmeklētu, izvairoties no cikliem.

Algoritms darbojas šādi:

Sāciet, ievietojot jebkuru no diagrammas virsotnēm rindas aizmugurē.
Paņemiet rindas priekšējo vienumu un pievienojiet to apmeklēto sarakstam.
Izveidojiet šīs virsotnes blakus esošo mezglu sarakstu. Pievienojiet tos, kas nav apmeklēto sarakstā, rindas aizmugurē.
Atkārtojiet 2. un 3. darbību, līdz rinda ir tukša.

Grafikā var būt divas atšķirīgas atvienotas daļas, tāpēc, lai pārliecinātos, ka mēs aptveram katru virsotni, mēs varam arī palaist BFS algoritmu katrā mezglā

BFS piemērs

Apskatīsim, kā darbojas Breadth First Search algoritms, ar piemēru. Mēs izmantojam nenovirzītu grafiku ar 5 virsotnēm.

Nevirzīts grafiks ar 5 virsotnēm

Mēs sākam no 0 virsotnes, BFS algoritms sākas, ievietojot to sarakstā Visited un ievietojot visas blakus esošās virsotnes kaudzē.

Apmeklējiet sākuma virsotni un pievienojiet tai blakus esošās virsotnes rindā

Pēc tam mēs apmeklējam elementu rindas priekšā, ti, 1 un dodamies uz blakus esošajiem mezgliem. Tā kā 0 jau ir apmeklēts, tā vietā mēs apmeklējam 2.

Apmeklējiet pirmo sākuma mezgla 0 kaimiņu, kas ir 1

2. virsotnei ir neapmeklēta blakus esošā virsotne 4, tāpēc mēs to pievienojam rindas aizmugurē un apmeklējam 3, kas atrodas rindas priekšpusē.

2. apmeklējums, kas tika pievienots rindai agrāk, lai pievienotu kaimiņus

4, paliek rindā

Rindā palikuši tikai 4, jo vienīgais blakus esošais mezgls ar 3, ti, 0 jau ir apmeklēts. Mēs to apmeklējam.

Apmeklējiet pēdējo atlikušo vienumu kaudzē, lai pārbaudītu, vai tajā nav apmeklēti kaimiņi

Tā kā rinda ir tukša, mēs esam pabeiguši diagrammas pirmo platuma šķērsošanu.

BFS pseidokods

 izveidojiet rindu Q atzīme v kā apmeklēta un ielieciet v Q, kamēr Q nav tukša, noņemiet Q atzīmes galviņu u un uzlieciet visus (neapmeklētos) kaimiņus u

Python, Java un C / C ++ piemēri

Zemāk ir parādīts platuma pirmās meklēšanas algoritma kods ar piemēru. Kods ir vienkāršots, lai mēs varētu koncentrēties uz algoritmu, nevis citām detaļām.

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