fork(4) download
copy 
  1. #include<vector>
  2. #include<iostream>
  3. #include<cmath>
  4. #include<string>
  5. using namespace std;
  6.  
  7. /************LINKED LIST**********************************************/
  8. //Adjacency List Representation of the Graph
  9. class Node{
  10.     public:
  11.     int data;
  12.     Node* next;
  13.     Node(int x):data(x){next = NULL;}
  14.     void displayData(){
  15.         cout<<data;
  16.     }
  17. };
  18. class LinkList {
  19.     public:
  20.     Node* head;
  21.     int length;
  22.  
  23.     LinkList(){
  24.         head = NULL;
  25.     }
  26.     LinkList(int x){
  27.         head= new Node(x);       
  28.     }
  29.     LinkList(int x, int y){
  30.         head= new Node(x);   
  31.         length = y;
  32.     }
  33.     void insert_at_head(int x){
  34.         Node* new_node = new Node(x);       
  35.         new_node->next=head->next;
  36.         head->next=new_node;
  37.     }//end insertFirst
  38.  
  39.     void remove_at_head(){
  40.     }//end removeFirst
  41.  
  42.     void insert_at_tail(int x){
  43.         //parse to get to the end element
  44.         Node* parse = this->head;       
  45.         while(parse->next != NULL){           
  46.             parse=parse->next;//last node
  47.         }
  48.         Node* n;
  49.         n->data = x;   
  50.         n->next = NULL;
  51.         parse->next = n;       
  52.     }
  53.     int countNodes(){//count the number of nodes
  54.         int count=0;
  55.         Node* curr = head;
  56.         while(curr!=NULL){
  57.             curr=curr->next;
  58.             count++;
  59.         }
  60.         return count;
  61.     }
  62. };
  63.  
  64. class Graph{
  65. public:
  66.     int V;//number of vertices
  67.     LinkList* vertex_array;//linked list implementation of vertex array for dynamic allocation
  68.  
  69.     Graph(int v){//create Graph of v vertices
  70.  
  71.     this->V = v;
  72.      this->vertex_array = new LinkList[V];
  73.  
  74.     // Create an array of adjacency lists.  Size of array will be V
  75.    // LinkList graph->vertex_array[V] = new LinkList();//declaration
  76.     //allocate memory to each element of vertex_array
  77.     int i;
  78.     for (i = 0; i < V; ++i){
  79.         //graph->vertex_array[i] = new LinkList();
  80.        this->vertex_array[i].head = NULL;
  81.     }
  82.     }
  83.     void addEdge(int src, int dest);
  84.     void printGraph();
  85. };
  86.  
  87. // A utility function that creates a graph of V vertices
  88.  
  89. // Adds an edge to an undirected graph
  90. void Graph::addEdge(int src, int dest)
  91. {
  92.     // Add an edge from src to dest.  A new node is added to the adjacency
  93.     // list of src.  The node is added at the begining.. for efficiency
  94.     Node* newNode = new Node(dest);
  95.     newNode->next = this->vertex_array[src].head;
  96.     this->vertex_array[src].head = newNode;
  97.  
  98.     // Since graph is undirected, add an edge from dest to src also
  99.     newNode = new Node(src);
  100.     newNode->next = this->vertex_array[dest].head;
  101.     this->vertex_array[dest].head = newNode;
  102. }
  103.  
  104. // A utility function to print the adjacenncy list representation of graph
  105. void Graph::printGraph()
  106. {
  107.     int v;
  108.     for (v = 0; v < this->V; ++v)
  109.     {
  110.         Node* pCrawl = this->vertex_array[v].head;
  111.        cout<<"\n Adjacency list of vertex "<<v<<"\n head";
  112.         while (pCrawl)
  113.         {
  114.             cout<<"->"<<pCrawl->data;
  115.             pCrawl = pCrawl->next;
  116.         }
  117.         cout<<"\n";
  118.     }
  119. }
  120.  
  121. int main(){
  122.  // create the graph given in above fugure
  123.     int V = 5;
  124.  
  125.     Graph* graph = new Graph(V);
  126.     graph->addEdge(0, 1);
  127.     graph->addEdge(0, 4);
  128.     graph->addEdge(1, 2);
  129.     graph->addEdge(1, 3);
  130.     graph->addEdge(1, 4);
  131.     graph->addEdge(2, 3);
  132.     graph->addEdge(3, 4);
  133.  
  134.     // print the adjacency list representation of the above graph
  135.     graph->printGraph();
  136.  
  137.     return 0;
  138. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 Adjacency list of vertex 0
 head->4->1

 Adjacency list of vertex 1
 head->4->3->2->0

 Adjacency list of vertex 2
 head->3->1

 Adjacency list of vertex 3
 head->4->2->1

 Adjacency list of vertex 4
 head->3->1->0
https://ideone.com/ih7CQl
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!