You are given an undirected, unweighted graph that may be disconnectedi.e. some
ID: 3772775 • Letter: Y
Question
You are given an undirected, unweighted graph that may be disconnectedi.e. some vertices may not bereachable from other vertices. Every group of mutually reachable vertices forms an island, called a connected component.There is no path between vertices in different connected components. If a graph is notdisconnected, then its vertices are in a single connected component, which is the entire graph itself.
Implement a method using depth-first searchthat will number each vertex with the connected componentthat it belongs to. If there is a single connected component, then all vertices will be numbered 0 (zero). Ifthere are two islands, then vertices in one island will all be numbered 0, and those in the other will all benumbered 1. And so forth.
Write your implementation in thecomponents method in the followingGraphclass. Assume that when this method is called, the adjLists structure is already populated. You can implement helper methods asnecessary.
class Neighbor {
int vnum;Neighbor next;
}
public class Graph { // undirected, unweighted
Neighbor[] adjLists;
...
// returns an array with connected component numbers for all vertices
// i.e. returned[i] is the compnonent number for vertex i
public int[] components() {
/*COMPLETE THIS METHOD*/
Explanation / Answer
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.