{"id":"4c999483-81a5-49d6-beed-c9d005ea87ad","name":"Iterative Depth First Traversal","description":"1. You are given a graph, and a source vertex.\r\n2. You are required to do a iterative depth first traversal and print which vertex is reached via which \r\n path, starting from the source.\r\n\r\nNote -> For output, check the sample output and question video. Iterative depth first traversal \r\n should mimic \"Reverse preorder\" i.e. nbr with highest value should be visited first and \r\n should be printed on the way down in recursion.","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n\nusing namespace std;\n\nclass Edge\n{ \npublic:\n int src = 0; \n int nbr = 0;\n int wt = 0;\n \n\n Edge(int src, int nbr,int wt)\n {\n this->src = src; \n this->nbr = nbr; \n this->wt = wt; \n\n }\n};\n\n\nint main() { \n \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 \n graph[u].push_back(Edge(u, v, w)); \n graph[v].push_back(Edge(v, u, w)); \n } \n int src;\n cin >> src; \n //write your code here \n \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":"import threading , queue\n\nclass Edge:\n def __init__(self,src,nbr,wt):\n self.src = src\n self.nbr = nbr\n self.wt = wt\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 wt=int(lines[2])\n e1 = Edge(v1 ,v2, wt ) \n e2 = Edge(v2 ,v1, wt ) \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\n3@23\r\n4@234\r\n6@2346\r\n5@23465\r\n0@230\r\n1@2301","questionVideo":"https://www.youtube.com/embed/iUtmQ66IC_0?end=743","hints":[],"associated":[{"id":"07e01839-7830-49cf-aec6-03167ce64ded","name":"In which order do we perform Depth First Traversal?","slug":"in-which-order-do-we-perform-depth-first-traversal","type":4},{"id":"0a69e088-2216-4789-adce-7f02ba528374","name":"Which path is followed in Depth First Traversal?","slug":"which-path-is-followed-in-depth-first-traversal","type":4},{"id":"35117a89-8482-45c6-86d7-efac2b1812f8","name":"Time Complexity of DFS is? (V – number of vertices, E – number of edges) (Iterative Depth First Traversal)","slug":"time-complexity-of-dfs-is-v-number-of-vertices-e-number-of-edges-iterative-depth-first-traversal","type":4},{"id":"b6b9e99b-952f-42d8-a93f-5b6c49e09793","name":"How many times a node is visited in Depth First Traversal?","slug":"how-many-times-a-node-is-visited-in-depth-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":"249e36c0-8346-451d-a030-b5c8bf345194","name":"Iterative Depth First Traversal","slug":"iterative-depth-first-traversal","type":1}],"next":{"id":"f3472ecd-a28f-41ef-88f8-cf388d02421a","name":"Iterative Depth First Traversal","type":3,"slug":"iterative-depth-first-traversal"},"prev":{"id":"88cb03ca-e99a-4714-a359-8d65cbb9eb88","name":"Order of Compilation","type":3,"slug":"order-of-compilation"}}}

Iterative Depth First Traversal

1. You are given a graph, and a source vertex. 2. You are required to do a iterative depth first traversal and print which vertex is reached via which path, starting from the source. Note -> For output, check the sample output and question video. Iterative depth first traversal should mimic "Reverse preorder" i.e. nbr with highest value should be visited first and should be printed on the way down in recursion.

{"id":"4c999483-81a5-49d6-beed-c9d005ea87ad","name":"Iterative Depth First Traversal","description":"1. You are given a graph, and a source vertex.\r\n2. You are required to do a iterative depth first traversal and print which vertex is reached via which \r\n path, starting from the source.\r\n\r\nNote -> For output, check the sample output and question video. Iterative depth first traversal \r\n should mimic \"Reverse preorder\" i.e. nbr with highest value should be visited first and \r\n should be printed on the way down in recursion.","inputFormat":"Input has been managed for you","outputFormat":"Check the sample output","constraints":"None","sampleCode":{"cpp":{"code":"#include <iostream>\n\nusing namespace std;\n\nclass Edge\n{ \npublic:\n int src = 0; \n int nbr = 0;\n int wt = 0;\n \n\n Edge(int src, int nbr,int wt)\n {\n this->src = src; \n this->nbr = nbr; \n this->wt = wt; \n\n }\n};\n\n\nint main() { \n \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 \n graph[u].push_back(Edge(u, v, w)); \n graph[v].push_back(Edge(v, u, w)); \n } \n int src;\n cin >> src; \n //write your code here \n \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":"import threading , queue\n\nclass Edge:\n def __init__(self,src,nbr,wt):\n self.src = src\n self.nbr = nbr\n self.wt = wt\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 wt=int(lines[2])\n e1 = Edge(v1 ,v2, wt ) \n e2 = Edge(v2 ,v1, wt ) \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\n3@23\r\n4@234\r\n6@2346\r\n5@23465\r\n0@230\r\n1@2301","questionVideo":"https://www.youtube.com/embed/iUtmQ66IC_0?end=743","hints":[],"associated":[{"id":"07e01839-7830-49cf-aec6-03167ce64ded","name":"In which order do we perform Depth First Traversal?","slug":"in-which-order-do-we-perform-depth-first-traversal","type":4},{"id":"0a69e088-2216-4789-adce-7f02ba528374","name":"Which path is followed in Depth First Traversal?","slug":"which-path-is-followed-in-depth-first-traversal","type":4},{"id":"35117a89-8482-45c6-86d7-efac2b1812f8","name":"Time Complexity of DFS is? (V – number of vertices, E – number of edges) (Iterative Depth First Traversal)","slug":"time-complexity-of-dfs-is-v-number-of-vertices-e-number-of-edges-iterative-depth-first-traversal","type":4},{"id":"b6b9e99b-952f-42d8-a93f-5b6c49e09793","name":"How many times a node is visited in Depth First Traversal?","slug":"how-many-times-a-node-is-visited-in-depth-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":"249e36c0-8346-451d-a030-b5c8bf345194","name":"Iterative Depth First Traversal","slug":"iterative-depth-first-traversal","type":1}],"next":{"id":"f3472ecd-a28f-41ef-88f8-cf388d02421a","name":"Iterative Depth First Traversal","type":3,"slug":"iterative-depth-first-traversal"},"prev":{"id":"88cb03ca-e99a-4714-a359-8d65cbb9eb88","name":"Order of Compilation","type":3,"slug":"order-of-compilation"}}}
plane

Editor

Loading...

Iterative Depth First Traversal

easy

1. You are given a graph, and a source vertex. 2. You are required to do a iterative depth first traversal and print which vertex is reached via which path, starting from the source. Note -> For output, check the sample output and question video. Iterative depth first traversal should mimic "Reverse preorder" i.e. nbr with highest value should be visited first and should be printed on the way down in recursion.

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 3@23 4@234 6@2346 5@23465 0@230 1@2301

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode