[Java] Exception in BFS/DFS algorithm for graph

[ramsrib]

In section 12.3.1, the algorithm for BFS & DFS is given as below:

void bfs(Graph g, int r) {
   boolean[] seen = new boolean[g.nVertices()];
   Queue<Integer> q = new SLList<Integer>();
   q.add(r);
   seen[r] = true;
   while (!q.isEmpty()) {
     int i = q.remove();
     for (Integer j : g.outEdges(i)) {
      if (!seen[j]) {
         q.add(j);
         seen[j] = true;
} }
} }

There is mistake in the below highlighted line. It iterates over the value of the edges rather than index. for (Integer j : g.outEdges(i)) {

If graph doesn't have sequenced number as value, the following line will throw ArrayIndexOutOfBoundsException.

if (!seen[j]) {

For example, graph like this: 0->1, 0->5, 3 -> 5, 0 -> 3 where size of the graph is 4. while i = 0 and j = 5, It'll try access the seen array with index value 5. which won't exist and throw exception. Because, seen array won't have 5th index.

It also applies to section 12.3.2 (DFS).