Graph implementation in C
Graph is a non-linear one which has vertices and edges. Vertices are the nodes and the edges are links which connect the nodes. General representation of G is represented by
G = (V,E)
Where, V represents by vertices and E represents by edges.
Let us implement the graph in two different ways as follows..
- 1.
Adjacency Matrix
- 2.
Adjacency List
1.Adjacency Matrix implementation of Graph:
This
method follows a two-dimensional Matrix to implement the graph. It creates a 2D
matrix to get the graph structure. It reads the edges from the user and assigns
the value. Finally displays the graph.
C Program:
#include <stdio.h>
#define V 4
void printIt(int adjM_graph[V][V]) {
for (int i = 0; i
< V; i++) {
for (int j =
0; j < V; j++) {
printf("%d ", adjM_graph[i][j]);
}
printf("\n");
}
}
int main() {
int
adjM_graph[V][V] = {0};
// To Add edges
values
adjM_graph[0][0] =
1;
adjM_graph[1][1] =
1;
adjM_graph[2][2] =
1;
adjM_graph[3][3] =
1;
printIt(adjM_graph);
return 0;
}
Output:
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
Next method is given as follows.
2.Adjacency List implementation
of Graph:
This
implementation deals with linked list. A linked list is created. Using the
linked list, a graph is formed.using a function add_edges(), the edges are
added. Finally, it displays the graph.
C Code:
#include <stdio.h>
#include <stdlib.h>
struct g_Node {
int g_vertex;
struct g_Node*
next;
};
struct Graph_l {
int nVertices;
struct g_Node**
aLists;
};
struct g_Node* createIt(int v) {
struct g_Node*
newNode = malloc(sizeof(struct g_Node));
newNode->g_vertex = v;
newNode->next =
NULL;
return newNode;
}
struct Graph_l* cGraph(int vertices) {
struct Graph_l*
graph = malloc(sizeof(struct Graph_l));
graph->nVertices = vertices;
graph->aLists =
malloc(vertices * sizeof(struct g_Node*));
for (int i = 0; i
< vertices; i++)
graph->aLists[i] = NULL;
return graph;
}
void add_Edge(struct Graph_l* graph, int src, int dest) {
struct g_Node*
newNode = createIt(dest);
newNode->next =
graph->aLists[src];
graph->aLists[src] = newNode;
}
void printIt(struct Graph_l* graph) {
for (int v = 0; v
< graph->nVertices; v++) {
struct g_Node*
temp = graph->aLists[v];
printf("Vertex %d:", v);
while (temp) {
printf(" %d ->", temp->g_vertex);
temp =
temp->next;
}
printf("
NULL\n");
}
}
int main() {
struct Graph_l*
graph = cGraph(5);
add_Edge(graph, 1,
1);
add_Edge(graph, 1,
2);
add_Edge(graph, 2,
3);
add_Edge(graph, 2,
4);
printIt(graph);
return 0;
}
Output:
Vertex 0: NULL
Vertex 1: 2 -> 1 -> NULL
Vertex 2: 4 -> 3 -> NULL
Vertex 3: NULL
Vertex 4: NULL
These are the two methods to implement graph (a non-linear
data structure) in C.Hope, this code is useful to you. Keep Coding!!!!
Comments
Post a Comment