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

Groups > comp.lang.javascript > #32463

Re: Backtracking algorithms and graph connection

Show all headers | View raw

Den lördag 4 februari 2017 kl. 02:32:30 UTC+1 skrev jonas.t...@gmail.com:
> Den lördag 4 februari 2017 kl. 02:18:16 UTC+1 skrev jonas.t...@gmail.com:
> > Den lördag 4 februari 2017 kl. 02:16:20 UTC+1 skrev jonas.t...@gmail.com:
> > > Den fredag 3 februari 2017 kl. 20:03:28 UTC+1 skrev Michael Haufe (TNO):
> > > > 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
> > > 
> > > I see that BFS is a linear approach and time complexity, and i realise my is much much faster. So it must be another approach.
> > > 
> > > I implement mine 2 or 3 times before with alot of grief, but maybe this time i have a better datastructure.
> > 
> > Sorry was thinking wrong my approach is definitly linear.
> 
> So the linearity in my graph is that each node of course will be travered, and each node have links but my approach do not need travelse every edge/link of the node it settles when it find a new one, and that may make it faster it do not need to traverse all the edges/links of all the nodes.
> 
> I think that BFS traverse all edges? So if there is 1000's of edges/links from each node my algorithm will be a timesaver? Becuse it doesn't care it just form chains. And check the interconnections, it seem for bad and good my algorithm do not care about the underlying tree, just the viable chaining.

Probably it is my storage structure of connections that make it viable, each node carry its own set of outgoing links/edges.

I do not need to traverse to make chains. The edges/links are attributes to the nodes.

  arr[m] ={nodelinks : []}

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