Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #32459

Re: Backtracking algorithms and graph connection

Newsgroups comp.lang.javascript
Date 2017-02-03 11:03 -0800
References <630d7b1b-8682-4f75-a8a1-808f98641a47@googlegroups.com>
Message-ID <df83bb74-0771-41db-b614-912053c7aa8d@googlegroups.com> (permalink)
Subject Re: Backtracking algorithms and graph connection
From "Michael Haufe (TNO)" <tno@thenewobjective.com>

Show all headers | View raw

jonas.t...@gmail.com wrote:
> To check if a graph connected seem to be a pretty hard problem, 

That depends on your definition of "hard"

> i was thinking making chains of nodes linked connections, and then after the chains created check for interrelationships between the chains. So as one chain ends you start a new one and if any the nodes in the new chain link back to any other, you do not have to check anymore until the new chain broken is again. So as you progress the set of linked nodes get bigger and bigger.
> 
> So i only check if the new chain have any connection to the masterchain?
> 
> Does it seem as a reasonable approach, i can't come up with any faster.

Just do a BFS/DFS on the graph and mark the the nodes visited. If every node is visited then the graph is connected.

> What time complexity would such a chain backtracking algorithm have?

O(|V| + |E|) with the BFS approach

Back to comp.lang.javascript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 01:19 -0800
  Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 01:53 -0800
  Re: Backtracking algorithms and graph connection Silvio <silvio@internet.com> - 2017-02-03 11:09 +0100
    Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 03:28 -0800
  Re: Backtracking algorithms and graph connection "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-02-03 11:03 -0800
    Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 17:16 -0800
      Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 17:18 -0800
        Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 17:32 -0800
          Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-03 17:59 -0800
      Re: Backtracking algorithms and graph connection "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-02-04 10:26 -0800
        Re: Backtracking algorithms and graph connection jonas.thornvall@gmail.com - 2017-02-04 23:07 -0800

csiph-web