Traversing graphs

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.

Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions.

A community for students.

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
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.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions

1 Attachment
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?
... maybe it helps to redraw the graph? |dw:1433579283033:dw|

Not the answer you are looking for?

Search for more explanations.

Ask your own question

Other answers:

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

Not the answer you are looking for?

Search for more explanations.

Ask your own question