UnkleRhaukus
  • UnkleRhaukus
Traversing graphs
Meta-math
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
UnkleRhaukus
  • UnkleRhaukus
1 Attachment
UnkleRhaukus
  • UnkleRhaukus
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?
UnkleRhaukus
  • UnkleRhaukus
... maybe it helps to redraw the graph? |dw:1433579283033:dw|

Looking for something else?

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

More answers

UnkleRhaukus
  • UnkleRhaukus
I can't see how breadth, depth, or level make sense here
rational
  • rational
|dw:1433580732682:dw|
rational
  • rational
dequeue and grab all the adjacent vertices |dw:1433580852616:dw|
rational
  • rational
push all the unseen vertices into Queue : |dw:1433580916917:dw|
rational
  • rational
dequeue and grab all the adjacent vertices |dw:1433580986838:dw|
rational
  • rational
push all the unseen vertices into Queue : |dw:1433581041015:dw|
rational
  • rational
dequeue and grab all the adjacent vertices : |dw:1433581119983:dw|
rational
  • rational
push all the unseen vertices into queue : |dw:1433581254223:dw|
rational
  • rational
dequeue and grab all the adjacent vertices : |dw:1433581272392:dw|
rational
  • rational
push all the unseen vertices into queue : |dw:1433581330168:dw|
rational
  • rational
dequeue and grab all the adjacent vertices : |dw:1433581347294:dw|
rational
  • rational
push all the unseen vertices into queue : |dw:1433581402680:dw|
rational
  • rational
dequeue and grab all the adjacent vertices : the queue is empty, so we're done!
rational
  • rational
|dw:1433581460670:dw|
UnkleRhaukus
  • UnkleRhaukus
adj(D) = {A,C}
rational
  • rational
right! my mistake, but that wont change anything because both A and C are seen already
rational
  • rational
since {E,D,C} are at same level, we will have 3! = 6 different paths using breadth first search
UnkleRhaukus
  • UnkleRhaukus
hmm, ok, should i start by making the adjacent list?
rational
  • rational
you want to implement ?
UnkleRhaukus
  • UnkleRhaukus
or adjacent matrix perhaps?
rational
  • rational
for representing graph is it ?
rational
  • rational
this is a small graph so anything will do i guess
UnkleRhaukus
  • UnkleRhaukus
\[\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
  • UnkleRhaukus
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?
rational
  • rational
for depth first, just replace queue with a stack
UnkleRhaukus
  • UnkleRhaukus
ok thanks !
UnkleRhaukus
  • UnkleRhaukus
i had no idea stack and queues could be used for anything like this, but it kinda makes perfect sense now
UnkleRhaukus
  • UnkleRhaukus
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.
UnkleRhaukus
  • UnkleRhaukus
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)]
UnkleRhaukus
  • UnkleRhaukus
but, i suppose i would have been able to guess from 1.2
rational
  • rational
Nice!
UnkleRhaukus
  • UnkleRhaukus
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!
UnkleRhaukus
  • UnkleRhaukus
1 Attachment
UnkleRhaukus
  • UnkleRhaukus
Now, lets see what happens if add . . . |dw:1433594282292:dw|
UnkleRhaukus
  • UnkleRhaukus
Node  Adjacent Elements A: B B: C, D, E C: A, D D: A, C E: F
UnkleRhaukus
  • UnkleRhaukus
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]
UnkleRhaukus
  • UnkleRhaukus
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.
UnkleRhaukus
  • UnkleRhaukus
breadth first ABCDEF, ABCEDF, ABDECF, ABDCEF, ABEDCF, ABECDF depth first ABCDEF, ABCEFD, ABDEFC, ABDCEF, ABEDCF, ABEFCD is this right?

Looking for something else?

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