graph implementation c++ code example

Example 1: graph using djacency matrix c++

// Adjacency Matrix representation in C++

#include <iostream>
using namespace std;

class Graph {
   private:
  bool** adjMatrix;
  int numVertices;

   public:
  // Initialize the matrix to zero
  Graph(int numVertices) {
    this->numVertices = numVertices;
    adjMatrix = new bool*[numVertices];
    for (int i = 0; i < numVertices; i++) {
      adjMatrix[i] = new bool[numVertices];
      for (int j = 0; j < numVertices; j++)
        adjMatrix[i][j] = false;
    }
  }

  // Add edges
  void addEdge(int i, int j) {
    adjMatrix[i][j] = true;
    adjMatrix[j][i] = true;
  }

  // Remove edges
  void removeEdge(int i, int j) {
    adjMatrix[i][j] = false;
    adjMatrix[j][i] = false;
  }

  // Print the martix
  void toString() {
    for (int i = 0; i < numVertices; i++) {
      cout << i << " : ";
      for (int j = 0; j < numVertices; j++)
        cout << adjMatrix[i][j] << " ";
      cout << "\n";
    }
  }

  ~Graph() {
    for (int i = 0; i < numVertices; i++)
      delete[] adjMatrix[i];
    delete[] adjMatrix;
  }
};

int main() {
  Graph g(4);

  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 0);
  g.addEdge(2, 3);

  g.toString();
}

Example 2: graph c++

//Code by Soumyadeep Ghosh insta- @soumyadepp
//linked in :  https://www.linkedin.com/in/soumyadeep-ghosh-90a1951b6/
//Basic implementation of undirected graph using OOP

#include <bits/stdc++.h>

using namespace std;

//undirected graph
class graph
{
  vector<int>*adjacency_list; //array of vectors to store adjacency list
  int Vertices;
  public:
    //constructor
    graph(int n)
    {
      Vertices=n;
      adjacency_list=new vector<int>[Vertices]; //dynamic allocation
    }
  
    void add_edge(int,int);
    void display_graph();
};

int main()
{
  graph g1(5);  //graph of 5 vertices indices- 0 to 4
  //adding edges
  g1.add_edge(0,1); //connect node number 0 to node number 1
  g1.add_edge(1,2); //connect node number 1 to node number 2
  g1.add_edge(1,3); //connect node number 1 to node number 3
  g1.add_edge(2,4); //connect node number 2 to node number 4
  g1.add_edge(2,3); //connect node number 2 to node number 3
  //displaying the graph
  cout<<"The entered Graph is "<<endl;
  g1.display_graph();
  return 0;
}

//function definitions
void graph::add_edge( int u,int v )
   {
     if( u >= Vertices || v >= Vertices )
     {
       cout<<"Overflow"<<endl;
       return;
     }
     if( u<0 || v<0 )
     {
       cout<<"underflow"<<endl;
       return;
     }
     adjacency_list[u].push_back(v);
     adjacency_list[v].push_back(u);
   }
  void graph::display_graph()
   {
     for(int i=0;i<Vertices;i++)
     {
       cout<<"Adjacency list of vertex of vertex "<<i<<endl;
       for(auto it:adjacency_list[i]) //traverse through each list
       {
         cout<<it<<" ";
       }
       cout<<endl;
     }
   }
//thank you!

Example 3: Graph Adjacent Node in c++

#include <iostream>
using namespace std;

struct adjNode {
    int val, cost;
    adjNode* next;
};

struct graphEdge {
    int start_ver, end_ver, weight;
};
class DiaGraph{
   
    adjNode* getAdjListNode(int value, int weight, adjNode* head)   {
        adjNode* newNode = new adjNode;
        newNode->val = value;
        newNode->cost = weight;
         
        newNode->next = head; 
        return newNode;
    }
    int N;  
public:
    adjNode **head;          

    DiaGraph(graphEdge edges[], int n, int N)  {
     
        head = new adjNode*[N]();
        this->N = N;
       
        for (int i = 0; i < N; ++i)
            head[i] = nullptr;
      
        for (unsigned i = 0; i < n; i++)  {
            int start_ver = edges[i].start_ver;
            int end_ver = edges[i].end_ver;
            int weight = edges[i].weight;
       
            adjNode* newNode = getAdjListNode(end_ver, weight, head[start_ver]);
             
                  
            head[start_ver] = newNode;
             }
    }
   
     ~DiaGraph() {
    for (int i = 0; i < N; i++)
        delete[] head[i];
        delete[] head;
     }
};

void display_AdjList(adjNode* ptr, int i)
{
    while (ptr != nullptr) {
        cout << "(" << i << ", " << ptr->val
            << ", " << ptr->cost << ") ";
        ptr = ptr->next;
    }
    cout << endl;
}

int main()
{
    
    graphEdge edges[] = {
      
        {0,1,2},{0,2,4},{1,4,3},{2,3,2},{3,1,4},{4,3,3}
    };
    int N = 6;   
  
    int n = sizeof(edges)/sizeof(edges[0]);
   
    DiaGraph diagraph(edges, n, N);
  
    cout<<"Graph adjacency list "<<endl<<"(start_vertex, end_vertex, weight):"<<endl;
    for (int i = 0; i < N; i++)
    {
        
        display_AdjList(diagraph.head[i], i);
    }
    return 0;
}

Example 4: Oriented and unoriented graphs C++

#include <iostream>
using namespace std;
// stores adjacency list items
struct adjNode {
    int val, cost;
    adjNode* next;
};
// structure to store edges
struct graphEdge {
    int start_ver, end_ver, weight;
};
class DiaGraph{
    // insert new nodes into adjacency list from given graph
    adjNode* getAdjListNode(int value, int weight, adjNode* head)   {
        adjNode* newNode = new adjNode;
        newNode->val = value;
        newNode->cost = weight;
         
        newNode->next = head;   // point new node to current head
        return newNode;
    }
    int N;  // number of nodes in the graph
public:
    adjNode **head;                //adjacency list as array of pointers
    // Constructor
    DiaGraph(graphEdge edges[], int n, int N)  {
        // allocate new node
        head = new adjNode*[N]();
        this->N = N;
        // initialize head pointer for all vertices
        for (int i = 0; i < N; ++i)
            head[i] = nullptr;
        // construct directed graph by adding edges to it
        for (unsigned i = 0; i < n; i++)  {
            int start_ver = edges[i].start_ver;
            int end_ver = edges[i].end_ver;
            int weight = edges[i].weight;
            // insert in the beginning
            adjNode* newNode = getAdjListNode(end_ver, weight, head[start_ver]);
             
                        // point head pointer to new node
            head[start_ver] = newNode;
             }
    }
      // Destructor
     ~DiaGraph() {
    for (int i = 0; i < N; i++)
        delete[] head[i];
        delete[] head;
     }
};
// print all adjacent vertices of given vertex
void display_AdjList(adjNode* ptr, int i)
{
    while (ptr != nullptr) {
        cout << "(" << i << ", " << ptr->val
            << ", " << ptr->cost << ") ";
        ptr = ptr->next;
    }
    cout << endl;
}
// graph implementation
int main()
{
    // graph edges array.
    graphEdge edges[] = {
        // (x, y, w) -> edge from x to y with weight w
        {0,1,2},{0,2,4},{1,4,3},{2,3,2},{3,1,4},{4,3,3}
    };
    int N = 6;      // Number of vertices in the graph
    // calculate number of edges
    int n = sizeof(edges)/sizeof(edges[0]);
    // construct graph
    DiaGraph diagraph(edges, n, N);
    // print adjacency list representation of graph
    cout<<"Graph adjacency list "<<endl<<"(start_vertex, end_vertex, weight):"<<endl;
    for (int i = 0; i < N; i++)
    {
        // display adjacent vertices of vertex i
        display_AdjList(diagraph.head[i], i);
    }
    return 0;
}

Example 5: weighted graph c++

//code  by Soumyadeep Ghosh
//insta : @soumyadepp
//linked in: https://www.linkedin.com/in/soumyadeep-ghosh-90a1951b6/

#include <bits/stdc++.h>
using namespace std;

//undirected weighted graph and all functions
class WeightedGraph
{
  vector< pair<int,int> >*adjacency_list;
  int vertices;
  public:
  WeightedGraph(int n)
  {
    vertices=n;
    adjacency_list=new vector< pair<int,int> >[n];
  }
  void add_edge(int v1,int v2,int wt);
  void dfsHelper(int src,bool visited[]);
  void dfs(int src);
  void bfs(int src);
  int minDistance(vector<int>dist,bool visited[]);  
  void djisktra(int src);
  void display_graph();
};

int main()
{
  //graph of five vertices
  WeightedGraph wg1(5);
  //adding edges
  wg1.add_edge(0,1,10);
  wg1.add_edge(1,2,20);
  wg1.add_edge(2,3,30);
  wg1.add_edge(1,3,40);
  wg1.add_edge(2,4,100);
  wg1.add_edge(4,0,10);
  //displaying the graph
  wg1.display_graph();
  //dfs from vertex 0
  wg1.dfs(0);
  //bfs from vertex 0
  wg1.bfs(0);
  //djikstra
  for(int i=0;i<5;i++)
  {
    djikstra(i);
  }
  return 0;
}
//function definitions

void WeightedGraph::add_edge(int v1,int v2,int wt)
{
  /*push the other vertex into the adjacency list of the given vertex
  and vice versa. If it would have been a directed graph,
  only the first line would be enough
  */
  adjacency_list[v1].push_back(make_pair(v2,wt));
  adjacency_list[v2].push_back(make_pair(v1,wt));
}

void WeightedGraph::dfsHelper(int src,bool visited[])
{
  visited[src]=true;
  cout<<src<<" ";
  for(vector<int>::iterator it=adjacency_list.begin();i!=adjacency_list.end();it++)
  {
    if(!visited[it->first]);
      dfsHelper(it->first,visited);
  }
}
void WeightedGraph::dfs(int src)
{
  bool visited[vertices];
  for(int i=0;i<vertices;i++)
    visited[i]=false;
  dfsHelper(src,visited);
}
void WeightedGraph::bfs(int src)
{
  bool visited[vertices];
  for(int i=0;i<vertices;i++)
    visited[i]=false;
  cout<<src<<" ";
  visited[src]=true;
  queue<int>helper;
  helper.push(src);
  while(!helper.empty())
  {
    src=helper.front();
    for(vector<int>::iterator it=adjacency_list[src].begin();it!+adjacency_list[src].end();it++)
    {
      if(!visited[it->first])
      {
        visited[it->first]=true;
        cout<<it->first<<" ";
        helper.push(it->first);
      }
    }
    helper.pop();
  }
}

int WeightedGraph::minDistance(vector<int>dist,bool visited[])
  {
    int min=INT_MAX;
    int minIndex=INT_MAX;
    for(int i=0;i<N;i++)
    {
      if(!visited[i]&&dist[i]<=min)
      {
        min=dist[i];
        minIndex=i;
      }
    }
    return minIndex;
  }


void WeightedGraph::djikstra(int src)
  {
    vector<int>dist;
    bool visited[vertices];
    for(int i=0;i<vertices;i++)
    {
      dist.push_back(INT_MAX);
      visited[i]=false;
    }
    visited[src]=true;
    dist[src]=0;
    for(int i=0;i<vertices-1;i++)
    {
      int k=minDistance(dist,visited);
      visited[k]=true;
      for(int j=0;j<vertices;j++)
      {
        if(!visited[i]&&dist[i]!=INT_MAX&&adjacency_list[i][j].second+dist[i]<dist[j])
        {
          dist[j]=adjacency_list[i][j].second+dist[i];
        }
      }
    }
    for(int i=0;i<dist.size();i++)
      cout<<dist[i]<<" ";
    
    cout<<endl;
  }
void WeightedGraph::display_graph()
{
  int a,b;
  //first loop to traverse across vertices
  for(int i=0;i<vertices;i++)
  {
      cout<<"Adjacency list of vertex "<<i<<endl;
    //second loop to traverse across the adjacency list of some vertex i
    for(auto it=adjacency_list[i].begin();it!=adjacency_list[i].end();it++)
    {
      //set a as the vertex number and b as the weight
      a=it->first;
      b=it->second;
      cout<<"Vertex : "<<a<<" Weight : "<<b<<endl;
    }
    cout<<endl;
  }
}

//thank you!