БФС алгоритам графикона (са кодом на Ц, Ц ++, Јава и Питхон)

Преглед садржаја

БФС алгоритам
Пример БФС-а
БФС псеудоцоде
Примери за Питхон, Јава и Ц / Ц ++
Сложеност алгоритма БФС
Примене БФС алгоритма

У овом упутству ћете научити о алгоритму претраживања по ширини. Такође ћете наћи радне примере бфс алгоритма на Ц, Ц ++, Јава и Питхон.

Прелазак значи посећивање свих чворова графа. Прелазак прве ширине или Прва ширина претрага је рекурзивни алгоритам за претрагу свих врхова графикона или структуре података стабла.

БФС алгоритам

Стандардна БФС имплементација ставља сваки врх графикона у једну од две категорије:

Посетили
Није посећено

Сврха алгоритма је да означи сваки врх као посећени, избегавајући циклусе.

Алгоритам ради на следећи начин:

Почните стављањем било ког од врхова графа на задњу страну реда.
Узмите предњу ставку реда и додајте је на посећену листу.
Направите листу суседних чворова тог темена. Додајте оне који нису на посећеној листи на задњи део реда.
Понављајте кораке 2 и 3 док се ред не испразни.

График може имати два различита неповезана дела, тако да бисмо били сигурни да покривамо сваки врх, такође можемо покренути БФС алгоритам на сваком чвору

Пример БФС-а

Погледајмо како алгоритам Бреадтх Фирст Сеарцх функционише на примеру. Користимо неусмерени граф са 5 темена.

Неусмерени граф са 5 темена

Полазимо од темена 0, алгоритам БФС започиње стављањем на листу Посећено и стављањем свих суседних врхова у стек.

Посетите почетни врх и додајте суседна темена у ред

Даље, посећујемо елемент на чекању реда тј. 1 и идемо до његових суседних чворова. С обзиром да је 0 већ посећено, уместо тога посетимо 2.

Посетите првог суседа стартног чвора 0, који је 1

Вертек 2 има непосећени суседни темен у 4, па то додајемо на задњи део реда и посећујемо 3, који се налази испред чеканог реда.

Посета 2 која је раније додата у ред за додавање својих суседа

4 остаје у реду

Само 4 остаје у реду пошто је једини суседни чвор од 3, тј. 0 већ посећен. Посећујемо га.

Посетите последњу преосталу ставку у стеку да бисте проверили да ли има непосећених суседа

Пошто је ред празан, завршили смо прво прелажење ширине графикона.

БФС псеудоцоде

 створите ред К ознака в као посећено и ставите в К док К није празан уклоните главу у К ознаке и ставите у ред све (непосећене) комшије у

Примери за Питхон, Јава и Ц / Ц ++

Шифра алгоритма за прво претраживање ширине са примером је приказана испод. Код је поједностављен тако да се можемо усредсредити на алгоритам, а не на друге детаље.

Питхон Јава Ц Ц +

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