{"id":"9ea389f7-ec10-4545-b7bd-8122e4f4b136","name":"Breadth First Traversal","description":"1. You are given a graph, and a src vertex.\r\n2. You are required to do a breadth first traversal and print which vertex is reached via which path, \r\n starting from the src.\r\n\r\nNote -> for output, check the sample output and question video.","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <queue>\n#include<string>\nusing namespace std;\n\nclass Edge\n{\npublic:\n int src = 0;\n int nbr = 0;\n\n Edge(int src, int nbr)\n {\n this->src = src; \n this->nbr = nbr;\n }\n};\n\n \n\nint main() { \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\n \n\n int edges;\n cin >> edges;\n\n for (int i = 0; i < edges; i++ ) {\n int u, v, w; \n cin >> u >> v >> w;\n graph[u].push_back(Edge(u, v));\n graph[v].push_back(Edge(v, u));\n } \n \n int src; \n cin >> src;\n // write your code here \n\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n\r\n Edge(int src, int nbr) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n graph[v1].add(new Edge(v1, v2));\r\n graph[v2].add(new Edge(v2, v1));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n\r\n // write your code here \r\n }\r\n}"},"python":{"code":"class Edge:\n def __init__(self,src,nbr):\n self.src = src\n self.nbr = nbr\n\n\ndef main():\n vtces = int(input())\n edges = int(input())\n graph = {}\n for i in range(vtces):\n graph[i] = []\n \n for i in range(edges):\n lines = input().split(\" \")\n v1=int(lines[0])\n v2=int(lines[1])\n e1 = Edge(v1 ,v2)\n e2 = Edge(v2 ,v1)\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n \n src=int(input())\n #write your code here \n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n8\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 10\r\n3 4 10\r\n4 5 10\r\n5 6 10\r\n4 6 10\r\n2","sampleOutput":"2@2\r\n1@21\r\n3@23\r\n0@210\r\n4@234\r\n5@2345\r\n6@2346","questionVideo":"https://www.youtube.com/embed/GHnC5qHexsk?end=423","hints":[],"associated":[{"id":"51b03c22-9a1d-4882-8457-b33fde69047a","name":"(Breadth First Traversal) The time taken to traverse a graph using BFS and DFS is","slug":"breadth-first-traversal-the-time-taken-to-traverse-a-graph-using-bfs-and-dfs-is","type":4},{"id":"8e341e29-4087-419c-83fc-712353f7a137","name":"DFS can be done without using queues, true or false? (Breadth First Traversal)","slug":"dfs-can-be-done-without-using-queues-true-or-false-breadth-first-traversal","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"bd9d1e1b-d4ae-4bb6-89ee-9f1a02c33cc6","name":"Breadth First Traversal","slug":"breadth-first-traversal","type":1}],"next":{"id":"d503ed5e-2def-4f47-91b3-fdd8774dfc09","name":"BREADTH FIRST TRAVERSAL","type":3,"slug":"breadth-first-traversal"},"prev":{"id":"d0bfafb3-548c-430a-8034-fa4daae93781","name":"Knights Tour","type":3,"slug":"knights-tour"}}}

Breadth First Traversal

1. You are given a graph, and a src vertex. 2. You are required to do a breadth first traversal and print which vertex is reached via which path, starting from the src. Note -> for output, check the sample output and question video.

{"id":"9ea389f7-ec10-4545-b7bd-8122e4f4b136","name":"Breadth First Traversal","description":"1. You are given a graph, and a src vertex.\r\n2. You are required to do a breadth first traversal and print which vertex is reached via which path, \r\n starting from the src.\r\n\r\nNote -> for output, check the sample output and question video.","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n#include <queue>\n#include<string>\nusing namespace std;\n\nclass Edge\n{\npublic:\n int src = 0;\n int nbr = 0;\n\n Edge(int src, int nbr)\n {\n this->src = src; \n this->nbr = nbr;\n }\n};\n\n \n\nint main() { \n int vtces;\n cin >> vtces;\n vector<vector<Edge>> graph(vtces, vector<Edge>());\n \n\n int edges;\n cin >> edges;\n\n for (int i = 0; i < edges; i++ ) {\n int u, v, w; \n cin >> u >> v >> w;\n graph[u].push_back(Edge(u, v));\n graph[v].push_back(Edge(v, u));\n } \n \n int src; \n cin >> src;\n // write your code here \n\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n static class Edge {\r\n int src;\r\n int nbr;\r\n\r\n Edge(int src, int nbr) {\r\n this.src = src;\r\n this.nbr = nbr;\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n int vtces = Integer.parseInt(br.readLine());\r\n ArrayList<Edge>[] graph = new ArrayList[vtces];\r\n for (int i = 0; i < vtces; i++) {\r\n graph[i] = new ArrayList<>();\r\n }\r\n\r\n int edges = Integer.parseInt(br.readLine());\r\n for (int i = 0; i < edges; i++) {\r\n String[] parts = br.readLine().split(\" \");\r\n int v1 = Integer.parseInt(parts[0]);\r\n int v2 = Integer.parseInt(parts[1]);\r\n graph[v1].add(new Edge(v1, v2));\r\n graph[v2].add(new Edge(v2, v1));\r\n }\r\n\r\n int src = Integer.parseInt(br.readLine());\r\n\r\n // write your code here \r\n }\r\n}"},"python":{"code":"class Edge:\n def __init__(self,src,nbr):\n self.src = src\n self.nbr = nbr\n\n\ndef main():\n vtces = int(input())\n edges = int(input())\n graph = {}\n for i in range(vtces):\n graph[i] = []\n \n for i in range(edges):\n lines = input().split(\" \")\n v1=int(lines[0])\n v2=int(lines[1])\n e1 = Edge(v1 ,v2)\n e2 = Edge(v2 ,v1)\n graph[e1.src].append(e1)\n graph[e2.src].append(e2)\n \n src=int(input())\n #write your code here \n \nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"7\r\n8\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 10\r\n3 4 10\r\n4 5 10\r\n5 6 10\r\n4 6 10\r\n2","sampleOutput":"2@2\r\n1@21\r\n3@23\r\n0@210\r\n4@234\r\n5@2345\r\n6@2346","questionVideo":"https://www.youtube.com/embed/GHnC5qHexsk?end=423","hints":[],"associated":[{"id":"51b03c22-9a1d-4882-8457-b33fde69047a","name":"(Breadth First Traversal) The time taken to traverse a graph using BFS and DFS is","slug":"breadth-first-traversal-the-time-taken-to-traverse-a-graph-using-bfs-and-dfs-is","type":4},{"id":"8e341e29-4087-419c-83fc-712353f7a137","name":"DFS can be done without using queues, true or false? (Breadth First Traversal)","slug":"dfs-can-be-done-without-using-queues-true-or-false-breadth-first-traversal","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"02ab8fe3-cddd-43ad-b241-b8b1a2fcd52e","name":"Graphs For Beginners","slug":"graphs-for-beginners","type":0},{"id":"bd9d1e1b-d4ae-4bb6-89ee-9f1a02c33cc6","name":"Breadth First Traversal","slug":"breadth-first-traversal","type":1}],"next":{"id":"d503ed5e-2def-4f47-91b3-fdd8774dfc09","name":"BREADTH FIRST TRAVERSAL","type":3,"slug":"breadth-first-traversal"},"prev":{"id":"d0bfafb3-548c-430a-8034-fa4daae93781","name":"Knights Tour","type":3,"slug":"knights-tour"}}}
plane

Editor

Loading...

Breadth First Traversal

easy

1. You are given a graph, and a src vertex. 2. You are required to do a breadth first traversal and print which vertex is reached via which path, starting from the src. Note -> for output, check the sample output and question video.

Constraints

None

Format

Input

Input has been managed for you

Output

Check the sample output

Example

Sample Input

7 8 0 1 10 1 2 10 2 3 10 0 3 10 3 4 10 4 5 10 5 6 10 4 6 10 2

Sample Output

2@2 1@21 3@23 0@210 4@234 5@2345 6@2346

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode