Graph Representations in Computers
A graph has:
The two most common representations are:
1. Adjacency Matrix
-
A 2D array of size
-
If there is an edge between vertex and ,
-
If no edge → store 0 (or ∞ for weighted).
Example
Graph: Vertices = {A, B, C, D}
Edges = {(A,B), (A,C), (B,D), (C,D)}
👉 Adjacency Matrix:
| A | B | C | D |
|---|
A | 0 | 1 | 1 | 0 |
B | 1 | 0 | 0 | 1 |
C | 1 | 0 | 0 | 1 |
D | 0 | 1 | 1 | 0 |
Example 2:
Example 3:
Example 4:
Advantages
-
Easy to check if an edge exists → .
Constant time complexity for checking adjacency.
-
Simple and direct representation.
-
Works well for dense graphs.
Disadvantages
2. Adjacency List
Example (same graph)
Vertices = {A, B, C, D}
Edges = {(A,B), (A,C), (B,D), (C,D)}
👉 Adjacency List:
-
A → B, C
-
B → A, D
-
C → A, D
-
D → B, C
Example:
Advantages
Disadvantages
3. Incidence Matrix (less common)
-
A matrix of size |V| × |E|.
-
Rows → vertices, Columns → edges.
-
If vertex is incident on edge , entry = 1.
-
For directed graphs: use 1 for out-going and -1 for incoming.
For Weighted graphs the entries represent weight
For directed Graph we use 1 for outgoing and -1 for incoming.( some authors use alternate options)
✅ Simple C Program (Adjacency Matrix)
C program to:
Represent a graph using Adjacency Matrix.
Take input for the number of vertices and edges.
Print the adjacency matrix.
Compute the degree of vertices.
/* Graph representation using adjacency matrix and finding the degree */
#include <stdio.h>
int adj[50][50],n;
void read()
{ int ad;
printf("Enter the Number of vertices\n");
scanf("%d",&n);
// storing element from [1][1]
//// assuming the vertices are numbered v1 v2..vn and we will enter only the index 1,2...n
for(int i=0;i<n;i++)
{
printf("Enter the list of vertices adjacent to v%d -1 to stop\n",i);
while(1)
{
scanf("%d",&ad);
if(ad==-1) break;
adj[i][ad]=1;
}
}
}//end of read
void disp()
{
printf("Adjacency Matrix..\n");
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
printf("%5d",adj[i][j]);
printf("\n");
}
}
void calculateDegree() {
int i, j;
printf("Vertex\tDegree\n");
for (i = 0; i <n; i++) {
int degree = 0;
for (j = 0; j < n; j++) {
if (adj[i][j] == 1) {
degree++;
}
}
printf("v%d\tdegree=%d\n", i , degree);
}
}
int main()
{
read();
disp();
calculateDegree();
return 0;
}
Enter the list of vertices adjacent to v0 -1 to stop
1 4 -1
Enter the list of vertices adjacent to v1 -1 to stop
0 2 3 4 -1
Enter the list of vertices adjacent to v2 -1 to stop
1 3 -1
Enter the list of vertices adjacent to v3 -1 to stop
1 2 4 -1
Enter the list of vertices adjacent to v4 -1 to stop
0 1 3 -1
Adjacency Matrix..
0 1 0 0 1
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
1 1 0 1 0
Vertex Degree
v0 degree=2
v1 degree=4
v2 degree=2
v3 degree=3
v4 degree=3
✅ Simple C Program (Adjacency List)
#include <stdio.h>
#include <stdlib.h>
struct vertex
{
int data;
struct vertex *next;
}*adj[50],*tail[50],*temp=NULL;
int nv;
void read()
{ int adv;
printf("Enter the Number of vertices\n");
scanf("%d",&nv);
// storing element from [1][1]
//// assuming the vertices are numbered v1 v2..vn and we will enter only the index 1,2...n
for(int i=0;i<nv;i++)
{
printf("Enter the list of vertices adjacent to v%d -1 to stop\n",i);
adj[i]=NULL;tail[i]=NULL;
while(1)
{
scanf("%d",&adv);
if(adv==-1) break;
temp=(struct vertex *)malloc(sizeof(struct vertex));
temp->data=adv;
temp->next=NULL;
if(adj[i]==NULL) {adj[i]=temp;tail[i]=temp;} else { tail[i]->next=temp;tail[i]=temp;}
}
}
}//end of read
void disp()
{
printf("Adjacency List..\n");
for(int i=0;i<nv;i++)
{ temp=adj[i];
printf("V%d-->",i);
while(temp!=NULL)
{
printf("V%d--->",temp->data);
temp=temp->next;
}
printf("NULL\n");
}
}
int main()
{
read();
disp();
return 0;
}
Enter the Number of vertices
5
Enter the list of vertices adjacent to v0 -1 to stop
1 2 3 -1
Enter the list of vertices adjacent to v1 -1 to stop
0 3 4 -1
Enter the list of vertices adjacent to v2 -1 to stop
0 3 -1
Enter the list of vertices adjacent to v3 -1 to stop
0 1 2 4 -1
Enter the list of vertices adjacent to v4 -1 to stop
1 3 -1
Adjacency List..
V0-->V1--->V2--->V3--->NULL
V1-->V0--->V3--->V4--->NULL
V2-->V0--->V3--->NULL
V3-->V0--->V1--->V2--->V4--->NULL
V4-->V1--->V3--->NULL
✅ C Program: Incidence Matrix with In-degree & Out-degree
#include <stdio.h>
#define MAXV 10 // maximum number of vertices
#define MAXE 20 // maximum number of edges
int incidence[MAXV][MAXE];
int n, e; // number of vertices and edges
// Function to compute out-degree of a vertex
int outDegree(int v) {
int j, count = 0;
for (j = 0; j < e; j++) {
if (incidence[v][j] == -1) // tail of edge
count++;
}
return count;
}
// Function to compute in-degree of a vertex
int inDegree(int v) {
int j, count = 0;
for (j = 0; j < e; j++) {
if (incidence[v][j] == 1) // head of edge
count++;
}
return count;
}
int main() {
int i, j, u, v, vertex;
// Step 1: Input
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter number of edges: ");
scanf("%d", &e);
// Initialize incidence matrix with 0
for (i = 0; i < n; i++) {
for (j = 0; j < e; j++) {
incidence[i][j] = 0;
}
}
// Step 2: Read edges and fill incidence matrix
printf("Enter directed edges (u v) between 0 and %d:\n", n - 1);
for (j = 0; j < e; j++) {
scanf("%d%d", &u, &v);
incidence[u][j] = -1; // tail (outgoing)
incidence[v][j] = +1; // head (incoming)
}
// Step 3: Print incidence matrix
printf("\nIncidence Matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < e; j++) {
printf("%2d ", incidence[i][j]);
}
printf("\n");
}
// Step 4: Input vertex and compute degrees
printf("\nEnter vertex to compute degrees: ");
scanf("%d", &vertex);
printf("In-degree of %d = %d\n", vertex, inDegree(vertex));
printf("Out-degree of %d = %d\n", vertex, outDegree(vertex));
return 0;
}
Enter number of vertices: 4
Enter number of edges: 4
Enter directed edges (u v) between 0 and 3:
0 1
1 2
2 0
0 3
Incidence Matrix:
1 0 -1 1
-1 1 0 0
0 -1 1 0
0 0 0 -1
Enter vertex to compute degrees: 0
In-degree of 0 = 1
Out-degree of 0 = 2
Comments
Post a Comment