educative.io

Why are we using temp.data as an indices?

Courses
,
#1 
function bfsTraversal_helper(g, source, visited, obj) {
 
  let queue = new Queue(g.vertices);queue.enqueue(source);

  visited[source] = true;

  //Traverse while queue is not empty
  while (queue.isEmpty() == false) {
    //Dequeue a vertex/node from queue and add it to result
    let current_node = queue.dequeue();
    obj.result += String(current_node);

    //Get adjacent vertices to the current_node from the list,
    //and if they are not already visited then enqueue them in the Queue

    let temp = g.list[current_node].getHead();

    while (temp != null) {

      //if the node is not visited
      if (**visited[temp.data]** == false) {

        //push it to the queue
        queue.enqueue(temp.data);

        //update that it's visited 
        **visited[temp.data]** = true; //Visit the children
      }

      //go through the next node 
      temp = temp.nextElement;
    }
  }
}

From the solution above, could anyone explain to me why we’re using temp.data as an indices? In that case, wouldn’t the value of each indices could be only 0,1,2,3… (sorted and starts from 0)? I’ve tried a different case with

g1.addEdge(5, 9);
g1.addEdge(5, 8);
g1.addEdge(9, 2);
g1.addEdge(9, 3);
console.log(bfsTraversal(g1, 0));

The result is incorrect.

Course: Data Structures for Coding Interviews in JavaScript - Learn Interactively
Lesson: Solution Review: Implement Breadth First Search - Data Structures for Coding Interviews in JavaScript

#2

Hi @Mingeng !!
In the provided code, temp.data is used as an index to access vertices in the graph. It assumes that the vertices in the graph are represented using integer values starting from 0 and increasing consecutively. In many cases, graphs are represented this way, where each vertex is assigned a unique integer value as its identifier.

For example, if you have a graph with five vertices, they might be labeled as follows:

Vertex 0
Vertex 1
Vertex 2
Vertex 3
Vertex 4

The code uses these integer values as indices to access the visited array and the adjacency list of the graph (g.list). When it dequeues a vertex from the queue, it gets the adjacent vertices from the adjacency list and checks if they are visited by using visited[temp.data].
I hope it helps. Happy learning :blush: