Skip to content

Instantly share code, notes, and snippets.

@tahia-khan tahia-khan/graph.c
Created Nov 8, 2015

Embed
What would you like to do?
adjacency list implementation in c
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#define N 10
typedef struct {
int y;
int weight;
struct Edge *next; /* next in adj list */
} Edge;
typedef struct {
int x;
struct Edge *next;
} Vertex;
typedef struct {
Vertex *vertex[N];
int degree[N];
int nvertices;
int nedges;
bool directed;
} Graph;
void initialize_graph(Graph **g, bool directed) {
int i;
(*g)->nvertices = 0;
(*g)->nedges = 0;
(*g)->directed = directed;
for (i = 0; i < N ; i++) {
(*g)->degree[i]=0;
(*g)->vertex[i]=NULL;
}
}
void insert_edge(Vertex *v, Edge *e) {
e->next = v->next;
v->next = (struct Edge*) e;
}
void create_link(Graph **g, int x, int y, int weight, bool directed) {
Vertex *v;
Edge *e;
if (!(*g)->vertex[x]) {
v = malloc(sizeof(Vertex));
if (!v) return;
v->x = x;
(*g)->vertex[x] = v;
(*g)->nvertices+=1;
} else v = (*g)->vertex[x];
e = malloc(sizeof(Edge));
e->y = y;
e->weight = weight;
insert_edge(v, e);
if (!directed)
create_link(g, y, x, weight, true);
else
(*g)->nedges+=1;
}
void print_graph(Graph *g) {
int i;
Vertex *v;
Edge *e;
for (i=0; i<g->nvertices+1; i++) {
v = g->vertex[i];
if (v) {
printf("Vertex %d: ", v->x);
for (e = (Edge*) v->next; e; e = (Edge*) e->next)
printf(" %d(%d)", e->y, e->weight);
printf("\n");
}
}
}
/* 1-----2---3 */
/* | ___/| | */
/* |/ | | */
/* 5-----4---+ */
int main() {
Graph *g = malloc(sizeof(Graph));
initialize_graph(&g, false);
create_link(&g,1,2,1,false);
create_link(&g,1,5,1,false);
create_link(&g,2,5,1,false);
create_link(&g,2,4,1,false);
create_link(&g,2,3,1,false);
create_link(&g,3,4,1,false);
create_link(&g,4,5,1,false);
print_graph(g);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.