{"id":16117,"date":"2023-05-05T05:58:08","date_gmt":"2023-05-05T05:58:08","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=16117"},"modified":"2023-05-05T05:58:08","modified_gmt":"2023-05-05T05:58:08","slug":"graph-traversal-in-data-structure","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/graph-traversal-in-data-structure\/","title":{"rendered":"Graph Traversal in Data Structure"},"content":{"rendered":"

\"\"<\/p>\n

A graph is a non-linear data structure composed of vertices and edges. Edges are lines or arcs that connect any two nodes in the network. Vertices are also known as nodes. A graph, in more technical terms, is made up of vertices (V) and edges (E). The representation of a graph is G(E, V). So, in this article, we will look at some Graph Traversal Techniques.<\/p>\n

Graph Traversal in Data Structure<\/h2>\n

We can traverse a graph in two ways :<\/p>\n

    \n
  1. BFS ( Breadth First Search )<\/li>\n
  2. DFS ( Depth First Search )<\/li>\n<\/ol>\n

    BFS Graph Traversal in Data Structure<\/h3>\n

    Breadth-first search (BFS) traversal is a technique for visiting all nodes in a given network. This traversal algorithm selects a node and visits all nearby nodes in order. After checking all nearby vertices, examine another set of vertices, then recheck adjacent vertices. This algorithm uses a queue as a data structure as an additional data structure to store nodes for further processing. Queue size is the maximum total number of vertices in the graph. <\/p>\n

    Graph Traversal: BFS Algorithm<\/h3>\n

    Pseudo Code :<\/strong><\/p>\n

    def bfs(graph, start_node):\n    queue = [start_node]\n    visited = set()\n\n    while queue:\n        node = queue.pop(0)\n\n        if node not in visited:\n            visited.add(node)\n            print(node)\n\n            for neighbor in graph[node]:\n                queue.append(neighbor)<\/code><\/pre>\n
    Explanation of the above Pseudocode<\/strong><\/p>\n
      \n
    • The technique starts by creating a queue with the start node and an empty set to keep track of visited nodes. <\/li>\n
    • It then starts a loop that continues until all nodes have been visited.<\/li>\n
    • During each loop iteration, the algorithm dequeues the first node from the queue, checks if it has been visited and if not, marks it as visited, prints it (or performs any other desired action), and adds all its adjacent nodes to the queue. <\/li>\n
    • The operation is repeated until the queue is empty, indicating that all nodes have been visited.<\/li>\n<\/ul>\n
      Let us understand the algorithm using a diagram.<\/strong><\/p>\n
      \"\"<\/p>\n
      In the above diagram, the full way of traversing is shown using arrows.<\/p>\n
        \n
      • Step 1:<\/strong> Create a Queue with the same size as the total number of vertices in the graph. <\/li>\n
      • Step 2:<\/strong> Choose 12 as your beginning point for the traversal. Visit 12 and add it to the Queue.  <\/li>\n
      • Step 3:<\/strong> Insert all the adjacent vertices of 12 that are in front of the Queue but have not been visited into the Queue. So far, we have 5, 23, and 3.<\/li>\n
      • Step 4:<\/strong> Delete the vertex in front of the Queue when there are no new vertices to visit from that vertex. We now remove 12 from the list.<\/li>\n
      • Step 5:<\/strong> Continue steps 3 and 4 until the queue is empty.  <\/li>\n
      • Step 6:<\/strong> When the queue is empty, generate the final spanning tree by eliminating unnecessary graph edges. <\/li>\n<\/ul>\n
        Code Implementation<\/strong><\/p>\n\t\t\t\t\t\t