0

我正在对来自输入文件的格式（u、v、权重）的大型图形数据集运行广度优先搜索和贝尔曼福特算法。

我在广度优先搜索中初始化，所有顶点都应该标记为 0 表示未访问。

在程序的后期，因为我在每次添加边之后都调用 BFS，而不是在程序结束时一起调用（它是贝尔曼福特和 BFS 研究项目的一部分，尽管它不太有意义）我将顶点数组重新初始化为未访问。

但是，当我运行更大的集合时，我遇到了分段错误，似乎在我重新初始化顶点数组时。我对更大的集合做出假设，因为我有一些较小的测试数据集，从 8 个顶点到 10 个，然后在 100 个或更大时它失败了。

以下是我在程序开始时的初始化方式：

for(i=0;i<numberVertices;i++)
{
    vertexArray[i].v = i+1;
    vertexArray[i].adj = NULL;
    vertexArray[i].marked = 0;
    if(i==0)
    {
        vertexArray[i].weight = 0;
    }
    else{
        vertexArray[i].weight = 10000;
    }
}

下面是我如何在 while 循环结束时重新初始化，设置为在 BFS 完成后直接到达文件末尾时中断：

BFS(q, u)
for(i=0;i<numberVertices;i++)
{
    vertexArray[i].marked = 0;
}

就像我说的那样，它似乎适用于较小的数据集，但我不明白为什么当我重新初始化时它似乎会出现段错误。

请让我知道您的想法和建议！

Valgrind 输出示例：

==6634== Memcheck, a memory error detector
==6634== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==6634== Using Valgrind-3.6.0 and LibVEX; rerun with -h for copyright info
==6634== Command: ./a.out 100S.txt
==6634==
==6634== Conditional jump or move depends on uninitialised value(s)
==6634==    at 0x400C13: checkonqueue (bfs.c:160)
==6634==    by 0x400B7F: BFS (bfs.c:142)
==6634==    by 0x40094A: main (bfs.c:103)
==6634==
==6634== Invalid write of size 4
==6634==    at 0x40096E: main (bfs.c:107)
==6634==  Address 0x4d00000041 is not stack'd, malloc'd or (recently) free'd
==6634==
==6634==
==6634== Process terminating with default action of signal 11 (SIGSEGV)
==6634==  Access not within mapped region at address 0x4D00000041
==6634==    at 0x40096E: main (bfs.c:107)
==6634==  If you believe this happened as a result of a stack
==6634==  overflow in your program's main thread (unlikely but
==6634==  possible), you can try to increase the size of the
==6634==  main thread stack using the --main-stacksize= flag.
==6634==  The main thread stack size used in this run was 10485760.
==6634==
==6634== HEAP SUMMARY:
==6634==     in use at exit: 3,448 bytes in 181 blocks
==6634==   total heap usage: 181 allocs, 0 frees, 3,448 bytes allocated
==6634==
==6634== LEAK SUMMARY:
==6634==    definitely lost: 0 bytes in 0 blocks
==6634==    indirectly lost: 0 bytes in 0 blocks
==6634==      possibly lost: 0 bytes in 0 blocks
==6634==    still reachable: 3,448 bytes in 181 blocks
==6634==         suppressed: 0 bytes in 0 blocks
==6634== Reachable blocks (those to which a pointer was found) are not shown.
==6634== To see them, rerun with: --leak-check=full --show-reachable=yes
==6634==
==6634== For counts of detected and suppressed errors, rerun with: -v
==6634== Use --track-origins=yes to see where uninitialised values come from
==6634== ERROR SUMMARY: 16120 errors from 2 contexts (suppressed: 6 from 6)
Segmentation fault (core dumped)

检查队列功能：

int checkonqueue(int * q, int value)
{
    int i = 0;
    for(i=0;i < max;i++)
    {
        if(q[i] == value)
        {
            return 1;
        }
    }
    return 0;
}

第 160 行是 if 条件的行

4

0 回答 0