GRAPHS: SEARCH

GRAPHS: SEARCH
Slide Note
Embed
Share

Delve into the world of graphs, trees, and their applications in computer science. Explore concepts such as tree traversal, graph search algorithms, and more. Discover how to print vertices in a tree and the various traversal methods used. Gain insights into stack and queue operations, tree BFS, and practical implementations. Dive deep into the foundational knowledge of these essential data structures.

  • Graphs
  • Trees
  • Data Structures
  • Algorithms
  • Computer Science
aisa
aisa Follow

Uploaded on Feb 17, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. GRAPHS: SEARCH David Kauchak CS 62 Spring 2021

  2. Admin Assignment 9: Text Generation

  3. Graphs A graph is a set of vertices V and a set of edges (u,v) E where u,v V A B F D E C G

  4. Searching a tree A B E D C F G How can we print out all of the vertices in a tree?

  5. Searching a tree A B E D C F G We could do any of the traversals we saw before: pre-order, in-order, post-order

  6. A flash from the past Stack: - LIFO - Add to the back - Remove from the back Queue: - FIFO - Add to the back - Remove from the front

  7. Searching a tree treeBFS( start ) q = new Queue() q.add(start) treeSearch(q) treeDFS( start ) s = new Stack() s.add(start) treeSearch(s) treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c)

  8. Tree BFS A treeBFS( start ) q = new Queue() q.add(start) treeSearch(q) B E D C F G q: Visited:

  9. Tree BFS A treeBFS( start ) q = new Queue() q.add(start) treeSearch(q) B E D C F G q: A Visited:

  10. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: A printed: What order will the nodes get printed out? Assume children are traversed left to right.

  11. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: A printed:

  12. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: printed: A

  13. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: printed: A

  14. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: B D E printed: A

  15. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: B D E printed: A

  16. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: D E printed: A B

  17. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: D E printed: A B

  18. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: D E C F printed: A B

  19. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: D E C F printed: A B

  20. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: E C F printed: A B D

  21. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: E C F printed: A B D

  22. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: E C F printed: A B D

  23. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: E C F printed: A B D

  24. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: C F printed: A B D E

  25. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: C F printed: A B D E

  26. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: C F G printed: A B D E

  27. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: C F G printed: A B D E How are we exploring the vertices?

  28. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G Frontier: all vertices a given number of edges from the start/root toVisit-queue: C F G printed: A B D E

  29. Tree BFS = Tree breadth first search A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G Frontier: all vertices a given number of edges from the start/root toVisit-queue: C F G printed: A B D E

  30. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: C F G printed: A B D E

  31. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: F G printed: A B D E C

  32. Tree BFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-queue: printed: A B D E C F G

  33. Tree DFS treeDFS( start ) s = new Stack() s.add(start) treeSearch(s) A B E D C F G s: printed:

  34. Tree DFS treeDFS( start ) s = new Stack() s.add(start) treeSearch(s) A B E D C F G s: A printed:

  35. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: A printed: What order will the nodes get printed out? Assume children are traversed left to right.

  36. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: A printed:

  37. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: printed: A

  38. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: printed: A

  39. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: B D E printed: A

  40. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: B D E printed: A

  41. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: B D printed: A E

  42. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: B D printed: A E

  43. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: B D G printed: A E

  44. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: B D G printed: A E

  45. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: B D printed: A E G

  46. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: B D printed: A E G

  47. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: B D printed: A E G

  48. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: B printed: A E G D

  49. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G toVisit-stack: B printed: A E G D How are we exploring the vertices?

  50. Tree DFS A treeSearch( toVisit ) while !toVisit.empty() v = toVisit.remove() // visit v, e.g., print it out for c in v.getChildren() toVisit.add(c) B E D C F G Frontier: go as far down one branch as possible, working right to left toVisit-stack: B printed: A E G D

Related


Product and Knowledge Graphs for Enhanced Information Retrieval

Product and Knowledge Graphs for Enhanced Information Retrieval

roza
Exploring Various Types of Graphs in Statistics Education

Exploring Various Types of Graphs in Statistics Education

aisling
Graphs: An Introduction to Data Visualization

Graphs: An Introduction to Data Visualization

julissa
Bar Graphs, Double Bar Graphs, and Histograms

Bar Graphs, Double Bar Graphs, and Histograms

michal
Primal-Dual Algorithms for Node-Weighted Network Design in Planar Graphs

Primal-Dual Algorithms for Node-Weighted Network Design in Planar Graphs

acacius
Representation of Abstract Groups through Graphs

Representation of Abstract Groups through Graphs

alge672
Informed and Uninformed Search Algorithms in Artificial Intelligence

Informed and Uninformed Search Algorithms in Artificial Intelligence

aub_l
Low Threshold Rank Graphs and Their Structural Properties

Low Threshold Rank Graphs and Their Structural Properties

mcqueary_j
k-Ary Search on Modern Processors

k-Ary Search on Modern Processors

ertl_j
Solving Problems by Searching in Artificial Intelligence: Uninformed Search Strategies

Solving Problems by Searching in Artificial Intelligence: Uninformed Search Strategies

pdha
Exploring Types of Graphs for Data Representation

Exploring Types of Graphs for Data Representation

jayd_813
Relationships Through Graphs

Relationships Through Graphs

everardob
Search Patterns for Music Materials in Libraries

Search Patterns for Music Materials in Libraries

mary_908
Correlation in Scatter Graphs

Correlation in Scatter Graphs

auch_r
Symmetric Chromatic Function for Voltage Graphs

Symmetric Chromatic Function for Voltage Graphs

beas805
Uniquely Bipancyclic Graphs by Zach Walsh

Uniquely Bipancyclic Graphs by Zach Walsh

chr_br
Graphs for Mathematical Interpretation

Graphs for Mathematical Interpretation

jala_482
Adjacency Labeling Schemes and Induced-Universal Graphs

Adjacency Labeling Schemes and Induced-Universal Graphs

juliash
Graphs and Their Models

Graphs and Their Models

itan232
Introduction to Graph Theory: Exploring Graphs and Their Properties

Introduction to Graph Theory: Exploring Graphs and Their Properties

ken_duf
Overview of Informed Search Methods in Computer Science

Overview of Informed Search Methods in Computer Science

satt378
Techniques in Beyond Classical Search and Local Search Algorithms

Techniques in Beyond Classical Search and Local Search Algorithms

myk_cha

More Related Content