C语言实现Prim、Dijkstra算法时，图add_edge函数实现遇阻求助

Got it, let's work through this step by step. You're tackling an assignment to implement Prim's and Dijkstra's algorithms with an adjacency list graph, and you're stuck on the add_edge function. Let's fill in the missing pieces and break down each part so it makes sense.

Step 1: Complete the Header Declarations #

First, let's finish the truncated add_edge function in your header (I'll assume we're building an undirected graph since Prim's algorithm works on undirected graphs—we can adjust for directed if needed):

// APIs for graph representation by adjacency list
typedef struct ADJNODE {
    // adjacency node
    int vertex;
    int weight;
    struct ADJNODE *next;
} adjnode;

typedef struct GRAPH {
    int vn; // number of nodes
    adjnode **adjlist; // pointer to an array of pointers of neighbors
} graph;

graph *new_graph(int n);
void add_edge(graph *g, int u, int v, int weight);
void free_graph(graph *g); // helper to clean up memory leaks

Step 2: Implement new_graph #

This function sets up a blank graph with n vertices. We need to allocate memory for the graph struct and the adjacency list array, then initialize each vertex's neighbor list to empty:

#include <stdlib.h>

graph *new_graph(int n) {
    if (n <= 0) return NULL; // invalid vertex count

    graph *g = (graph *)malloc(sizeof(graph));
    if (!g) return NULL; // handle memory allocation failure

    g->vn = n;
    // Allocate array of adjacency list heads
    g->adjlist = (adjnode **)malloc(n * sizeof(adjnode *));
    if (!g->adjlist) {
        free(g); // clean up if adjlist allocation fails
        return NULL;
    }

    // Initialize each adjacency list to empty (NULL)
    for (int i = 0; i < n; i++) {
        g->adjlist[i] = NULL;
    }

    return g;
}

Step 3: Implement add_edge #

The core of your problem—this function creates a new adjacency node and inserts it into the source vertex's list. For undirected graphs, we need to add the edge in both directions (from u to v and v to u):

// Helper to create a single adjacency node
static adjnode *create_adjnode(int v, int weight) {
    adjnode *new_node = (adjnode *)malloc(sizeof(adjnode));
    if (!new_node) return NULL;
    new_node->vertex = v;
    new_node->weight = weight;
    new_node->next = NULL;
    return new_node;
}

void add_edge(graph *g, int u, int v, int weight) {
    // Validate inputs to avoid out-of-bounds errors
    if (!g || u < 0 || u >= g->vn || v < 0 || v >= g->vn) {
        return;
    }

    // Add edge from u to v (insert at head for O(1) efficiency)
    adjnode *node_u = create_adjnode(v, weight);
    if (node_u) {
        node_u->next = g->adjlist[u];
        g->adjlist[u] = node_u;
    }

    // For undirected graphs, add reverse edge from v to u
    // Remove this block if you need a directed graph
    adjnode *node_v = create_adjnode(u, weight);
    if (node_v) {
        node_v->next = g->adjlist[v];
        g->adjlist[v] = node_v;
    }
}

Step 4: Helper Function free_graph #

Don't forget to clean up memory to avoid leaks—critical for testing and long-running code:

void free_graph(graph *g) {
    if (!g) return;

    // Free each node in every adjacency list
    for (int i = 0; i < g->vn; i++) {
        adjnode *current = g->adjlist[i];
        while (current) {
            adjnode *temp = current;
            current = current->next;
            free(temp);
        }
    }

    // Free the adjacency list array and graph struct
    free(g->adjlist);
    free(g);
}

Quick Tip for Your Algorithms (Prim & Dijkstra) #

Both algorithms will need to iterate over a vertex's neighbors. Here's how you'll loop through the adjacency list of vertex u in your code:

adjnode *current = g->adjlist[u];
while (current) {
    int neighbor = current->vertex;
    int edge_weight = current->weight;
    // Use these values in your Prim/Dijkstra logic
    current = current->next;
}

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