Finding the number of connected components

This is a discussion on Finding the number of connected components within the C Programming forums, part of the General Programming Boards category; Hello, I can't figure out how to find the number of connected components from an undirected disconnected graph. the input ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    7

    Finding the number of connected components

    Hello,

    I can't figure out how to find the number of connected components from an undirected disconnected graph.

    the input I'm getting is like this:
    7
    1 2
    4 5
    3 6
    2 7

    the top number is the number of vertices and the rest of the numbers are the edges, eg. 1--2 is an edge.

    Is there a way that you can implement DFS algorithm to find the number of connected components?
    like increment a variable every time DFS is called or something?


    Thanks in advance

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,673
    So what's the intended output of all this?

    Something like
    There are 3 separate components
    1 2 7
    4 5
    3 6

    A first step would be to write the code to just read the input data into some kind of data structure.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 10-31-2009, 06:49 PM
  2. Connected Components not quite working
    By taurus in forum C Programming
    Replies: 1
    Last Post: 09-22-2009, 06:23 PM
  3. Finding The Hcf Of A Number
    By Saimadhav in forum C++ Programming
    Replies: 5
    Last Post: 10-31-2008, 06:50 AM
  4. Storing components of a complex number
    By cashmerelc in forum C Programming
    Replies: 6
    Last Post: 11-19-2007, 12:37 PM
  5. number of components
    By kellymart87 in forum C++ Programming
    Replies: 2
    Last Post: 04-17-2007, 09:26 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21