الگوریتم BFS چیست؟ – به زبان ساده + مثال

1#include <stdbool.h>
2#include <stdio.h>
3#include <stdlib.h>
4 
5#define MAX_VERTICES 50
6 
7// This struct represents a directed graph using
8// adjacency list representation
9typedef struct Graph_t {
10     
11    // No. of vertices
12    int V;
13    bool adj[MAX_VERTICES][MAX_VERTICES];
14} Graph;
15 
16// Constructor
17Graph* Graph_create(int V)
18{
19    Graph* g = malloc(sizeof(Graph));
20    g->V = V;
21 
22    for (int i = 0; i < V; i++) {
23        for (int j = 0; j < V; j++) {
24            g->adj[i][j] = false;
25        }
26    }
27 
28    return g;
29}
30 
31// Destructor
32void Graph_destroy(Graph* g) {
33    free(g);
34}
35 
36// function to add an edge to graph
37void Graph_addEdge(Graph* g, int v, int w)
38{
39    // Add w to v’s list.
40    g->adj[v][w] = true;
41}
42 
43// Prints BFS traversal from a given source s
44void Graph_BFS(Graph* g, int s)
45{
46    // Mark all the vertices as not visited
47    bool visited[MAX_VERTICES];
48    for (int i = 0; i < g->V; i++) {
49        visited[i] = false;
50    }
51 
52    // Create a queue for BFS
53    int queue[MAX_VERTICES];
54    int front = 0, rear = 0;
55 
56    // Mark the current node as visited and enqueue it
57    visited[s] = true;
58    queue[rear++] = s;
59 
60    while (front != rear) {
61        // Dequeue a vertex from queue and print it
62        s = queue[front++];
63        printf("%d ", s);
64 
65        // Get all adjacent vertices of the dequeued
66        // vertex s. If a adjacent has not been visited,
67        // then mark it visited and enqueue it
68        for (int adjacent = 0; adjacent < g->V;
69             adjacent++) {
70            if (g->adj[s][adjacent] && !visited[adjacent]) {
71                visited[adjacent] = true;
72                queue[rear++] = adjacent;
73            }
74        }
75    }
76}
77 
78// Driver code
79int main()
80{
81    // Create a graph
82    Graph* g = Graph_create(4);
83    Graph_addEdge(g, 0, 1);
84    Graph_addEdge(g, 0, 2);
85    Graph_addEdge(g, 1, 2);
86    Graph_addEdge(g, 2, 0);
87    Graph_addEdge(g, 2, 3);
88    Graph_addEdge(g, 3, 3);
89 
90    printf("Following is Breadth First Traversal "
91           "(starting from vertex 2) \n");
92    Graph_BFS(g, 2);
93    Graph_destroy(g);
94 
95    return 0;
96}

1// C++ code to print BFS traversal from a given
2// source vertex
3 
4#include <bits/stdc++.h>
5using namespace std;
6 
7// This class represents a directed graph using
8// adjacency list representation
9class Graph {
10 
11    // No. of vertices
12    int V;
13 
14    // Pointer to an array containing adjacency lists
15    vector<list<int> > adj;
16 
17public:
18    // Constructor
19    Graph(int V);
20 
21    // Function to add an edge to graph
22    void addEdge(int v, int w);
23 
24    // Prints BFS traversal from a given source s
25    void BFS(int s);
26};
27 
28Graph::Graph(int V)
29{
30    this->V = V;
31    adj.resize(V);
32}
33 
34void Graph::addEdge(int v, int w)
35{
36    // Add w to v’s list.
37    adj[v].push_back(w);
38}
39 
40void Graph::BFS(int s)
41{
42    // Mark all the vertices as not visited
43    vector<bool> visited;
44    visited.resize(V, false);
45 
46    // Create a queue for BFS
47    list<int> queue;
48 
49    // Mark the current node as visited and enqueue it
50    visited[s] = true;
51    queue.push_back(s);
52 
53    while (!queue.empty()) {
54         
55        // Dequeue a vertex from queue and print it
56        s = queue.front();
57        cout << s << " ";
58        queue.pop_front();
59 
60        // Get all adjacent vertices of the dequeued
61        // vertex s. If a adjacent has not been visited,
62        // then mark it visited and enqueue it
63        for (auto adjacent : adj[s]) {
64            if (!visited[adjacent]) {
65                visited[adjacent] = true;
66                queue.push_back(adjacent);
67            }
68        }
69    }
70}
71 
72// Driver code
73int main()
74{
75    // Create a graph given in the above diagram
76    Graph g(4);
77    g.addEdge(0, 1);
78    g.addEdge(0, 2);
79    g.addEdge(1, 2);
80    g.addEdge(2, 0);
81    g.addEdge(2, 3);
82    g.addEdge(3, 3);
83 
84    cout << "Following is Breadth First Traversal "
85         << "(starting from vertex 2) \n";
86    g.BFS(2);
87 
88    return 0;
89}

1// C# program to print BFS traversal from a given source
2// vertex. BFS(int s) traverses vertices reachable from s.
3 
4using System;
5using System.Collections.Generic;
6using System.Linq;
7using System.Text;
8 
9// This class represents a directed graph
10// using adjacency list representation
11class Graph {
12 
13    // No. of vertices
14    private int _V;
15 
16    // Adjacency Lists
17    LinkedList<int>[] _adj;
18 
19    public Graph(int V)
20    {
21        _adj = new LinkedList<int>[ V ];
22        for (int i = 0; i < _adj.Length; i++) {
23            _adj[i] = new LinkedList<int>();
24        }
25        _V = V;
26    }
27 
28    // Function to add an edge into the graph
29    public void AddEdge(int v, int w)
30    {
31        _adj[v].AddLast(w);
32    }
33 
34    // Prints BFS traversal from a given source s
35    public void BFS(int s)
36    {
37 
38        // Mark all the vertices as not
39        // visited(By default set as false)
40        bool[] visited = new bool[_V];
41        for (int i = 0; i < _V; i++)
42            visited[i] = false;
43 
44        // Create a queue for BFS
45        LinkedList<int> queue = new LinkedList<int>();
46 
47        // Mark the current node as
48        // visited and enqueue it
49        visited[s] = true;
50        queue.AddLast(s);
51 
52        while (queue.Any()) {
53 
54            // Dequeue a vertex from queue
55            // and print it
56            s = queue.First();
57            Console.Write(s + " ");
58            queue.RemoveFirst();
59 
60            // Get all adjacent vertices of the
61            // dequeued vertex s. If a adjacent
62            // has not been visited, then mark it
63            // visited and enqueue it
64            LinkedList<int> list = _adj[s];
65 
66            foreach(var val in list)
67            {
68                if (!visited[val]) {
69                    visited[val] = true;
70                    queue.AddLast(val);
71                }
72            }
73        }
74    }
75 
76    // Driver code
77    static void Main(string[] args)
78    {
79        Graph g = new Graph(4);
80        g.AddEdge(0, 1);
81        g.AddEdge(0, 2);
82        g.AddEdge(1, 2);
83        g.AddEdge(2, 0);
84        g.AddEdge(2, 3);
85        g.AddEdge(3, 3);
86 
87        Console.Write("Following is Breadth First "
88                      + "Traversal(starting from "
89                      + "vertex 2) \n");
90        g.BFS(2);
91    }
92}
93 
94// This code is contributed by anv89

1// Java program to print BFS traversal from a given source
2// vertex. BFS(int s) traverses vertices reachable from s.
3 
4import java.io.*;
5import java.util.*;
6 
7// This class represents a directed graph using adjacency
8// list representation
9class Graph {
10 
11    // No. of vertices
12    private int V;
13 
14    // Adjacency Lists
15    private LinkedList<Integer> adj[];
16 
17    // Constructor
18    Graph(int v)
19    {
20        V = v;
21        adj = new LinkedList[v];
22        for (int i = 0; i < v; ++i)
23            adj[i] = new LinkedList();
24    }
25 
26    // Function to add an edge into the graph
27    void addEdge(int v, int w) { adj[v].add(w); }
28 
29    // prints BFS traversal from a given source s
30    void BFS(int s)
31    {
32        // Mark all the vertices as not visited(By default
33        // set as false)
34        boolean visited[] = new boolean[V];
35 
36        // Create a queue for BFS
37        LinkedList<Integer> queue
38            = new LinkedList<Integer>();
39 
40        // Mark the current node as visited and enqueue it
41        visited[s] = true;
42        queue.add(s);
43 
44        while (queue.size() != 0) {
45             
46            // Dequeue a vertex from queue and print it
47            s = queue.poll();
48            System.out.print(s + " ");
49 
50            // Get all adjacent vertices of the dequeued
51            // vertex s If a adjacent has not been visited,
52            // then mark it visited and enqueue it
53            Iterator<Integer> i = adj[s].listIterator();
54            while (i.hasNext()) {
55                int n = i.next();
56                if (!visited[n]) {
57                    visited[n] = true;
58                    queue.add(n);
59                }
60            }
61        }
62    }
63 
64    // Driver code
65    public static void main(String args[])
66    {
67        Graph g = new Graph(4);
68        g.addEdge(0, 1);
69        g.addEdge(0, 2);
70        g.addEdge(1, 2);
71        g.addEdge(2, 0);
72        g.addEdge(2, 3);
73        g.addEdge(3, 3);
74 
75        System.out.println(
76            "Following is Breadth First Traversal "
77            + "(starting from vertex 2)");
78 
79        g.BFS(2);
80    }
81}
82 
83// This code is contributed by Aakash Hasija

1// Javacript Program to print BFS traversal from a given
2    // source vertex. BFS(int s) traverses vertices
3    // reachable from s.
4     
5     
6    // This class represents a directed graph using
7    // adjacency list representation
8    class Graph
9    {
10         
11        // Constructor
12        constructor(v)
13        {
14            this.V = v;
15            this.adj = new Array(v);
16            for(let i = 0; i < v; i++)
17                this.adj[i] = [];
18        }
19         
20        // Function to add an edge into the graph
21        addEdge(v, w)
22        {
23             
24            // Add w to v's list.
25            this.adj[v].push(w);
26        }
27         
28        // prints BFS traversal from a given source s
29        BFS(s)
30        {
31            // Mark all the vertices as not visited(By default
32            // set as false)
33            let visited = new Array(this.V);
34            for(let i = 0; i < this.V; i++)
35                visited[i] = false;
36             
37            // Create a queue for BFS
38            let queue=[];
39             
40            // Mark the current node as visited and enqueue it
41            visited[s]=true;
42            queue.push(s);
43             
44            while(queue.length>0)
45            {
46                // Dequeue a vertex from queue and print it
47                s = queue[0];
48                console.log(s+" ");
49                queue.shift();
50                 
51                // Get all adjacent vertices of the dequeued
52                // vertex s. If a adjacent has not been visited,
53                // then mark it visited and enqueue it
54                this.adj[s].forEach((adjacent,i) => {
55                    if(!visited[adjacent])
56                    {
57                        visited[adjacent]=true;
58                        queue.push(adjacent);
59                    }
60                });
61            }
62        }
63    }
64     
65    // Driver program to test methods of graph class
66     
67    // Create a graph given in the above diagram
68    g = new Graph(4);
69    g.addEdge(0, 1);
70    g.addEdge(0, 2);
71    g.addEdge(1, 2);
72    g.addEdge(2, 0);
73    g.addEdge(2, 3);
74    g.addEdge(3, 3);
75     
76    console.log("Following is Breadth First Traversal " +
77                "(starting from vertex 2) ");
78     
79    g.BFS(2);
80     
81    // This code is contributed by Aman Kumar.

1# Python3 Program to print BFS traversal
2# from a given source vertex. BFS(int s)
3# traverses vertices reachable from s.
4 
5from collections import defaultdict
6 
7 
8# This class represents a directed graph
9# using adjacency list representation
10class Graph:
11 
12    # Constructor
13    def __init__(self):
14 
15        # Default dictionary to store graph
16        self.graph = defaultdict(list)
17 
18    # Function to add an edge to graph
19    def addEdge(self, u, v):
20        self.graph[u].append(v)
21 
22    # Function to print a BFS of graph
23    def BFS(self, s):
24 
25        # Mark all the vertices as not visited
26        visited = [False] * (max(self.graph) + 1)
27 
28        # Create a queue for BFS
29        queue = []
30 
31        # Mark the source node as
32        # visited and enqueue it
33        queue.append(s)
34        visited[s] = True
35 
36        while queue:
37 
38            # Dequeue a vertex from
39            # queue and print it
40            s = queue.pop(0)
41            print(s, end=" ")
42 
43            # Get all adjacent vertices of the
44            # dequeued vertex s. If a adjacent
45            # has not been visited, then mark it
46            # visited and enqueue it
47            for i in self.graph[s]:
48                if visited[i] == False:
49                    queue.append(i)
50                    visited[i] = True
51 
52 
53# Driver code
54if __name__ == '__main__':
55 
56    # Create a graph given in
57    # the above diagram
58    g = Graph()
59    g.addEdge(0, 1)
60    g.addEdge(0, 2)
61    g.addEdge(1, 2)
62    g.addEdge(2, 0)
63    g.addEdge(2, 3)
64    g.addEdge(3, 3)
65 
66    print("Following is Breadth First Traversal"
67          " (starting from vertex 2)")
68    g.BFS(2)
69 
70# This code is contributed by Neelam Yadav