Student No : 101030382 Can i get help with this discrete structure questions ple
ID: 3844026 • Letter: S
Question
Student No : 101030382
Can i get help with this discrete structure questions please?
Questions 8-9 all refer to the undirected graph specified below: 8. Given the graph G (V, E) in the figure above, compute the breadth-first search tree starting from the vertex that is labelled with the third-to-last digit in your student number. To clarify, if your student number is 100123456, start your breadth-first search tree from vertex 4. You must provide your search tree as an adjacency list; do not "draw" your search trees. Whenever you have a "choice" of which adjacent vertex to consider, you must consider them in numerical order from least to greatest.Explanation / Answer
Student No : 101030382
So start with 3(third to last digit)
Adjacency list
0 - 4- 6- 9
1-0 - 2-4
2 - 1 - 3- 4- 5
3 - 2 - 5 -8
4 - 0- 1 - 2 - 7
5 - 2 - 3 - 6 - 8
6 - 0 - 5 - 7
7 - 4 - 5 - 6 - 8
8 - 3 - 5 - 7 -9
9 - 0 - 8
8. Depth-first Search
DFS: 3 Stack: 3<-
DFS: 3 2 Stack: 3 2<-
DFS: 3 2 1 Stack: 3 2 1<-
DFS: 3 2 1 0 Stack: 3 2 1 0<-
DFS: 3 2 1 0 4 Stack: 3 2 1 0 4<-
DFS: 3 2 1 0 4 7 Stack: 3 2 1 0 4 7<-
DFS: 3 2 1 0 4 7 5 Stack: 3 2 1 0 4 7 5<-
DFS: 3 2 1 0 4 7 5 6 Stack: 3 2 1 0 4 7 5 6<-
DFS: 3 2 1 0 4 7 5 6 8 Stack: 3 2 1 0 4 7 5 6 8<-
DFS: 3 2 1 0 4 7 5 6 8 9 Stack: 3 2 1 0 4 7 5 6 8 9<-
DFS: 3 2 1 0 4 7 5 6 8 9
9.
Breadth First Search
BFS: 3 Queue: 2 5 8
BFS: 3 2 Queue: 5 8 1 4
BFS: 3 2 5 Queue: 8 1 4 6
BFS: 3 2 5 8 Queue: 1 4 6 7 9
BFS: 3 2 5 8 1 Queue: 4 6 7 9
BFS: 3 2 5 8 1 4 Queue: 6 7 9 0
BFS: 3 2 5 8 1 4 6 Queue: 7 9 0
BFS: 3 2 5 8 1 4 6 7 Queue: 9 0
BFS: 3 2 5 8 1 4 6 7 9 Queue: 0
BFS: 3 2 5 8 1 4 6 7 9 0 Queue: empty
BFS: 3 2 5 8 1 4 6 7 9 0