Gettin Memory Limit with BFS

Let's talk about algorithms!

Moderator: Board moderators

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

Gettin Memory Limit with BFS

Post by Sotek » Mon Jun 05, 2006 12:10 am

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

Post by asif_rahman0 » Wed Jun 07, 2006 4:29 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

Post by Sotek » Thu Jun 08, 2006 12:25 am

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!

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Thu Jun 08, 2006 8:56 am

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

Post by Sotek » Sun Jun 11, 2006 5:29 pm

ok shamim, thank you :)

Post Reply

Return to “Algorithms”