c - C 中的广度优先搜索代码，可能的堆栈溢出

Question

我使用压缩的稀疏行数据结构用 C 编写了广度优先搜索的代码。该代码似乎对于一个图表运行良好，但对于另一个图表文件返回错误。它适用于 this file但会抛出 this file 的错误作为 C 编程新手，我找不到问题的原因，希望得到任何帮助

我尝试检查 while 循环的条件。当代码挂起并返回错误时，循环的条件为真。我使用 mingw 编译器在 CodeBlocks 16.01 上运行此代码。

#include <stdio.h>
#include <stdlib.h>
// Declaring a struct type to hold

int main(){
int n, m, counter, current, x, src, dst;
n=0, m=0, counter = 0, current =0, src = 0, dst = 0;

FILE *fp; //create a pointer to the file directory
fp = fopen("filename.graph","r"); //set the directory pointer to the path of the text file containing graph data
if ((fp == NULL)){ perror("Error, no such file exists \n");  exit(1);} 
//If file not found, print error message and exit the program
else
    {
        fscanf(fp,"%d %d", &n,&m); //read first line of text file to get number of vertices and edges in graph

        struct CSRgraph //Create CSR data structure
            {
                int heads[m];    //Stores heads of edges
                int offsets[n+1]; //Stores information on the number of edges leaving each node
            };
        struct CSRgraph g;  //Create an instance of the CSR graph data structure
        g.offsets[0] = 0; //Set the initial offset value to 0
        g.offsets[n] = m; //Set the offset value of 'phantom' node to the number of edges in graph

        for(x=0;x<m;x++) //iterate over all lines containing edge information in text file
            //Read file and create CSR data structure from information in text file
            {
                fscanf(fp,"%d %d",&src,&dst); //read source and head information from file
                g.heads[x] = dst; //assign head information to the next available slot in data structure
                if (src < n+1) //Check that node is valid
                    {
                        if (src == current) //check that current edge originates from same source as previous edge
                            {
                                counter++; //increment counter for the number of edges that originate from current source
                            }
                        else //Current edge does not originate from previous source. New source node encountered
                            {
                                g.offsets[src] = counter + g.offsets[src -1]; //Update offset value for previous source
                                counter = 1; //restart edge origin counter
                                current = src ; //set current to current source
                            }
                    }

            }

fclose(fp); //Close file after use

int Discovered[n],Queue[n+1],Explored[n], *front_ptr,*end_ptr,*exp_ptr;
front_ptr = Queue;  //Initialize the front pointer to the Queue array
end_ptr = Queue;    //Initialize the end pointer to the Queue array
exp_ptr = Explored; //Initialize the explored pointer to the Explored array

for (x=0;x<n;x++)
{
    Discovered[x] = 0; //An array to track discovered nodes. Not necessarily explored, but nodes that have showed up previously
}
// Advance the pointers in the direction you want
*end_ptr = 0; //setting the first element in the queue as the node 0
end_ptr++; //advancing the end pointer to the next available array spot
Discovered[0] = 1;

while (front_ptr != end_ptr)
    { //Queue is empty if front pointer is the same as end pointer
        int p,curr;
        curr = *front_ptr; //grab the front of the queue and set it as current node
        front_ptr++; //equivalent to removing from element and pushing the next node in line to the front
        *exp_ptr = curr; //set current node to explored
        exp_ptr++; //advance the explored pointer one step

    for (p = g.offsets[curr]; p < g.offsets[curr+1]; p++)
        //iterate over all neighbors of current node
        {
        if (Discovered[g.heads[p]] == 0)
        //if node is not already discovered, set it to discovered, add it to queue and advanced the end pointer of queue one step
            {
                Discovered[g.heads[p]] = 1;
                *end_ptr = g.heads[p];
                end_ptr++;
            }
        }
    }

}
    return 0;
}

Answer 1

您对int heads[m];的使用作为 int 的 VLA m = 108744 (以及您分配的 2950 整数的其他 4 个 VLA)可能会导致 StackOverflow...(这将取决于编译器、操作系统和内存模型)。要解决此问题，请更改 CSRgraph让成员(member)heads和offsets是指针，然后根据从文件第一行读取的数字动态分配存储，例如

typedef struct {    /* typdef for convenience */
    int *heads,
        *offsets;
} CSRgraph_t;

int main (int argc, char **argv) {

    CSRgraph_t g;                   /* declare instance of struct */
    ...
    /* allocate/validate g.heads & g.offsets */
    if (!(g.heads = malloc (m * sizeof *g.heads))) {
        perror ("malloc-g.heads");
        return 1;
    }
    /* calloc used to zero g.offsets */
    if (!(g.offsets = calloc ((n + 1), sizeof *g.offsets))) {
        perror ("malloc-g.offsets");
        return 1;
    }
    g.offsets[0] = 0;
    g.offsets[n] = m;
    ...

(注意: calloc 用于 offsets 将其初始化为全零，以便稍后比较 p < g.offsets[curr+1] )

总而言之，你可以这样做:

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

typedef struct {    /* typdef for convenience */
    int *heads,
        *offsets;
} CSRgraph_t;

int main (int argc, char **argv) {

    CSRgraph_t g;                   /* declare instance of struct */
    int n, m, counter, current;
    n = m = counter = current = 0;
    /* use filename provided as 1st argument (stdin by default) */
    FILE *fp = argc > 1 ? fopen (argv[1], "r") : stdin;

    if (!fp) {  /* validate file open for reading */
        perror ("file open failed");
        return 1;
    }
    if (fscanf (fp, "%d %d", &n, &m) != 2) {    /* validate EVERY read */
        fputs ("error: invalid format n, m.\n", stderr);
        return 1;
    }

    /* allocate/validate g.heads & g.offsets */
    if (!(g.heads = malloc (m * sizeof *g.heads))) {
        perror ("malloc-g.heads");
        return 1;
    }
    /* calloc used to zero g.offsets */
    if (!(g.offsets = calloc ((n + 1), sizeof *g.offsets))) {
        perror ("malloc-g.offsets");
        return 1;
    }
    g.offsets[0] = 0;
    g.offsets[n] = m;

    for (int x = 0; x < m; x++) {
        int src;    /* src is only needed within scope of loop */
        if (fscanf (fp, "%d %d", &src, &g.heads[x]) != 2) {
            fprintf (stderr, "error: invalid format - line %d.\n", x);
        }
        if (src < n+1) {
            if (src == current)
                counter++;
        }
        else {
            g.offsets[src] = counter + g.offsets[src -1];
            counter = 1;    /* restart edge origin counter */
            current = src;  /* set current to current source */
        }
    }

    if (fp != stdin) fclose (fp);   /* close file if not stdin */

    int Discovered[n], Queue[n+1], Explored[n], 
        *front_ptr, *end_ptr, *exp_ptr;

    front_ptr = Queue;  /* front pointer to the Queue array */
    end_ptr = Queue;    /* end pointer to the Queue array */
    exp_ptr = Explored; /* explored pointer to the Explored array */

    for (int x = 0; x < n; x++)
        Discovered[x] = 0;

    /* Advance the pointers in the direction you want */
    *end_ptr = 0;
    end_ptr++;
    Discovered[0] = 1;

    while (front_ptr != end_ptr) {
        int curr = *front_ptr;
        front_ptr++;
        *exp_ptr = curr;
        exp_ptr++;

        for (int p = g.offsets[curr]; p < g.offsets[curr+1]; p++) {
            if (Discovered[g.heads[p]] == 0) {
                Discovered[g.heads[p]] = 1;
                *end_ptr = g.heads[p];
                end_ptr++;
            }
        }
    }

    free (g.heads);
    free (g.offsets);

    return 0;
}

(注意:避免硬编码文件名，例如 fopen("filename.graph","r") 、 main() 接受参数，使用它们将文件名作为第一个参数传递给程序[您可以从 stdin 读取如果没有提供参数则默认])

内存使用/错误检查

$ valgrind ./bin/readgraphsfile ~/tmp/graphfile/large.graph
==17345== Memcheck, a memory error detector
==17345== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==17345== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==17345== Command: ./bin/readgraphsfile ~/tmp/graphfile/large.graph
==17345==
==17345==
==17345== HEAP SUMMARY:
==17345==     in use at exit: 0 bytes in 0 blocks
==17345==   total heap usage: 3 allocs, 3 frees, 447,332 bytes allocated
==17345==
==17345== All heap blocks were freed -- no leaks are possible
==17345==
==17345== For counts of detected and suppressed errors, rerun with: -v
==17345== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

它与您的 large.graph 配合得很好文件。