Results 1 to 2 of 2
Thread: Counting components in a graph
 10132012, 03:12 PM #1Member
 Join Date
 Oct 2012
 Posts
 2
 Rep Power
 0
Counting components in a graph
Hi all
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
4
0 1 0 0
1 0 0 1
0 0 0 0
0 1 0 0
5
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
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
PHP Code:01 012 / \ / / 43 3 2
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.Last edited by static_rage; 10132012 at 03:24 PM.
 10142012, 04:16 PM #2
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.
Similar Threads

scrollable graph on JFrame. (I've made the graph and I need it scrollable)
By noobplus in forum AWT / SwingReplies: 16Last Post: 03212012, 10:41 AM 
Counting characters
By Reine in forum New To JavaReplies: 5Last Post: 09282011, 09:04 PM 
Counting help
By jksmithson in forum New To JavaReplies: 1Last Post: 11062009, 03:43 AM 
Recursive Counting
By zlwilly in forum New To JavaReplies: 1Last Post: 01292009, 09:42 PM 
Counting Pixels
By shaungoater in forum Java 2DReplies: 5Last Post: 11292007, 06:51 PM
Bookmarks