Counting components in a graph
I must write a program that counts the number of components in a undirected graph. The program takes input in from System.in in the form of an adjacency matrix such as this
0 1 0 0
1 0 0 1
0 0 0 0
0 1 0 0
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
Each single line integer represents a new (n by n) graph with an order of what ever the number is. Each line after represents a node and all the nodes it has an edge to. The 0 at the bottom represents the end of the input. From the above adjacency matrix you would get 2 graphs that looked like so
So the first graph should have 2 components and the second should have 1 component.
/ \ /
I'm not sure how to write the code for this. We've been given a Graph ADT which can be found here http://www.cs.auckland.ac.nz/compsci...es/graphs2008/ so most algorithms and data structures we would need to use are there, I'm just unsure how one would go about getting each element. I've been stuck on this for a number of days now so any help would be appreciated.
Re: Counting components in a graph
So, first off, what do you have? Show us. Secondly, you understand what an adjacency matrix is and how it works right? Reading each row of the matrix gives you the list of it's connections. The dimensions of the matrix give you the bounds of the elements inside. So, since the bounds are known, using a for loop would make sense. Since a matrix is a 2 dimensional array, a nested for loop makes sense. Inside your loop structure, you can examine the the elements. This tells you two things. If a given element exists, and what it connects to (in an undirected graph). So, as you find elements and connections, you can create them in your Graph data structure.