1

我在 C 中有一个程序，它从文件中读取图形的定义，搜索哈密顿循环（只有一个），如果找到，则将其打印在屏幕上。问题是当我试图在具有 30 个或更多顶点的图中找到循环时，程序崩溃（对于 30 个顶点，它有时会显示循环结束崩溃（具有不同的饱和度），更多会立即崩溃）。当我尝试调试时，它会在 free() 函数处停止并显示 SIGTRAP 信号。我能做些什么来解决这个问题？这是我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

typedef struct Lista
{
    struct Lista * next;
    int v;
} Lista;

Lista * stos;

bool *visited;
int wierzcholki, krawedzie;
int *S;
int sptr;
Lista **graf;
bool czyZnaleziono = false;

int DFSHamilton(int v)
{
    if (!czyZnaleziono)
    {
        int i;
        bool test;
        Lista *p;

        S[sptr++] = v;
        if(sptr < wierzcholki)
        {
            visited[v] = true;
            for(p = graf[v]; p; p = p->next)
                if(!visited[p->v]) DFSHamilton(p->v);
            visited[v] = false;
        }
        else
        {
            test = false;
            for(p = graf[v]; p; p = p->next)
                if(!(p->v))
                {
                    test = true;
                    break;
                }

            if(test)
            {
                printf("Hamiltonian Cycle : ");
                for(i = 0; i < sptr; i++)
                {
                    printf("%d ",S[i]);
                }
                printf("0\n");
                czyZnaleziono = true;
            }
        }
        sptr--;
    }
}

int main()
{
    FILE *plik;
    Lista *p, *r;
    plik = fopen("rzeczy40-95.txt", "r");
    double start, stop, czas;
    int i, j, w1, w2;
    sptr = 0;
    visited = malloc(krawedzie*sizeof(bool));

    if (plik == NULL)
    {
        printf("Nie mozna odnalezc pliku");
        return 0;
    }
    else
    {

        fscanf(plik, "%d %d", &wierzcholki, &krawedzie);
        S = malloc(wierzcholki*sizeof(int));
        graf = malloc(wierzcholki*sizeof(Lista));
        for(i=0; i<wierzcholki; i++)
        {
            graf[i] = NULL;
            visited[i] = false;
        }

        for(j=0; j<krawedzie; j++)
        {

            fscanf(plik,"%d %d", &w1, &w2);
            p = malloc(sizeof(Lista));
            r = malloc(sizeof(Lista));
            p->v = w2;
            p->next = graf[w1];
            graf[w1] = p;
            r->v = w1;
            r->next = graf[w2];
            graf[w2] = r;
        }

        fclose(plik);

        DFSHamilton(0);

        free(visited);
        free(S);
        for (i = 0; i < wierzcholki; i++)
        {
            free(graf[i]);
        }
        free(graf);


        return 0;
    }
}
4

0 回答 0