Ошибка сегментации при поиске в глубину больших графов в c - PullRequest
Новая
       26

Ошибка сегментации при поиске в глубину больших графов в c

0 голосов
/ 03 марта 2012

У меня есть следующая рекурсивная реализация поиска в глубину.В конце массив предварительно показывает, в каком порядке были посещены несколько вершин.Я хочу запустить его для действительно больших графиков.В этом примере: n = 2097152, m = 6291408. G представлен в виде списка смежности. 

static int cnt, pre[2097152];
static link t;

void dfsRAdjazenz(Graph G, Edge e)
{ 
    int w = e.w 
    pre[w] = cnt++; 

    for (t = G->adj[w]; t != NULL; t = t->next) {
        if (pre[t->v] == -1) {            
            Edge e = {w, t->v};
            dfsRAdjazenz(G, e); 
        }
    }
}

int main (int argc, const char * argv[])
{   
    cnt=0;
    int v;
    for (v = 0; v < 2097152; v++) {
        pre[v] = -1;
    }

    Edge e = {1,1};
    dfsRAdjazenz(G, e);
    return 0;
}

Проблема в том, что у меня всегда недостаточно памяти -> ошибка сегментации, хотя памяти действительно достаточно,Он работает примерно с 1 миллионом узлов.

Редактировать: структуры данных: 

typedef struct node *link;  

struct node { 
    int v; 
    link next; 
};

struct graph { 
    int V; 
    int E; 
    link *adj; 
};

typedef struct { 
    int v; 
    int w; 
} Edge;

typedef struct graph *Graph;

Ответы [ 2 ]

2 голосов
/ 03 марта 2012

Возможно, из-за используемой вами рекурсии вы исчерпали стек. если график не разреженный, то рекурсия может быть очень глубокой, и это также объясняет, почему она работает с небольшими значениями.

1 голос
/ 03 марта 2012

Это кажется мне странным 

t = G->adj[w]

Вы используете индексирование массива в том, что выглядит как связанный список.

Я бы ожидал, что это вызовет ошибку для любого значения, кроме 1.

Конечно, трудно понять, не видя определения G.

...