# Graph Representation using Linked List in C++

«

This is a C++ program to represent graph using linked list.

Problem Description

1. This algorithm represents a graph using linked list.
2. The time complexity of this algorithm is O(e).

Problem Solution

1. This algorithm takes the input of the number of vertex and edges.
2. Take the input of connected vertex pairs.
4. Exit.

Program/Source Code

C++ program to represent graph using linked list.
This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

```#include<iostream>

using namespace std;

// A structure to represent a node in the adjacency list.
struct node
{
int data;
};

// A structure to represent list of vertexes connected to the given vertex.
struct vertexlist
{
};

// A structure to maintain the graph vertexes and its connections to other vertexes.
struct Graph
{
int v;
struct vertexlist *vl;
};

// A function to declare the graph according to the number of vertex.
struct Graph* CreateGraph(int n)
{
int i;
struct Graph *vlist = new Graph;
vlist->v = n;

// declare a list for n vertex.
vlist->vl = new vertexlist[n+1];

// Assign the head to NULL.
for(i = 0; i < n+1; i++)
{
}

return vlist;
}

// A function to create a new data node.
struct node* NewNode(int value)
{
struct node *newnode = new node;
newnode->data = value;

return newnode;
}

// A  function to add the edge into the undirected graph.
void InsertNode(Graph *G, int v1, int v2)
{
node *newnode1 = NewNode(v1);
node *newnode2 = NewNode(v2);
node *temp = new node;
// Since it is undirected graph, count each edge as two connection.
// Connection 1, v2 to v1.
{
// If the head is null insert the node to the head.
}
else
{
// Otherwise, add the node at the beginning.
}
// Connection 2, v1 to v2.
{
// If the head is null insert the node to the head.
}
else
{
// Otherwise, add the node at the beginning.
}
}

int main()
{
int i, v, e;

// Take the input of the number of vertex and edges the graph have.
cout<<"Enter the number of vertexes of the graph: ";
cin>>v;
struct Graph *G = CreateGraph(v);
cout<<"\nEnter the number of edges of the graph: ";
cin>>e;
int edge[e];

// Take the input of the adjacent vertex pairs of the given graph.
for(i = 0; i < e; i++)
{
cout<<"\nEnter the vertex pair for edge "<<i+1;
cout<<"\nV(1): ";
cin>>edge[i];
cout<<"V(2): ";
cin>>edge[i];

InsertNode(G, edge[i], edge[i]);
}

// Print the incidence list representation of the graph.
cout<<"\n\nThe incidence list representation for the given graph: ";
for(i = 0; i < v; i++)
{
cout<<"\n\tV("<<i+1<<") -> {  ";
{
}
cout<<"}";
}
}```
Program Explanation

1. Construct a structure ‘node’ with data and link to the next node.
2. Construct a structure ‘vertexlist’ which contains list of nodes.
3. Construct a structure ‘graph’ which contain list of ‘vertexlist’.
4. Now in the main, take the input of the number of vertex ‘v’ and edges ‘e’.
5. Declare Graph object ‘G’.
6. Allocate memory to ‘G’ using CreateGraph(), which will Assign memory to ‘v’ objects of ‘vertexlist’.
7. Take the input of ‘e’ pairs of connected vertex and insert the nodes in the graph using InsertNode().
8. In the InsertNode(), If the head is NULL assign newnode to it.
9. Otherwise, add the new node at the beginning of the linked list.
10. Exit.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Runtime Test Cases
```Case 1:
Enter the number of vertexes of the graph: 5

Enter the number of edges of the graph: 8

Enter the vertex pair for edge 1
V(1): 1
V(2): 3

Enter the vertex pair for edge 2
V(1): 1
V(2): 4

Enter the vertex pair for edge 3
V(1): 1
V(2): 5

Enter the vertex pair for edge 4
V(1): 2
V(2): 3

Enter the vertex pair for edge 5
V(1): 2
V(2): 5

Enter the vertex pair for edge 6
V(1): 3
V(2): 4

Enter the vertex pair for edge 7
V(1): 3
V(2): 5

Enter the vertex pair for edge 8
V(1): 4
V(2): 5

The incidence list representation for the given graph:
V(1) -> {  5  4  3  }
V(2) -> {  5  3  }
V(3) -> {  5  4  2  1  }
V(4) -> {  5  3  1  }
V(5) -> {  4  3  2  1  }

Case 2:
Enter the number of vertexes of the graph: 4

Enter the number of edges of the graph: 4

Enter the vertex pair for edge 1
V(1): 1
V(2): 3

Enter the vertex pair for edge 2
V(1): 1
V(2): 4

Enter the vertex pair for edge 3
V(1): 2
V(2): 4

Enter the vertex pair for edge 4
V(1): 3
V(2): 4

The incidence list representation for the given graph:
V(1) -> {  4  3  }
V(2) -> {  4  }
V(3) -> {  4  1  }
V(4) -> {  3  2  1  }```

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms. 