Traversing graphs

- UnkleRhaukus

Traversing graphs

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- chestercat

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- UnkleRhaukus

##### 1 Attachment

- 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

... 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

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

- rational

|dw:1433580732682:dw|

- rational

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

- rational

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

- rational

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

- rational

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

- rational

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

- rational

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

- rational

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

- rational

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

- rational

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

- rational

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

- rational

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

- rational

|dw:1433581460670:dw|

- UnkleRhaukus

adj(D) = {A,C}

- rational

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

- rational

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

- UnkleRhaukus

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

- rational

you want to implement ?

- UnkleRhaukus

or adjacent matrix perhaps?

- rational

for representing graph is it ?

- rational

this is a small graph so anything will do i guess

- 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

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

for depth first, just replace queue with a stack

- UnkleRhaukus

ok thanks !

- UnkleRhaukus

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

- 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

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

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

- rational

Nice!

- 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

##### 1 Attachment

- UnkleRhaukus

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

- UnkleRhaukus

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

- 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

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

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.