# Thread: Counting components in a graph

1. Member
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:
```0---1              0---1---2
/               \      /
/                  4----3
3    2```
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.
Last edited by static_rage; 10-13-2012 at 03:24 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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•