In: Computer Science
Graph theory unit.
1. List important computing algorithms in Computer Networking based
on application of graph theory.
2. Explain following using an example. a. graph, edges and vertices of the graph, directed graph, in-degree and outdegree of vertex, incident, a path, a distance
3. What is the worst – case memory usage of DFS?
4. Does DFS find the shortest path from start node to some node w ?
answer 1
some important computing algorithms in networking based on graph theory
Answer 2 3 4 given below
i have given calling seq of dfs for a vertex so that you can trace dfs tree execution in question 4
Path from a to c is 4 in graph but in resultant dfs tree path from a to c is 5
Clearly path in dfs tree is not shortest path
If you are having any doubts please ask i will answer asap