UnkleRhaukus one year ago Traversing graphs

1. UnkleRhaukus

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

3. UnkleRhaukus

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

4. UnkleRhaukus

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

5. rational

|dw:1433580732682:dw|

6. rational

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

7. rational

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

8. rational

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

9. rational

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

10. rational

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

11. rational

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

12. rational

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

13. rational

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

14. rational

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

15. rational

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

16. rational

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

17. rational

|dw:1433581460670:dw|

18. UnkleRhaukus

19. rational

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

20. rational

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

21. UnkleRhaukus

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

22. rational

you want to implement ?

23. UnkleRhaukus

24. rational

for representing graph is it ?

25. rational

this is a small graph so anything will do i guess

26. 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}$

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

28. rational

for depth first, just replace queue with a stack

29. UnkleRhaukus

ok thanks !

30. UnkleRhaukus

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

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

32. 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)]

33. UnkleRhaukus

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

34. rational

Nice!

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

36. UnkleRhaukus

37. UnkleRhaukus

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

38. UnkleRhaukus

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

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

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

41. UnkleRhaukus

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