1. Class WeightedGraph in this chapter is to be extended to include a removeVert

Question

1. Class WeightedGraph in this chapter is to be extended to include a removeVertex operation, which removes a vertex from the graph. Deleting a vertex is more complicated than deleting an edge from the graph. Discuss the reasons for this operations's greater complexity.

2.Our shortestPaths method is concerned with the minimum distance between two vertices of a graph. Create a minEdges method that returns the minimum number of edges that exist on a path between two given vertices. You can put your new method in our useGraph class in the textbook and use it to test your code

Explanation / Answer

1. Deleting a vertex is more complicated than deleting an edge from the graph. This is because for deleting an edge between vertex i and vertex j, we just need to remove it from the
   1. entry from the adjacency list if graph is stored in adjacency list form
   2. If graph is stored in matrix, then we need to update cell (i, j) and (j, i)
but for deleting the vertex, we need to remove all the edges connected to that cell. so this is more complicated then deleting one edge.

Edit:
Ans 2 You already have shortestPath method. we can resue it to compute minEdges method, Assign weight of all edges as 1. i.e. weight of all edges is same. So, shortest path between two vertices is same as minimum edges between them on a path.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.