dfs on a disconnected graph

This is a discussion on dfs on a disconnected graph within the C++ Programming forums, part of the General Programming Boards category; hi suppose that we have a adjacency list that represents a disconnected graph I have a function that uses recursion ...

  1. #1
    nik
    nik is offline
    Registered User
    Join Date
    Nov 2010
    Posts
    44

    dfs on a disconnected graph

    hi

    suppose that we have a adjacency list that represents a disconnected graph

    I have a function that uses recursion in order to implement the DFS but it doesn't work when the graph is disconnected..

    what's the best way to implement dfs on a disconnected graph?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You need to do dfs on each component of the graph. So pick a vertex, do dfs and you'll find the entire connected component which that vertex is on. Once you're done, pick another vertex (and keep picking until you find an unvisited one), and do it again. Lather, rinse, and repeat.

  3. #3
    nik
    nik is offline
    Registered User
    Join Date
    Nov 2010
    Posts
    44
    Quote Originally Posted by tabstop View Post
    You need to do dfs on each component of the graph. So pick a vertex, do dfs and you'll find the entire connected component which that vertex is on. Once you're done, pick another vertex (and keep picking until you find an unvisited one), and do it again. Lather, rinse, and repeat.
    thank you it worked great

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Generate Disconnected Graph in C
    By anirban in forum C Programming
    Replies: 3
    Last Post: 06-08-2008, 09:04 AM
  2. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 07:55 PM
  3. Problem using DFS with a DAG graph
    By incognito54 in forum C Programming
    Replies: 2
    Last Post: 05-11-2005, 06:16 AM
  4. determining a path through the graph
    By Mist in forum C Programming
    Replies: 2
    Last Post: 02-27-2005, 11:21 AM
  5. Minimize crossing edges in undirected graph
    By Shiro in forum C Programming
    Replies: 0
    Last Post: 12-26-2001, 03:48 AM

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