Write the programs that performs the given tasks of the graph below using JAVA.
ID: 3833764 • Letter: W
Question
Write the programs that performs the given tasks of the graph below using JAVA. The graph model is an undirected graph of the US towns and roads whose weight
is a distance between two towns, given in the data.
Task: Depth First Search
Starting from Grand Forks, traverse all of the towns by DFS.
1.1) List the towns in the order of traversal.
1.2) Give the total weight of your DFS tree of the traversed towns.
1.3) Give the list of back edges.
Data
u v weight 114 vertices 290 edges Washington, D.C. Norfolk 208 Washington, D.C. Baltimore 39 Washington, D.C. Philadelphia 235 Washington, D.C. Pittsburgh 251 Washington, D.C. Charleston, W.VA 380 Washington, D.C. Charlotte 388 Washington, D.C. Knoxville 512 Washington, D.C. Cincinnati 523 Washington, D.C. Richmond 108 Norfolk Richmond 99 Knoxville Nashville 177 Knoxville Charlotte 231 Knoxville Cincinnati 254 Knoxville Raleigh 362 Knoxville Charleston, SC 403 Charleston, SC Myrtle Beach 98 Charleston, SC Savannah 108 Charleston, SC Charlotte 218 Charleston, W.VA Pittsburgh 221 Charleston, W.VA Louisville 257 Charleston, W.VA Cleveland 260 Charleston, W.VA Charlotte 314 Charleston, W.VA Richmond 331 Orlando Daytona Beach 58 Orlando Tampa 84 Orlando Lake City 160 Orlando Miami 236 Tallahassee Lake City 111 Tallahassee Montgomery 208 Tallahassee Tampa 252 Tallahassee Mobile 253 Tallahassee Atlanta 275 Atlanta Birmingham 149 Atlanta Montgomery 161 Atlanta Knoxville 230 Atlanta Charlotte 249 Atlanta Nashville 252 Atlanta Savannah 256 Atlanta Lake City 292 Atlanta Charleston, SC 329 Atlanta Jacksonville 354 Atlanta Memphis 394 Memphis Little Rock 138 Memphis Nashville 208 Memphis Jackson 212 Memphis Birmingham 241 Memphis Springfield 281 Memphis St. Louis 283 Jacksonville Raleigh 536 Jacksonville Charlotte 399 Jacksonville Tampa 190 Jacksonville Savannah 138 Jacksonville Daytona Beach 99 Jacksonville Lake City 65 Lake City Tampa 169 Miami Tampa 266 Miami Key West 156 Miami Daytona Beach 270 Kansas City Topeka 65 Kansas City Springfield 170 Kansas City Wichita 183 Kansas City Des Moines 197 Wilmington Norfolk 259 Wilmington Richmond 255 Wilmington Myrtle Beach 71 Grand Forks Fargo 76 Grand Forks Minot 210 Grand Forks Duluth 268 Duluth Madison 340 Des Moines Madison 373 Milwaukee Madison 78 Chicago Milwaukee 91 Chicago Madison 152 Chicago Indianapolis 177 Chicago Grand Rapids 190 Chicago St. Louis 302 Chicago Cleveland 345 Chicago Des Moines 362 Chicago Nashville 473 Chicago Kansas City 557 Chicago Detroit 300 Detroit Grand Rapids 157 Detroit Cleveland 173 Detroit Columbus 206 Detroit Cincinnati 260 Detroit Indianapolis 283 Detroit Buffalo, NY 417 Buffalo, NY Cleveland 194 Buffalo, NY Binghamton 220 Buffalo, NY Albany 289 Binghamton Albany 137 Cincinnati Louisville 102 Cincinnati Indianapolis 108 Cincinnati Columbus 109 Cincinnati Columbus 202 Cincinnati St. Louis 353 Montgomery Birmingham 92 Montgomery Mobile 171 Montgomery Jackson 251 New York City Hartford 118 New York City Albany 160 New York City Harrisburg 174 New York City Binghamton 199 New York City Cleveland 481 New York City Philadelphia 99 Harrisburg Philadelphia 105 Baltimore Philadelphia 98 Boston Hartford 101 Boston Portland, ME 103 Boston Albany 177 Denver Cheyenne 102 Denver Lamar 206 Denver Oakley 247 Denver North Platte 290 Denver Cortez 411 Denver Albuquerque 457 Denver Salt Lake City 529 Denver St. George 648 Portland, ME Bangor 132 Portland, OR Eugene 115 Portland, OR Seattle 180 Portland, OR Riley 268 Portland, OR Crescent City 346 Portland, OR Spokane 400 Portland, OR Boise 439 Reno Winnemucca 164 Reno Yosemite Village 213 Reno Ely 331 Reno Riley 342 Boise Riley 210 Boise Twin Falls 123 Boise Winnemucca 257 Boise Spokane 379 Boise Seattle 499 Spokane Seattle 276 Bismarck Minot 106 Bismarck Fargo 194 Bismarck Pierre 209 Bismarck Rapid City 358 Bismarck Billings 418 Bismarck Malta 430 Rapid City Pierre 174 Rapid City Buffalo, WY 216 Rapid City Cheyenne 290 Rapid City Sioux Falls 350 Phoenix Tucson 112 Phoenix Flagstaff 141 Phoenix Springerville 236 Phoenix San Diego 368 Phoenix El Paso 404 Los Angeles Phoenix 393 Los Angeles San Diego 118 Los Angeles Barstow 138 Los Angeles Yosemite Village 313 Los Angeles Reno 522 San Francisco Los Angeles 384 San Francisco Reno 228 San Francisco Barstow 442 San Francisco Yosemite Village 193 San Francisco Crescent City 371 San Francisco Eugene 540 Riley Eugene 230 Las Vegas St. George 122 Las Vegas Barstow 155 Las Vegas Ely 282 Las Vegas Phoenix 288 Las Vegas Reno 442 Las Vegas Salt Lake City 423 Salt Lake City Twin Falls 222 Salt Lake City Rawlins 294 Salt Lake City Ely 294 Salt Lake City St. George 305 Salt Lake City Cortez 348 Salt Lake City Winnemucca 362 Salt Lake City Helena 482 Salt Lake City Old Faithful 482 Raleigh Wilmington 127 Raleigh Richmond 156 Raleigh Norfolk 170 Cleveland Pittsburgh 141 Cleveland Columbus 146 Cleveland Des Moines 677 San Antonio Eagle Pass 142 San Antonio Laredo 154 San Antonio Houston 201 San Antonio Brownsville 281 San Antonio Big Spring 298 San Antonio El Paso 552 San Antonio Dallas 273 Dallas Oklahoma City 208 Dallas Houston 237 Dallas Big Spring 266 Dallas Springfield 282 Dallas Little Rock 315 Dallas Amarillo 367 Dallas Jackson 417 Dallas New Orleans 509 Omaha Des Moines 143 Omaha Topeka 163 Omaha Sioux Falls 175 Omaha Kansas City 194 Omaha North Platte 298 Omaha Liberal 489 Omaha Rapid City 539 Minneapolis Duluth 152 Minneapolis Fargo 242 Minneapolis Sioux Falls 247 Minneapolis Madison 260 Minneapolis Des Moines 286 Minneapolis Pierre 399 Minneapolis Omaha 409 Minneapolis St. Louis 540 New Orleans Mobile 153 New Orleans Jackson 183 New Orleans Birmingham 354 New Orleans Houston 363 Buffalo, WY Old Faithful 296 Buffalo, WY Billings 168 Buffalo, WY Rawlins 236 Old Faithful Rawlins 320 Rawlins Cheyenne 146 North Platte Cheyenne 215 North Platte Oakley 158 North Platte Pierre 264 Charlotte Raleigh 175 Charlotte Myrtle Beach 180 Charlotte Wilmington 188 Nashville Louisville 180 Nashville St. Louis 312 Nashville Birmingham 192 Jackson Birmingham 234 Pittsburgh Harrisburg 218 Pittsburgh Columbus 184 Indianapolis St. Louis 244 Indianapolis Columbus 179 Indianapolis Louisville 124 Brownsville Houston 365 Brownsville Laredo 204 Eagle Pass Laredo 124 Billings Malta 206 Billings Helena 243 Helena Old Faithful 216 Helena Malta 293 Helena Missoula 116 Spokane Missoula 198 Twin Falls Missoula 401 Twin Falls Ely 255 Little Rock Springfield 219 Little Rock Jackson 267 Little Rock Houston 315 Little Rock Oklahoma City 336 Little Rock St. Louis 350 St. Louis Des Moines 387 St. Louis Louisville 259 St. Louis Kansas City 250 St. Louis Springfield 224 Malta Minot 457 Fargo Minot 268 Fargo Duluth 259 Fargo Sioux Falls 253 Flagstaff St. George 286 Flagstaff Cortez 263 Flagstaff Barstow 348 San Diego Barstow 181 El Paso Big Spring 344 El Paso Amarillo 412 El Paso Eagle Pass 484 El Paso Houston 746 El Paso Tucson 324 El Paso Albuquerque 270 Albuquerque Lamar 393 Albuquerque Flagstaff 325 Albuquerque Amarillo 296 Albuquerque Cortez 273 Albuquerque Springerville 233 Albuquerque Big Spring 418 Albuquerque Liberal 421 Amarillo Liberal 164 Amarillo Oklahoma City 259 Amarillo Big Spring 224 Amarillo Lamar 228 Liberal Lamar 168 Liberal Oakley 143 Liberal Wichita 209 Topeka Wichita 138 Topeka Oakley 289 Topeka Liberal 361 Oklahoma City Wichita 156 Oklahoma City Liberal 256 Oklahoma City Springfield 283Explanation / Answer
Executable Code:-
package chegg1;
import java.util.Arrays;
import java.util.Scanner;
public class Graph {
class Edge implements Comparable<Edge> {
int src, dest, weight;
public int compareTo(Edge compareEdge) {
return this.weight - compareEdge.weight;
}
};
class subset {
int parent, rank;
};
int V, E;
Edge edge[];
Graph(int v, int e) {
V = v;
E = e;
edge = new Edge[E];
for (int i = 0; i < e; ++i)
edge[i] = new Edge();
}
int find(subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void Union(subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
void KruskalMST() {
Edge result[] = new Edge[V];
int e = 0;
int i = 0;
for (i = 0; i < V; ++i)
result[i] = new Edge();
Arrays.sort(edge);
subset subsets[] = new subset[V];
for (i = 0; i < V; ++i)
subsets[i] = new subset();
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0;
while (e < V - 1) {
Edge next_edge = new Edge();
next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
Union(subsets, x, y);
}
}
int net_weight = 0;
int net_edges = e;
System.out.println("Following are the edges in the constructed MST:");
for (i = 0; i < e; ++i) {
System.out.println("result[i].src+" - "+result[i].dest+:");
net_weight = net_weight + result[i].weight;
}
System.out.println("Total number of edges in the MST are: " + net_edges);
System.out.println("Total weight of the MST is : " + net_weight);
}
public static void main(String[] args) {
int V = 114;
int E = 290;
Graph graph = new Graph(V, E);
int src, dest, weight;
Scanner sc = new Scanner(System.in);
System.out.println(
"Enter the data as Source vertex number 'u', Destination vertex number 'v' and weight 'w' for all 290 edges:");
for (int i = 0; i < 290; i++) {
graph.edge[i].src = sc.nextInt();
graph.edge[i].dest = sc.nextInt();
graph.edge[i].weight = sc.nextInt();
}
graph.KruskalMST();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.