-
Notifications
You must be signed in to change notification settings - Fork 0
/
graph.h
96 lines (69 loc) · 1.83 KB
/
graph.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#ifndef __GRAPH_H_INCLUDED__ // if x.h hasn't been included yet...
#define __GRAPH_H_INCLUDED__
#include <stdio.h>
#include <stdlib.h>
#define R 100
#define C 100
struct node {
int dest;
int weight;
struct node * next;
};
struct adjList {
struct node * head;
};
struct graph {
int v;
struct adjList * array;
};
struct node * newAdjListNode( int dest, int weight ) {
struct node * new_node = ( struct node * ) malloc( sizeof( struct node) ); // make a new node
new_node -> dest = dest;
new_node -> next = NULL;
new_node -> weight = weight;
return new_node;
}
struct graph * make_graph ( int v ) {
struct graph * g = ( struct graph * ) malloc ( sizeof( struct graph ) ); // make a graph node.
g -> v = v;
g -> array = ( struct adjList * ) malloc ( v * sizeof ( struct adjList ) ); // make an array of adjList type nodes. This
int i;
for ( i = 0 ; i < v; i++ ) {
g -> array[i].head = NULL;
}
return g;
}
void addEdge ( struct graph * g, int src, int dest, int weight = 0) {
// edge from src to dest
//printf ("adding weight %d", weight);
struct node * n = newAdjListNode(dest, weight);
n -> next = g -> array[src].head;
g -> array[src].head = n;
/*
// edge from dest to src
n = newAdjListNode ( src );
n -> next = g -> array[dest].head;
g -> array[dest].head = n;
*/
}
void printGraph ( struct graph * g ) {
int v;
for ( v = 0; v < g -> v; v++ ) {
struct node * crawl = g -> array[v].head;
printf ( "Adjacent list for this vertex %d ---> ", v );
while ( crawl ) {
printf ( "%d (%d) ", crawl -> dest, crawl->weight);
crawl = crawl -> next ;
}
printf ( "\n" );
}
}
void freemem( struct graph * g ) {
int v;
for ( v = 0; v < g -> v; v++ ) {
struct node * crawl = g -> array[v].head;
free ( crawl );
}
free ( g );
}
#endif