Concept
그래프의 인접리스트를 2차원 배열, 2차원 연결리스트, 또는 해시테이블과 연결리스트로 등으로 구현할 수 있음
Example
2차원 연결리스트의 구현의 경우
#include <stdio.h>
#include <stdlib.h>
typedef struct _vertex {
struct _vertex *next;
struct _vertex *adjacent;
int number;
} Vertex;
typedef struct _graph {
Vertex *head;
} Graph;
Vertex *newVertex() {
Vertex *vertex = (Vertex *) malloc(sizeof(Vertex));
vertex->number = -1;
vertex->next = NULL;
vertex->adjacent = NULL;
return vertex;
}
Graph *newGraph() {
Graph *graph = (Graph *) malloc(sizeof(Graph));
graph->head = NULL;
return graph;
}
void make(Graph *graph, int from, int to) {
Vertex *current = graph->head;
Vertex *prev;
while(current != NULL) {
if (current->number == from) break;
prev = current;
current = current->next;
}
if(!current) {
Vertex *vertex = newVertex();
vertex->number = from;
current = vertex;
}
if(!graph->head) graph->head = current;
else prev->next = current;
while(current->adjacent != NULL) {
current = current->adjacent;
}
Vertex *adjacent = newVertex();
adjacent->number = to;
current->adjacent = adjacent;
}
void print(Graph *graph) {
Vertex *current = graph->head;
while(current != NULL) {
printf("[%d] ", current->number);
Vertex *adjacent = current->adjacent;
while(adjacent != NULL) {
printf("%d ", adjacent->number);
adjacent = adjacent->adjacent;
}
current = current->next;
printf("\n");
}
}
int main() {
Graph *graph = newGraph();
make(graph, 1, 2);
make(graph, 2, 3);
make(graph, 2, 4);
make(graph, 4, 5);
print(graph);
return 0;
}