Data Structures

Getting paths in unweighted graph between two points

what we need:

• parameters - start vertex, end vertex, graph(adjacency list)
• checklist array
• queue array

• maxMovesvariable to stop loop (Object.keys(graph.length)

• create a startObj {current: neighbour.data, prev: null }, push to checklist arr

• add source neighbours to queue. node object forEach{current: neighbour.data, prev: startObj }
• while queue is NOT empty && checklist.length < maxMoves
  1. let current vertex = shift() first item off queue
  2. if the current vertex is NOT in checklist, push current vertex to checklist
  3. for each neighbour of the vertex,
     1. if it is NOT the end vertex, push to queue
     2. if it is the end vertex, push to checklist

return checklist

Getting shortest path from above

what we need:

• parameters - start vertex, end vertex, pathArr(from above)
• shortestPath array

• current variable (pointer)

• set current to the end vertex in the pathArr, push current to shortestPath

• while current is NOT the start vertex,
  1. set current to current.prev
  2. push current
• reverse shortestPath

return shortestPath