隣接リストにアクセスしてループする方法は？

Question

グラフを作成するために使用される私の隣接リストの実装です。私はどのようにこのリストにアクセスし、何らかの目標（DFS検索など）を達成するためにそれをループする方法は知らない。

私はgraph[i][j]ような何かをしようとしたが、コンパイラが、それは誤り

添字値が配列でもポインタ

でもないです、私はここにグラフが単に別のを指すポインタである数えると言うでしょうリスト。

どうすればよいですか？

注：コードを正しくフォーマットできなかったため、私はペーストビンを使用することを選択しました。ご迷惑をおかけして申し訳ありません。

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オブジェクトへのポインタです。そのオブジェクトには、Vertexオブジェクトへのポインタの配列であるメンバーverticesがあります。したがって、頂点はgraph->verticesにあり、頂点＃0はgraph->vertices[0]になります。

各頂点には、最初のエッジへのポインタであるfirst_edgeというメンバがあります。したがって、頂点＃0の第1のエッジは、graph->vertices[0]->first_edgeであり、その重みは、例えば、graph->vertices[0]->first_edge->weightである。

隣接リストの次のエッジは、最初のエッジのnext_edge（たとえば、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); 
} 

になるまで、graph->vertices[0]->first_edgeおよび継続からnext_edgeに開始、forループを使用して、リストを処理する必要があり、それがお役に立てば幸いです。