15,969,543 members
1.00/5 (1 vote)
See more:
Hello everyone,

I want to erase an element from adjacency list (this is a digraph) if the element is equal to the vertex passed to the function (in this case, if it is equal to 'u'). I want to do it while traversing the graph (using BFS). Does anyone know how I can do it?

Here is the code I'm using to traverse the graph (BFS) and erase the edges. But it doesn't do the job properly:

C++
```void Graph::BFS(int u) {
int w;
bool *visited = new bool[V];
queue<int> q;
visited[u] = true;
q.push(u);

while(!q.empty()) {
w = q.front();
cout << w << " ";
q.pop();
list<int>::iterator i;

for(i=adj[w].begin(); i!= adj[w].end(); ) {
if(!visited[*i]) {
if(u == *i)
adj[w].erase(i++);
visited[*i] = true;
q.push(*i);
++i;
}
++i;
}
}
}```

Global variables used in BFS function:
int V; //Number of vertices
list<int> *adj; //Pointer to an array containing adjacency lists

What I have tried:

I tested my code on following Graph:

0->0 , 0->1 , 0->2, 1->2, 2->3, 3->3

My code does the job correctly when I start from 0 or 1, but trapped in an infinite loop (probably) when I pass 2 or 3 to the BFS.
Posted
Updated 10-May-16 10:43am
v8
Comments
MinooN 10-May-16 11:44am
I did initialize the array. "int V" (number of vertices) is a global variable in class Graph. But I should have mention it in my post. Thanks for your attention!

## Solution 2

You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.

The debugger allow you to follow the execution line by line, inspect variables and you will see that there is a point where it stop doing what you expect.
Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]

Quote:
but trapped in an infinite loop (probably) when I pass 2 or 3 to the BFS.

With the debugger, you will see where is the infinite loop.

Comments
MinooN 10-May-16 18:50pm
Thanks @ppolymorphe for your advice!

## Solution 1

Lets start with the most obvious problem I can see, that you haven't initialized the bool array visited

`bool *visited = new bool[V]; // this leaves all the values in the array random `
are you sure you didn't mean to initialize it like so?
`bool *visited = new bool[V](); // this zeros the entire array `

Alternatively just memset etc the array to initialize it.

v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Top Experts
Last 24hrsThis month
 Richard Deeming 120 OriginalGriff 23 lukeer 10 Dave Kreskowiak 10 Pete O'Hanlon 10
 OriginalGriff 361 Pete O'Hanlon 275 Richard Deeming 175 Dave Kreskowiak 165 merano99 115

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900