如何訪問並循環訪問鄰接列表？

Question

這裏是我的鄰接表的實現，用於形成一個圖形。我不知道如何訪問這個列表並通過它循環來實現一些目標（例如DFS搜索）。

我試圖做類似graph[i][j]，但編譯器會說這是一個錯誤

下標值既不是數組，也不指針

我在這裏想這個圖僅僅是一個指針指向另一個名單。

我該怎麼辦？

注：我無法正確格式化代碼，因此我選擇使用粘貼bin，對於造成不便，敬請諒解。

graph.c

#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對象。該對象具有成員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); 
} 

希望它能幫助。