Breadth First Search

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node* next;
};
int del(struct node** head,int* element);
int add(struct node** head,int element);
//main program
int main()
{
    //input no of nodes: Num
    int Num;
    printf("Enter number of nodes\n");
    scanf("%d",&Num);
    //create adjacency matrix
    int adj[Num][Num];
    //input adjacency matrix
    printf("Enter adjacency matrix\n");
    for(int i=0;i<Num;i++)
    {
        for(int j=0;j<Num;j++)
        {
            scanf("%d",&adj[i][j]);
        }
    }
    //BFS traversing
    //create a queue
    struct node *Queue=NULL;
    //create status array and set it to ready state
    enum{ready,waiting,processed};
    int status[Num];
    for(int i=0;i<Num;i++)
    {
        status[i]=ready;
    }
    //add first node to queue
    add(&Queue,0);
    status[0]=waiting;
    int node=NULL;
    printf("BFS traversing\n");
    while(Queue!=NULL)
    {
        //get a node from queue, display it and change status to processed
        del(&Queue,&node);
        printf("%d ",node);
        status[node]=processed;
        //add it's neighbours with status ready to queue
        for(int i=0;i<Num;i++)
        {
            if(adj[node][i]==1 && status[i]==ready)
            {
                add(&Queue,i);
                status[i]=waiting;
            }
        }
    }
    printf("\n");
}
//queue functions
int del(struct node** head,int* element)
{
    if(*head==NULL)
        return 1;
    *element=(*head)->data;
    struct node* temp;
    temp=*head;
    *head=(*head)->next;
    free(temp);
    return 0;
}
int add(struct node** head,int element)
{
    if((*head)==NULL)
    {
        *head=(struct node*)malloc(sizeof(struct node));
        (*head)->next=NULL;
        (*head)->data=element;
        return 0;
    }
    struct node* temp=*head;
    while(temp->next!=NULL)
    {
        temp=temp->next;
    }
    temp->next=(struct node*)malloc(sizeof(struct node));
    if(temp->next==NULL)
        return 1;
    temp=temp->next;
    temp->data=element;
    temp->next=NULL;
    return 0;
}

#include <iostream>
#include <map>
#include <set>
#include <queue>
/* Part of Cosmos by OpenGenus Foundation */
void bfs(int start,                             // the node that we are currently at
         std::map<int, std::set<int>>& adjList, // the adjacency list for each node
         std::map<int, bool>& visited,          // the 'visited' state for each node
         std::map<int, int>& distance           // the distance from the `start` node
        ) {
    // First, clear the distance map, so that only nodes that we can actually reach from the `start` appear in it at the end
    distance.clear();
    // This queue wil hold pairs of numbers of the form (nodeNumber, distance)
    std::queue<std::pair<int, int>> Q;
    // Add the first node with distance 0 to the queue and mark it as visited
    Q.push(std::make_pair(start, 0));
    visited[start] = true;
    // Repeat the algorithm until there are no more ndoes left to process
    while (!Q.empty()) {
        // Take the node from the front of the queue and pop it off the queue
        auto entry = Q.front(); Q.pop();
        int node = entry.first;
        int dist = entry.second;
        // Put the distance to this node into the distance map (this is the minimal distance to this node)
        distance[node] = dist;
        // Iterate over the neighbours of the current node
        for (auto neighbour : adjList[node]) {
            if (!visited[neighbour]) {
                // Mark the neighbour node as visited
                visited[neighbour] = true;
                Q.push(std::make_pair(neighbour, dist + 1));
            }
        }
    }
}
void addEdge(int a, int b, std::map<int, std::set<int>>& adjList) {
    adjList[a].insert(b);
    adjList[b].insert(a);
}
int main() {
    /*
    Do a breadth-first search in this graph:
    1--2--4--7
    | / \    |
    |/   \   |
    3     5--6
    8--9
    */
    std::map<int, std::set<int>> adjList;
    std::map<int, bool> visited;
    std::map<int, int> dist;
    addEdge(1, 2, adjList);
    addEdge(1, 3, adjList);
    addEdge(2, 3, adjList);
    addEdge(2, 4, adjList);
    addEdge(2, 5, adjList);
    addEdge(4, 7, adjList);
    addEdge(5, 6, adjList);
    addEdge(6, 7, adjList);
    addEdge(8, 9, adjList);
    // Set all nodes as unvisited at first
    for (int i = 1; i <= 8; i++) visited[i] = false;
    // Perform a bfs from the node `1`
    bfs(1, adjList, visited, dist);
    // Print the distance to all visited nodes
    for (auto entry : dist) {
        std::cout << "Distance from 1 to " << entry.first << " is " << entry.second << std::endl;
    }
    return 0;
}

// Java program to print BFS traversal from a given source vertex.
import java.io.*;
import java.util.*;
// Part of Cosmos by OpenGenus Foundation
// This class represents a directed Graph using adjacency list representation
class Bfs
{
    private int V;   // No. of vertices
    private LinkedList<Integer> adj[]; //Adjacency Lists
    // Constructor of the class
    Bfs(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList();
        }
    }
    // Function to add an edge into the Graph
    void addEdge(int v,int w) {
        adj[v].add(w);
    }
    // prints BFS traversal from a given source s
    void BFS(int s) {
        // Mark all the vertices as not visited(By default
        // set as false)
        boolean visited[] = new boolean[V];
        // Create a queue for BFS
        LinkedList<Integer> queue = new LinkedList<Integer>();
        // Mark the current node as visited and enqueue it
        visited[s]=true;
        queue.add(s);
        while (queue.size() != 0) {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            System.out.print( s + " ");
            // Get all adjacent vertices of the dequeued vertex s
            // If a adjacent has not been visited, then mark it visited and enqueue it
            Iterator<Integer> i = adj[s].listIterator();
            while( i.hasNext()) {
                int n = i.next();
                if ( !visited[n] ) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
    // Driver method to
    public static void main(String args[]) {
        Bfs g = new Bfs(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);
        System.out.println();
    }
}

#   This class represents a node in a graph.
#   It has a NAME and an ID and each node knows which nodes it is connected to.
class GraphNode
  require 'set'
  @@id = 0
  attr_reader :name, :id, :connections
  def initialize(name)
    @name = name
    @id = (@@id += 1)
    @connections = Set.new
  end
  def connect(node)
    return false unless node.is_a? GraphNode
    @connections << node
  end
  def equal?(other)
    return false unless other.is_a? GraphNode
    @name == other.name && @id == other.id
  end
  def to_s
    "<GraphNode:#{name}>"
  end
  def to_str
    to_s
  end
end
#   A simple function as a default function performed for each node in bfs()
def goalNode?(node)
  node.name == 'Goal'
end
#   Given a start node and a function or code block this performs a bread first search and will exit upon function or code block returning true, or returns :goal_node_not_found when it has visited the whole graph.
#
#   visited is a set containing all nodes that has been checked.
#   frontier is a queue were new nodes are appended, making this a breadth first search.
def bfs(start, goal = :goalNode?)
  require 'set'
  visited = Set.new
  frontier = []
  frontier << start
  until frontier.empty?
    current = frontier.shift
    next if visited.include? current
    visited << current
    found = false
    found = if block_given?
              yield(current)
            else
              send(goal, current)
            end
    if !found
      current.connections.each do |node|
        frontier << node
      end
    else
      return current
    end
  end
  :goal_node_not_found
end
#   A small test that will use bfs() for root node First, then for the Second node.
#   The bfs accepts a code block, and here we just print each visited node and will never find the goal-node.
#
#   The tests output:
#   Testing from root node 'First'
#     <GraphNode:First>
#     <GraphNode:Second>
#     <GraphNode:Third>
#     <GraphNode:Fourth>
#     <GraphNode:Fifth>
#     <GraphNode:Goal>
#     <GraphNode:Sixth>
#   goal_node_not_found
#   Testing from second node 'Second'
#     <GraphNode:Second>
#     <GraphNode:First>
#     <GraphNode:Fourth>
#     <GraphNode:Fifth>
#     <GraphNode:Third>
#     <GraphNode:Goal>
#     <GraphNode:Sixth>
#   goal_node_not_found
def test
  puts 'Building Graph for tests...'
  #         Simple graph
  #
  #            First
  #           /     \
  #       second    third
  #      /     |    |    \
  #   fourth fifth  goal sixth
  #
  # Construct graph
  first = GraphNode.new 'First'
  second = GraphNode.new 'Second'
  third = GraphNode.new 'Third'
  fourth = GraphNode.new 'Fourth'
  fifth = GraphNode.new 'Fifth'
  sixth = GraphNode.new 'Sixth'
  goal = GraphNode.new 'Goal'
  first.connect second
  first.connect third
  second.connect first
  second.connect fourth
  second.connect fifth
  third.connect first
  third.connect goal
  third.connect sixth
  fourth.connect second
  fifth.connect second
  goal.connect third
  sixth.connect third
  # Perform tests
  puts "Testing from root node 'First'"
  puts(bfs(first) { |node| puts '  ' + node })
  puts "Testing from second node 'Second'"
  puts(bfs(second) { |node| puts '  ' + node })
end
test if $PROGRAM_NAME == __FILE__

""" Part of Cosmos by OpenGenus Foundation"""
import collections
"""
    Wrapper function for the print function.
    Used as the default visitFunc for bfs
"""
def visitPrint(i):
    print(i)
"""
    A class representing a undirected graph of nodes.
    An edge can be added between two nodes by calling addEdge
        *This class assumes all edge weights are equal
"""
class Graph:
    def __init__(self):
        self.adjList = collections.defaultdict(set)
    def addEdge(self, node1, node2):
        self.adjList[node1].add(node2)
        self.adjList[node2].add(node1)
"""
    Given a 'start' node and a 'graph', call visitFunc
    sequentially on the current node, and then its children
    and so forth.
    When visiting each node, mark it as visited by adding it to the hashmap.
    Then queue up all of its children to be visited next.
"""
def bfs(start, graph, visitFunc=visitPrint):
    visited = collections.defaultdict(bool)
    queue = collections.deque()
    queue.append(start)
    while(len(queue) > 0):
        current = queue.popleft()
        if (not visited[current]):
            visited[current] = True
            visitFunc(current)
            for neighbor in graph.adjList[current]:
                queue.append(neighbor)
# Testing the breadth first search implementation
if __name__ == "__main__":
    # Testing on this tree
    #      1
    #     / \
    #    /   \
    #   2     3
    #  / \   / \
    # 4   5 6   7
    g = Graph()
    g.addEdge(1, 2)
    g.addEdge(1, 3)
    g.addEdge(2, 4)
    g.addEdge(2, 5)
    g.addEdge(3, 6)
    g.addEdge(3, 7)
    print("Test 1:")
    bfs(1, g)
    print("\nTest2:")
    bfs(2, g)
    """Output:
    Test 1:
    1
    2
    3
    4
    5
    6
    7
    Test2:
    2
    1
    4
    5
    3
    6
    7
    """
    

  func breadthFirstSearch(_ graph: Graph, source: Node) -> [String] {
  var queue = Queue<Node>()
  queue.enqueue(source)
  var nodesExplored = [source.label]
  source.visited = true
  while let current = queue.dequeue() {
    for edge in current.neighbors {
      let neighborNode = edge.neighbor
      if !neighborNode.visited {
        queue.enqueue(neighborNode)
        neighborNode.visited = true
        nodesExplored.append(neighborNode.label)
      }
    }
  }
  return nodesExplored
}