如何访问和循环访问邻接表？

Question

这是我用来形成图形的邻接表的实现。我不知道如何访问此列表并循环遍历它以实现某些目标（例如 DFS 搜索）。

我试图做类似 graph[i][j] 的事情，但编译器会说这是一个错误

subscripted value is neither array nor pointer

我认为这里的图表只是指向另一个列表的指针。

我该怎么办？

注意：我无法正确格式化代码，因此我选择使用粘贴箱，对于给您带来的不便，我们深表歉意。

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

#include "graph.h"

/* helper function prototypes */

// create a new vertex with a specific label
Vertex* new_vertex(const char* name);

// create a new w-weighted edge from vertex id u to vertex id v
Edge* new_edge(int u, int v, int w);

// destroy a vertex, including its label and all of its edges
void free_vertex(Vertex* vertex);


/* function definitions */

// create a new, empty graph, with space for n vertices
Graph* new_graph(int n) {
    Graph* graph = malloc(sizeof (*graph));
    assert(graph);

    graph->n = 0;
    graph->maxn = n;

    graph->vertices = malloc(n * sizeof (Vertex*));
    assert(graph->vertices);

    return graph;
}

// create a new vertex with a specific label
Vertex* new_vertex(const char* label) {
    assert(label);

    Vertex* vertex = malloc(sizeof (*vertex));
    assert(vertex);

    // make sure to copy the label across
    vertex->label = malloc((1 + strlen(label)) * sizeof (char));
    assert(vertex->label);
    strcpy(vertex->label, label);

    vertex->first_edge = NULL;

    return vertex;
}

// create a new w-weighted edge from vertex id u to vertex id v
Edge* new_edge(int u, int v, int w) {
    Edge* edge = malloc(sizeof (*edge));
    assert(edge);

    edge->u = u;
    edge->v = v;
    edge->weight = w;

    edge->next_edge = NULL;

    return edge;
}

// destroy a graph, its vertices, and their edges
void free_graph(Graph* graph) {
    if (graph) {
        int i;
        for (i = 0; i < graph->n; i++) {
            free_vertex(graph->vertices[i]);
        }

        free(graph->vertices);
        free(graph);    
    }
}

// destroy a vertex, including its label and all of its edges
void free_vertex(Vertex* vertex) {
    if (vertex) {
        while (vertex->first_edge) {
            Edge* edge = vertex->first_edge;
            vertex->first_edge = vertex->first_edge->next_edge;
            free(edge);
        }
        free(vertex->label);
        free(vertex);   
    }
}

// add a new vertex with label 'name' to a graph
void graph_add_vertex(Graph* graph, const char* name) {
    if (graph->n < graph->maxn) {
        graph->vertices[graph->n] = new_vertex(name);   
        graph->n++;
    } else {
        fprintf(stderr, "hey! adding new vertex to full graph\n");
    }
}

// add an undirected edge between u and v with weight w to graph
void graph_add_u_edge(Graph* graph, int u, int v, int w) {
    // an undirected edge is just two directed edges
    graph_add_d_edge(graph, u, v, w);
    graph_add_d_edge(graph, v, u, w);
}

// add a directed edge from u to v with weight w to a graph
void graph_add_d_edge(Graph* graph, int u, int v, int w) {
    if(u < graph->n && u >= 0 && v < graph->n && v >= 0) {
        Edge* edge = new_edge(u, v, w);
        edge->next_edge = graph->vertices[u]->first_edge;
        graph->vertices[u]->first_edge = edge;
    } else {
        fprintf(stderr, "hey! adding edge between non-existant vertices\n");
    }
}

graph.h

#ifndef GRAPH_H
#define GRAPH_H

typedef struct graph Graph;
typedef struct vertex Vertex;
typedef struct edge Edge;

// a graph knows its order (number of vertices) and an array of pointers to
// those vertices.
// these values can be used, but should not be *modified* outside of graph.c. 
// they are read-only!
struct graph {
    int n, maxn;
    Vertex** vertices;
};

// a vertex has a label and a pointer to the first edge in its adjacency list.
// these values can be used, but should not be *modified* outside of graph.c. 
// they are read-only!
struct vertex {
    char* label;
    Edge* first_edge;
};

// an edge knows the IDs of its two incident vertices; from u, to v
// each edge also knows its weight, and points to the next edge in a list of
// edges from the same vertex (or to NULL if it's the last edge in the list).
// these values can be used, but should not be *modified* outside of graph.c. 
// they are read-only!
struct edge {
    int u, v;
    int weight;
    Edge* next_edge;
};

// create a new, empty graph, with space for a maximum of n vertices
Graph* new_graph(int n);

// destroy a graph, its vertices, and their edges
void free_graph(Graph* graph);


// add a new vertex with label 'name' to a graph
void graph_add_vertex(Graph* graph, const char* name);

// add an undirected edge between u and v with weight w to graph
void graph_add_u_edge(Graph* graph, int u, int v, int w);

// add a directed edge from u to v with weight w to a graph
void graph_add_d_edge(Graph* graph, int u, int v, int w);

#endif

Answer 1

您的 graph 是指向 Graph 对象的指针。该对象具有成员 vertices，一个指向 Vertex 对象的指针数组。因此，顶点位于 graph->vertices，顶点 #0 位于 graph->vertices[0].

每个顶点都有一个成员first_edge，它是指向其第一条边的指针。因此，顶点 #0 的第一条边为 graph->vertices[0]->first_edge，其权重为 graph->vertices[0]->first_edge->weight。

邻接表中的下一条边是第一条边的 next_edge（例如，graph->vertices[0]->first_edge->next_edge）。要找到所有边，您应该使用 for 循环处理列表，从 graph->vertices[0]->first_edge 开始并继续到 next_edge，直到 next_edge 为 0。

for(Edge *current = graph->vertices[0]->first_edge; 
    current;
    current = current->next_edge) {
    do_something_with(current);
}

希望对您有所帮助。

如何访问和循环访问邻接表？

How to access and loop through an adjacency list?

c

traversal

adjacency-list