Summary
Full Transcript
Graph Traversal - Graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. BFS - In this traversal algorithm one node is selected and then all of the adjacent nodes are visited one by one. After completing all of the adjacent vertices, it moves further to check another vertices and checks its adjacent vertices again. Steps - 1. Define a Queue 2. Set current vertex V 3. Add current vertex V to queue 4. Print current vertex V 5. Add all neighbors(unvisited i.e. previously not in queue) of V to queue(in any order) 6. Repeat from step 4 till queue empty DFS - In this algorithm one starting vertex is given, and when an adjacent vertex is found, it moves to that adjacent vertex first and try to traverse in the same manner. Steps - 1. Define a Stack 2. Set current vertex V 3. Add current vertex V to stack 4. Print current vertex V 5. Add any 1 neighbor(unvisited i.e. not in stack previously) of V to stack 6. If current vertex has all its neighbors already visited, pop it from stack & backtrack 7. Check remaining vertices in the stack for any unvisited vertices. 8. Repeat till stack empty --------------------------------------------------------------------------------------------- Graph Theory - https://simplesnippets.tech/what-is-a-graph-data-structure-important-graph-terms-properties/ Graph Full C++ Code Implementation - https://simplesnippets.tech/graph-implementation-adjacency-matrix-vs-adjacency-list-full-c-program-code/ Full DSA playlist - https://www.youtube.com/watch?v=XCyuHSJS7XE&list=PLIY8eNdw5tW_zX3OCzX7NJ8bL1p6pWfgG Full C++ Programming for Beginners Course - https://www.youtube.com/watch?v=AKNGgAXTark&list=PLIY8eNdw5tW_o8gsLqNBu8gmScCAqKm2Q --------------------------------------------------------------------------------------------- Support Simple Snippets by Donations - Google Pay UPI ID - tanmaysakpal11@okicici PayPal - paypal.me/tanmaysakpal11 --------------------------------------------------------------------------------------------- Timecodes - 00:00 What is graph traversal? 02:20 BFS and DFS 05:13 BFS traversal working 12:50 DFS traversal working 21:59 Conclusion --------------------------------------------------------------------------------------------- Simple Snippets Official Website - http://simplesnippets.tech/ Simple Snippets on Facebook - https://www.facebook.com/simplesnippets/ Simple Snippets on Instagram - https://www.instagram.com/simplesnippets/ Simple Snippets on Twitter - https://twitter.com/simplesnippet Simple Snippets Google Plus Page - https://plus.google.com/+SimpleSnippets Simple Snippets email ID - [email protected] For More Technology News, Latest Updates and Blog articles visit our Official Website - http://simplesnippets.tech/ #graph #graphtraversal #graphdatastructure #bfs #dfs
Continue this lesson in the app
Install CourseHive on Android or iOS to keep learning while you move.
