A community for students.
Here's the question you clicked on:
 0 viewing
UnkleRhaukus
 one year ago
Traversing graphs
UnkleRhaukus
 one year ago
Traversing graphs

This Question is Closed

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1I 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?

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1... maybe it helps to redraw the graph? dw:1433579283033:dw

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1I can't see how breadth, depth, or level make sense here

rational
 one year ago
Best ResponseYou've already chosen the best response.3dw:1433580732682:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3dequeue and grab all the adjacent vertices dw:1433580852616:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3push all the unseen vertices into Queue : dw:1433580916917:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3dequeue and grab all the adjacent vertices dw:1433580986838:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3push all the unseen vertices into Queue : dw:1433581041015:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3dequeue and grab all the adjacent vertices : dw:1433581119983:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3push all the unseen vertices into queue : dw:1433581254223:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3dequeue and grab all the adjacent vertices : dw:1433581272392:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3push all the unseen vertices into queue : dw:1433581330168:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3dequeue and grab all the adjacent vertices : dw:1433581347294:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3push all the unseen vertices into queue : dw:1433581402680:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3dequeue and grab all the adjacent vertices : the queue is empty, so we're done!

rational
 one year ago
Best ResponseYou've already chosen the best response.3dw:1433581460670:dw

rational
 one year ago
Best ResponseYou've already chosen the best response.3right! my mistake, but that wont change anything because both A and C are seen already

rational
 one year ago
Best ResponseYou've already chosen the best response.3since {E,D,C} are at same level, we will have 3! = 6 different paths using breadth first search

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1hmm, ok, should i start by making the adjacent list?

rational
 one year ago
Best ResponseYou've already chosen the best response.3you want to implement ?

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1or adjacent matrix perhaps?

rational
 one year ago
Best ResponseYou've already chosen the best response.3for representing graph is it ?

rational
 one year ago
Best ResponseYou've already chosen the best response.3this is a small graph so anything will do i guess

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.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}\]

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1hmm 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?

rational
 one year ago
Best ResponseYou've already chosen the best response.3for depth first, just replace queue with a stack

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1i had no idea stack and queues could be used for anything like this, but it kinda makes perfect sense now

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.110. 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.

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1so 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)]

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1but, i suppose i would have been able to guess from 1.2

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1i 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!

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1Now, lets see what happens if add . . . dw:1433594282292:dw

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1Node ￼ Adjacent Elements A: B B: C, D, E C: A, D D: A, C E: F

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1Is 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]

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1Is 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.

UnkleRhaukus
 one year ago
Best ResponseYou've already chosen the best response.1breadth first ABCDEF, ABCEDF, ABDECF, ABDCEF, ABEDCF, ABECDF depth first ABCDEF, ABCEFD, ABDEFC, ABDCEF, ABEDCF, ABEFCD is this right?
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.