USA: +1 725-224-8795 
Sign in
2.Show the order in which the vertices in graph G are visited using the DFS algorithm and the BFS algorithm. G = (V,E) where V = {a, b, c, d, e, f, g} and E = {(a,b), (a,c), (b,d), (c,e), (d,f), (e,f), (e,g)}. Start at vertex a and check edges in alphabetical order.
3.Give a topological sort for the following relations: (a<b, a <c, d<b, e<c, a<e, a<d).
4.Using any resources known to you, investigate and report on two of the following algorithms: 1) Dijkstra’s, 2) Bellman-Ford’s, 3) Floyd-Warshall’s. In each report, give a description in your own words of i) the purpose of the algorithm, ii) the problem solving technique used, and iii) the reported complexity and efficiency of the algorithm. Be sure to cite all sources used including web pages. For each of your chosen algorithms, attach a copy of the best (in your opinion) web site that you found most helpful and understandable in describing the algorithm.
Expert Answer
Solution:
Note: Multiple questions asked, please post the questions separately
2.
DFS:
- DFS use a stack to hold and process the vertices of the graph.
- It is given that “a” should be the start vertex.
- So stack will be initialized with “a”.
- STACK: a and visited= a
- Now visit “b”, stack becomes: a, b and visited also a, b
- Now pop top of the stack, that is “b” and push adjacent of “b” to the stack and mark them as visited.
- Stack becomes: a, b, d and visited nodes are also a, b, d.
- Now visit adjacent of “d”, which is “f”. Now the visited vertices are a, b, d, f.
- Now from “f”, “e” is there in adjacent to “f”.
- The visited list now becomes a, b, d, f, e.
- Now adjacent of “e”, which is “c” and “g” take lower that is “c”, now the visited list is a, b, d, f, e, c.
- Now no unvisited vertex is there in adjacent to last visited vertex “c”, so take the second last “e”, which has “g” as unvisited, mark it as visited.
- Now the visited sequence is a, b, d, f, e, c, g.
- All the vertices are visited, stop here.
BFS:
- Here Queue is used for aid to visit the vertices.
- First vertex is “a”.
- Visit all the vertices adjacent to “a”.
- Here “b” and “c” are adjacent to “a” so visit them first.
- The visited sequence now becomes: a, b, c
- Now as queue process take “b” and visit all its adjacent vertices.
- Since edge (b, d ) is there add “d” to the visited list.
- Now the visited list is a, b, c, d
- Now take “c” and visit its adjacent vertices.
- Edge(c, e) is there so add “e” to the visited list.
- Now the visited list is a, b, c, d, e
- Now take “d” and visit its adjacent vertices.
- “f” is adjacent to “d” thus add “f”.
- Now the visited list is a, b, c, d, e, f.
- Now take “e”, “g” is adjacent to “e” add “g” to the visited list.
- Now all the vertices are visited so finish here.
- The visited sequence can be a, b, c, d, e, f, g.
