A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

UnkleRhaukus

  • one year ago

Traversing graphs

  • This Question is Closed
  1. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    1 Attachment
  2. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I know how to traverse: a tree (an undirected, acyclic graph, with one root), but how i am supposed to traverse: a cyclic graph with no root?

  3. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    ... maybe it helps to redraw the graph? |dw:1433579283033:dw|

  4. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I can't see how breadth, depth, or level make sense here

  5. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    |dw:1433580732682:dw|

  6. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    dequeue and grab all the adjacent vertices |dw:1433580852616:dw|

  7. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    push all the unseen vertices into Queue : |dw:1433580916917:dw|

  8. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    dequeue and grab all the adjacent vertices |dw:1433580986838:dw|

  9. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    push all the unseen vertices into Queue : |dw:1433581041015:dw|

  10. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    dequeue and grab all the adjacent vertices : |dw:1433581119983:dw|

  11. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    push all the unseen vertices into queue : |dw:1433581254223:dw|

  12. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    dequeue and grab all the adjacent vertices : |dw:1433581272392:dw|

  13. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    push all the unseen vertices into queue : |dw:1433581330168:dw|

  14. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    dequeue and grab all the adjacent vertices : |dw:1433581347294:dw|

  15. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    push all the unseen vertices into queue : |dw:1433581402680:dw|

  16. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    dequeue and grab all the adjacent vertices : the queue is empty, so we're done!

  17. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    |dw:1433581460670:dw|

  18. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    adj(D) = {A,C}

  19. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    right! my mistake, but that wont change anything because both A and C are seen already

  20. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    since {E,D,C} are at same level, we will have 3! = 6 different paths using breadth first search

  21. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    hmm, ok, should i start by making the adjacent list?

  22. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    you want to implement ?

  23. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    or adjacent matrix perhaps?

  24. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    for representing graph is it ?

  25. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    this is a small graph so anything will do i guess

  26. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    \[\begin{array}{cccccc}&A&B&C&D&E\\ A&\infty&1&\infty&\infty&\infty\\B&\infty&\infty&1&1&1\\C&1&\infty&\infty& 1&\infty\\D&1&\infty&1&\infty&\infty\\E&\infty&\infty&\infty&\infty&\infty \end{array}\]

  27. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    hmm ok, i haven't yet been through the detail but that method seems like it works for breadth first traversal. what is the method for depth first traversal?

  28. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    for depth first, just replace queue with a stack

  29. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    ok thanks !

  30. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i had no idea stack and queues could be used for anything like this, but it kinda makes perfect sense now

  31. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    10. The Adjacency List A: {B} B: {C, D, E} C: {A, D} D: {A, C} E: {} Operation Queue Output __________________________________ enqueue(A) |A| dequeue | | A enqueue( adj(A) ) |B| A dequeue | | AB enqueue( adj(B) ) |E,D,C| AB dequeue 1 |E,D| ABC dequeue 1.1 |E| ABCD | | ABCDE. dequeue 1.2 |D| ABCE | | ABCED. dequeue 2 |C,E| ABD dequeue 2.1 |C| ABDE dequeue | | ABDEC. dequeue 2.2 |E| ABDC dequeue | | ABDCE. dequeue 3 |C,D| ABE dequeue 3.1 |C| ABED dequeue | | ABEDC. dequeue 3.2 |D| ABEC dequeue | | ABECD.

  32. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    so the six possible breadth first traversals are: ABCDE (a) ABCED (b) ABDCE ABDEC (c) ABEDC ABECD so the answer to 10. is (d) all of the above [(a,b,c)]

  33. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    but, i suppose i would have been able to guess from 1.2

  34. rational
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 3

    Nice!

  35. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i got these questions from a past paper of a subject i've almost completed [just final exam to go], seems like the course has changed quite a bit since 2012, ive learnt about graphs, digraphs, adjacency lists/matrices, trees, traversals, stacks, queues, etc. Now i can put all the ideas together!

  36. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    1 Attachment
  37. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Now, lets see what happens if add . . . |dw:1433594282292:dw|

  38. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Node  Adjacent Elements A: B B: C, D, E C: A, D D: A, C E: F

  39. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Is this right for breadth first? Operation Queue Output __________________________________ enqueue(A) |A| dequeue | | A enqueue( adj(A) ) |B| A dequeue | | AB enqueue( adj(B) ) |E,D,C| AB dequeue |E,D| ABC [1] dequeue |E| ABCD dequeue | | ABCDE enqueue( adj(E) ) |F| ABCDE dequeue | | ABCDEF. [other traversals are valid]

  40. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Is this right for breadth first? Operation Queue Output __________________________________ enqueue(A) |A| dequeue | | A enqueue( adj(A) ) |B| A dequeue | | AB enqueue( adj(B) ) |E,D,C| AB [1 of 6] dequeue |E,D| ABC dequeue |E| ABCD dequeue | | ABCDE enqueue( adj(E) ) |F| ABCDE dequeue | | ABCDEF.

  41. UnkleRhaukus
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    breadth first ABCDEF, ABCEDF, ABDECF, ABDCEF, ABEDCF, ABECDF depth first ABCDEF, ABCEFD, ABDEFC, ABDCEF, ABEDCF, ABEFCD is this right?

  42. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.