Gettin Memory Limit with BFS

Let's talk about algorithms!

Moderator: Board moderators

Sotek
New poster
Posts: 8
Joined: Mon Jun 05, 2006 12:06 am
Location: Murcia, Spain

Gettin Memory Limit with BFS

First of all sorry about mi English cause is not very good
I'm trying to solve the problem called "The mysterious X network", you can see it here: http://acmicpc-live-archive.uva.es/nuev ... php?p=3502

I'm using BFS but the judge doesn't accept the problem because of the memory usage (memory limit)
What i'm doing wrong ?

Thank you in advance

Code: Select all

``````#include <iostream>
#include <list>
#include <queue>
#include <stdio.h>

using namespace std;

typedef list<int> ListaNodos;
typedef list<int>::iterator ListaNodosIterador;

typedef struct dnodo {
int nodo;
int distancia;
} dnodo;

int main() {
int casos, i, j, k, n, w, camarada, conoce, tio, inicio, fin;
ListaNodos *C;
ListaNodosIterador it;
dnodo *actual, *tmp;
scanf("%d", &casos);
queue<dnodo *> Q;
for(i=0; i<casos; i++) {
// get input
scanf("%d", &n);
C = new ListaNodos[n];
for(j=0; j<n; j++) {
scanf("%d", &camarada);
scanf("%d", &conoce);
for(k=0;k<conoce;k++) {
scanf("%d", &tio);
C[camarada].push_back(tio);
C[tio].push_back(camarada);
}
}
// get the start (inicio) and end (fin) node
scanf("%d", &inicio);
scanf("%d", &fin);
// BFS
actual = new dnodo;
actual->nodo=inicio;
actual->distancia=0;
Q.push(actual);
while(1) {
actual = Q.front();
Q.pop();
if(actual->nodo == fin) {
while(!Q.empty()) {
tmp = Q.front();
delete tmp;
Q.pop();
}
// Print the solution
printf("%d %d %d\n", inicio, fin, actual->distancia-1);
break;
}
it=C[actual->nodo].begin();
while(it != C[actual->nodo].end()) {
w = *it;
tmp = new dnodo;
tmp->distancia = actual->distancia+1;
tmp->nodo = w;
Q.push(tmp);
*it++;
}
delete actual;
}
for(j=0; j<n; j++) {
C[j].clear();
}
delete[] C;
}
return 0;
}
``````

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
i think there is a problem in ur code which is QUEUE overflow.
so check ur code again or change the code again or use array instead of VECTOR. Then experiment with vector.
ok.
i did the same thing may be 1yr ago.

Sotek
New poster
Posts: 8
Joined: Mon Jun 05, 2006 12:06 am
Location: Murcia, Spain
I've found the problem.
The queue got very big very soon because I did not check to expand a node just if it wasn't expanded previously.

Jus added this:

bool expandedNodes = new bool[n];

Thank you for helping me asif_rahman0!

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
In general, many BFS code will get memory limit exceded because the actual solution isn't BFS at all.

There are some DP problems, which seems like BFS, but you must use DP.

Sotek
New poster
Posts: 8
Joined: Mon Jun 05, 2006 12:06 am
Location: Murcia, Spain
ok shamim, thank you