• Post Reply Bookmark Topic Watch Topic
  • New Topic

Adjecency Matrix Algorithm - "Find the Spy"

 
Johnny Hagen
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've got problems with a task requireing me to go through a 500x500 adjecency matrix to find a "spy" (the node that's attached to all the others, but none is attached to it). Of course, there's no problem doing it the hard way, getting a O(n^2) time complexity, but the task says there's a O(n) way of finding it. Can anyone help me on this one? Thanx in advance
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There was a maze solving puzzle in the programming diversions forum, and several solutions used a Knuth algorithm for mapping connectedness and pathlength. You might snoop there and see if that algorithm helps.
 
Johnny Hagen
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanx...will do!
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Moving to performance forum...
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!