Graph Operations

Graph Operations

1. Graph creation using adjacency matrix

Creation of graph using adjacency matrix is quite simple task. The adjacency matrix is nothing but a two dimensional array. The algorithm for creation of graph using adjacency matrix will be as follows:

1. Declare an array of M[size] [size] which will store the graph.

2. Enter how many nodes you want in a graph.

3. Enter the edges of the graph by two vertices each, say V1, V; indicates some edge.

4. If the graph is directed set M[i][j]M[j][i]=1 as well.1. If graph is undirected set M[i][j]= 1 and

5. When all the edges for the desired graph is entered print the graph M[i][j].

void create()

{

int v1, v2

char ans='y';

printf("\n\t\t This is a Program To Create a Graph");

printf("\n\t\t The Display Is In Breadth First Manner");

printf("\nEnter no. of nodes");

scanf("%d",&n);

for (v1 = 0; v1 < n; v1++)

for (v2 = 0; v2 < n; v2++)

g[v1][v2] = FALSE;

printf("\nEnter the vertices no. starting from 0");

do

{

printf("\nEnter the vertices v1 & v2");

scanf("%d %d", &v1, &v2);

if (v1 >= n || v2 >= n)

printf("Invalid Vertex Value\n");

else

{

g[v1][v2]=TRUE;

g[v2][v1] = TRUE;

}

printf("\n\nAdd more edges??(y/n)");

ans=getche();

} while(ans=='y');

}

2. Graph creation using adjacency list

1. Declare node structure for creating adjacency list.

2.Initialize an array of nodes. This array will act as head nodes. Say "*head [10]'. The index of head [ ] will be the starting vertex.

3. The create function will create the adjacency list for given graph G as follows -

void create()

{

int V1, V2;

char ans='y';

for (V1= 0; V1 < MAX; V1++)

head[V1] = NULL;

do

{

printf("\nEnter the Edge of a graph \n");

scanf("%d %d", &V1,&V2);

if (V1>= MAX || V2 >= MAX)

printf("\nInvalid Vertex Value\n");

else

InsertEdge(V1, V2);

printf("\n\nAdd More nodes??");

ans=getche();

}while(ans=='y');

}

void add(int Hnode, int Vnum)

{

node *New, *first;

New = (node *)malloc(sizeof(node ) );

if (New == NULL)

printf("\n Memory can not be allocated\n");

New-> vertex = Vnum;

New->next = NULL;

first =head[Hnode];

if (first == NULL)

head[Hnode]=New;

else

{

while (first -> next != NULL)

first=first->next;

first->next = New;

}

New= (node *)malloc(sizeof(node ) );

if (New ==NULL)

printf("\n Memory Can not be allocated\n");

New-> vertex = Hnode;

New->next = NULL;

first = head[Vnum];

if (first == NULL)

head[Vnum] New;

else

{

while (first -> next != NULL)

first = first->next;

first->next = New;

}

}

3. Vertex Insertion

The vertex can be inserted in a graph by adding name of new vertex and name of the existing vertex to which it is attached.

For example:

Consider a graph G given below

4. Vertex Deletion

When particular vertex is deleted then all the edges associated with it gets deleted. All these edges are actually attached to neighbouring vertices. Hence while deleting some particular vertex, ask for the names of neighbouring vertices.

The neighbouring vertices are V₁, V₂, V₃.

Set

G[V₄][V₁] = G[V₁][V₄]= 0

G[V₄][V₂] = G[V₂][V₄] = 0

G[V₄][V₃] = G[V₃][V₄] = 0

Thus vertex V₄ gets deleted.

5. Find Vertex

For finding out the desired vertex we need to scan the complete graph. If vertex is present, then we will display its adjacent or neighbouring vertices.

For example

If we search for vertex V₄ then the vertices V₁, V₂ and V₃ are neighbouring vertices.

If the given vertex is not present in the graph then there will not be the neighbouring vertices. Hence we can simply display a message - "vertex not found".

6. Edge Addition

We can insert an edge in the graph. The edge is always represented by two vertices. Following are the steps to be carried out for adding an edge in the existing graph.

Step 1: Enter the name of new edge by specifying two vertices, say V₁, V₂

Step 2: Set G[V₁][V₂]= G [V₂ ][V₁]= 1

7. Edge Deletion

Deletion of any desired edge is the simplest operation. Following are the steps to be followed for deletion of an edge.

Step 1: Specify the name of an edge by two vertices say V1 and V2.

Step 2: Set G[V₁] [V₂]= G[V₂] [V₁]=0.

Step 3: Display the message that the edge is deleted.

For example:

If we want to delete an edge V2 - V3 then