(Java Programing Help) For this problem assume a graph consists of five nodes, A

Question

(Java Programing Help) For this problem assume a graph consists of five nodes, A, B, C, D and E, with two edges, one connecting A and B and the other one connecting B and C. A graph is connected if there is a path from every vertex to every other vertex, and a graph that is not connected consists of a set of connected components. For a connected graph, a traversal starting from one vertex will cover all vertices thus a connected graph will contain one connected componet. For a graph with two connected components, the traversal starts from node, then visits all nodes that are connected to the start node and then restarts from one of the unvisited nodes so all nodes get visited. In the mentioned graph it contains three connected components with 3, 1, and 1 nodes. Thus I need help implementing a function in java for computing the number of connected components and their sizes. Based on walk() in the second pastebin file which traverses the graph using depth-first-search and breadth-first-search create a walk2() function which computes the number of components and their sizes as explained above. Lastly create a main function to test walk2() using the example graph mentioned above. Therefore the expected output would be:

Graph interface: http://pastebin.com/cqQT5AUJ

Graph implementation: http://pastebin.com/1AcB0m3d

Explanation / Answer

import java.io.*;

import java.util.*;

import java.util.LinkedList;

void printSCCs()

    {

        Stack stack = new Stack();

boolean visited[] = new boolean[V];

        for(int i = 0; i < V; i++)

            visited[i] = false;

for (int i = 0; i < V; i++)

            if (visited[i] == false)

                fillOrder(i, visited, stack);

Graph gr = getTranspose();

for (int i = 0; i < V; i++)

            visited[i] = false;

while (stack.empty() == false)

        {

  int v = (int)stack.pop();

if (visited[v] == false)

            {

                gr.DFSUtil(v, visited);

                System.out.println();

            }

        }

    }

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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