C语言读取有向图文件数据用于BFS算法的方法咨询

First, let's fix a critical detail in your existing code: your addEdge function currently adds undirected edges (both src→dest and dest→src), but your input file describes a directed graph. Let's modify that first to only add the directed edge:

void addEdge(struct Graph* graph, int src, int dest) {
    // Add directed edge from src to dest (only one way)
    struct node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

Next, we need to write a function to read the graph-file.txt format and build your graph structure. The file uses 1-based vertex numbering, but your code uses 0-based indices, so we'll adjust for that during parsing.

Step 1: File Loading Function #

Here's a function that handles opening the file, parsing the vertex count, and building the adjacency lists:

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

// Add this function to your code
struct Graph* loadGraphFromFile(const char* filename) {
    FILE* file = fopen(filename, "r");
    if (!file) {
        printf("Error: Could not open file %s\n", filename);
        return NULL;
    }

    int numVertices;
    // Read the first line (vertex count)
    if (fscanf(file, "%d", &numVertices) != 1) {
        printf("Error: Invalid vertex count in file\n");
        fclose(file);
        return NULL;
    }

    // Create empty graph
    struct Graph* graph = createGraph(numVertices);

    // Skip any leftover characters (like newline) after vertex count
    fscanf(file, "%*[^\n]");
    fgetc(file);

    char lineBuffer[256];
    // Read the second line containing adjacency lists
    if (!fgets(lineBuffer, sizeof(lineBuffer), file)) {
        printf("Error: Could not read adjacency list line\n");
        fclose(file);
        freeGraph(graph); // We'll implement this next
        return NULL;
    }

    char* currentPos = lineBuffer;
    for (int vertexIdx = 0; vertexIdx < numVertices; vertexIdx++) {
        // Find the opening brace for this vertex's neighbors
        while (*currentPos != '{' && *currentPos != '\0') {
            currentPos++;
        }
        if (*currentPos == '\0') break; // Malformed input

        currentPos++; // Move past '{'

        int neighbor;
        // Parse each neighbor until closing brace
        while (*currentPos != '}' && *currentPos != '\0') {
            // Skip spaces and commas
            while ((*currentPos == ' ' || *currentPos == ',') && *currentPos != '\0') {
                currentPos++;
            }
            if (*currentPos == '}' || *currentPos == '\0') break;

            // Read neighbor value (1-based)
            if (sscanf(currentPos, "%d", &neighbor) == 1) {
                // Convert to 0-based index and add directed edge
                addEdge(graph, vertexIdx, neighbor - 1);
            }

            // Move past the neighbor number
            while (*currentPos != ' ' && *currentPos != ',' && *currentPos != '}' && *currentPos != '\0') {
                currentPos++;
            }
        }

        currentPos++; // Move past '}'
    }

    fclose(file);
    return graph;
}

// Add this function to free graph memory (prevents leaks)
void freeGraph(struct Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        struct node* temp = graph->adjLists[i];
        while (temp != NULL) {
            struct node* nextNode = temp->next;
            free(temp);
            temp = nextNode;
        }
    }
    free(graph->adjLists);
    free(graph->visited);
    free(graph);
}

Step 2: Using the Loader in Main #

Now you can use this function to load your graph and run BFS. Here's a sample main function:

int main() {
    struct Graph* graph = loadGraphFromFile("graph-file.txt");
    if (!graph) {
        return 1;
    }

    printf("Graph Adjacency Lists:\n");
    printGraph(graph);

    // Run BFS starting from vertex 1 (0-based index 0)
    printf("\nStarting BFS from vertex 1:\n");
    bfs(graph, 0);

    // Clean up memory
    freeGraph(graph);
    return 0;
}

Key Notes: #

• 1-based vs 0-based: The input file uses 1-based vertex numbers (vertex 1 to 7), but your graph structure uses 0-based indices (0 to 6). The loader converts neighbors by subtracting 1.
• Empty neighbor lists: The parser handles empty lists like {} or { } correctly, skipping them without adding any edges.
• Error handling: The loader checks for file opening errors, invalid vertex counts, and malformed adjacency list lines to avoid crashes.

When you run this code with your graph-file.txt, it will correctly build the directed graph and perform BFS starting from vertex 1 (0-based index 0).

内容的提问来源于stack exchange，提问作者NOA