Results 1 to 2 of 2
  1. #1
    static_rage is offline Member
    Join Date
    Oct 2012
    Posts
    2
    Rep Power
    0

    Default 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 04:24 PM.

  2. #2
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default 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

  1. Replies: 16
    Last Post: 03-21-2012, 10:41 AM
  2. Counting characters
    By Reine in forum New To Java
    Replies: 5
    Last Post: 09-28-2011, 10:04 PM
  3. Counting help
    By jksmithson in forum New To Java
    Replies: 1
    Last Post: 11-06-2009, 03:43 AM
  4. Recursive Counting
    By zlwilly in forum New To Java
    Replies: 1
    Last Post: 01-29-2009, 09:42 PM
  5. Counting Pixels
    By shaungoater in forum Java 2D
    Replies: 5
    Last Post: 11-29-2007, 06:51 PM

Posting Permissions

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