breadth-first search using an adjacency matrix

[sierramae]

Hi everyone,
I'm trying to implement a breadth-first search using an adjacency matrix for my undirected graph. Basically given v1 and v2, I'm trying to find a path of any length between them, and return this path. I already tried to implement it, but it outputs a path that doesn't make sense. I'm assuming you need to use a queue to keep track of unvisited neighbors, and somehow include a vector that stores the path. It needs to be able to back-track. How would I go about doing this? Thanks.

[ne555]

|to_expand visited tree| 
to_expand := Queue new.
to_expand push: root.
visited add: root.
[to_expand isEmpty] whileFalse:[
  |node|
  node := to_expand front.
  [node neighbours] do:[:K|
    (visited include: K) ifFalse:[
      visited add: K.
      tree link: node with: K.
      to_expand push: K.
    ].
  ].
  to_expand pop.
].

That will construct the spanning tree. But if you only care about the path, stop as soon as you find the other node.
Then follow the links in the tree.