Graph implementation C++

Below is a implementation of Graph Data Structure in C++ as Adjacency List.

I have used STL vector for representation of vertices and STL pair for denoting edge and destination vertex.

#include <iostream>
#include <vector>
#include <map>
#include <string>

using namespace std;

struct vertex {
    typedef pair<int, vertex*> ve;
    vector<ve> adj; //cost of edge, destination vertex
    string name;
    vertex(string s) : name(s) {}
};

class graph
{
public:
    typedef map<string, vertex *> vmap;
    vmap work;
    void addvertex(const string&);
    void addedge(const string& from, const string& to, double cost);
};

void graph::addvertex(const string &name)
{
    vmap::iterator itr = work.find(name);
    if (itr == work.end())
    {
        vertex *v;
        v = new vertex(name);
        work[name] = v;
        return;
    }
    cout << "\nVertex already exists!";
}

void graph::addedge(const string& from, const string& to, double cost)
{
    vertex *f = (work.find(from)->second);
    vertex *t = (work.find(to)->second);
    pair<int, vertex *> edge = make_pair(cost, t);
    f->adj.push_back(edge);
}

While all of the solutions do provide an implementation of graphs, they are also all very verbose. They are simply not elegant.

Instead of inventing your own graph class all you really need is a way to tell that one point is connected to another -- for that, std::map and std::unordered_map work perfectly fine. Simply, define a graph as a map between nodes and lists of edges. If you don't need extra data on the edge, a list of end nodes will do just fine.

Thus a succinct graph in C++, could be implemented like so:

using graph = std::map<int, std::vector<int>>;

Or, if you need additional data,

struct edge {
    int nodes[2];
    float cost; // add more if you need it
};

using graph = std::map<int, std::vector<edge>>;

Now your graph structure will plug nicely into the rest of the language and you don't have to remember any new clunky interface -- the old clunky interface will do just fine.

No benchmarks, but I have a feeling this will also outperform the other suggestions here.

NB: the ints are not indices -- they are identifiers.

The most common representations are probably these two:

• Adjacency list

• Adjacency matrix

Of these two the adjacency matrix is the simplest, as long as you don't mind having a (possibly huge) n * n array, where n is the number of vertices. Depending on the base type of the array, you can even store edge weights for use in e.g. shortest path discovery algorithms.

I prefer using an adjacency list of Indices ( not pointers )

typedef std::vector< Vertex > Vertices;
typedef std::set <int> Neighbours;


struct Vertex {
private:
   int data;
public:
   Neighbours neighbours;

   Vertex( int d ): data(d) {}
   Vertex( ): data(-1) {}

   bool operator<( const Vertex& ref ) const {
      return ( ref.data < data );
   }
   bool operator==( const Vertex& ref ) const {
      return ( ref.data == data );
   }
};

class Graph
{
private :
   Vertices vertices;
}

void Graph::addEdgeIndices ( int index1, int index2 ) {
  vertices[ index1 ].neighbours.insert( index2 );
}


Vertices::iterator Graph::findVertexIndex( int val, bool& res )
{
   std::vector<Vertex>::iterator it;
   Vertex v(val);
   it = std::find( vertices.begin(), vertices.end(), v );
   if (it != vertices.end()){
        res = true;
       return it;
   } else {
       res = false;
       return vertices.end();
   }
}

void Graph::addEdge ( int n1, int n2 ) {

   bool foundNet1 = false, foundNet2 = false;
   Vertices::iterator vit1 = findVertexIndex( n1, foundNet1 );
   int node1Index = -1, node2Index = -1;
   if ( !foundNet1 ) {
      Vertex v1( n1 );
      vertices.push_back( v1 );
      node1Index = vertices.size() - 1;
   } else {
      node1Index = vit1 - vertices.begin();
   }
   Vertices::iterator vit2 = findVertexIndex( n2, foundNet2);
   if ( !foundNet2 ) {
      Vertex v2( n2 );
      vertices.push_back( v2 );
      node2Index = vertices.size() - 1;
   } else {
      node2Index = vit2 - vertices.begin();
   }

   assert( ( node1Index > -1 ) && ( node1Index <  vertices.size()));
   assert( ( node2Index > -1 ) && ( node2Index <  vertices.size()));

   addEdgeIndices( node1Index, node2Index );
}

There can be an even simpler representation assuming that one has to only test graph algorithms not use them(graph) else where. This can be as a map from vertices to their adjacency lists as shown below :-

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

/* implement the graph as a map from the integer index as a key to the   adjacency list
 * of the graph implemented as a vector being the value of each individual key. The
 * program will be given a matrix of numbers, the first element of each row will
 * represent the head of the adjacency list and the rest of the elements will be the
 * list of that element in the graph.
*/

typedef map<int, vector<int> > graphType;

int main(){

graphType graph;
int vertices = 0;

cout << "Please enter the number of vertices in the graph :- " << endl;
cin >> vertices;
if(vertices <= 0){
    cout << "The number of vertices in the graph can't be less than or equal to 0." << endl;
    exit(0);
}

cout << "Please enter the elements of the graph, as an adjacency list, one row after another. " << endl;
for(int i = 0; i <= vertices; i++){

    vector<int> adjList;                    //the vector corresponding to the adjacency list of each vertex

    int key = -1, listValue = -1;
    string listString;
    getline(cin, listString);
    if(i != 0){
        istringstream iss(listString);
        iss >> key;
        iss >> listValue;
        if(listValue != -1){
            adjList.push_back(listValue);
            for(; iss >> listValue; ){
                adjList.push_back(listValue);
            }
            graph.insert(graphType::value_type(key, adjList));
        }
        else
            graph.insert(graphType::value_type(key, adjList));
    }
}

//print the elements of the graph
cout << "The graph that you entered :- " << endl;
for(graphType::const_iterator iterator = graph.begin(); iterator != graph.end(); ++iterator){
    cout << "Key : " << iterator->first << ", values : ";

    vector<int>::const_iterator vectBegIter = iterator->second.begin();
    vector<int>::const_iterator vectEndIter = iterator->second.end();
    for(; vectBegIter != vectEndIter; ++vectBegIter){
        cout << *(vectBegIter) << ", ";
    }
    cout << endl;
}
}

Here is a basic implementation of a graph. Note: I use vertex which is chained to next vertex. And each vertex has a list pointing to adjacent nodes.

#include <iostream>
using namespace std;


// 1 ->2 
// 1->4
// 2 ->3
// 4->3
// 4 -> 5
// Adjacency list
// 1->2->3-null
// 2->3->null
//4->5->null;

// Structure of a vertex
struct vertex {
   int i;
   struct node *list;
   struct vertex *next;
};
typedef struct vertex * VPTR;

// Struct of adjacency list
struct node {
    struct vertex * n;
    struct node *next;
};

typedef struct node * NODEPTR;

class Graph {
    public:
        // list of nodes chained together
        VPTR V;
        Graph() {
            V = NULL;
        }
        void addEdge(int, int);
        VPTR  addVertex(int);
        VPTR existVertex(int i);
        void listVertex();
};

// If vertex exist, it returns its pointer else returns NULL
VPTR Graph::existVertex(int i) {
    VPTR temp  = V;
    while(temp != NULL) {
        if(temp->i == i) {
            return temp;
        }
        temp = temp->next;
    }
   return NULL;
}
// Add a new vertex to the end of the vertex list
VPTR Graph::addVertex(int i) {
    VPTR temp = new(struct vertex);
    temp->list = NULL;
    temp->i = i;
    temp->next = NULL;

    VPTR *curr = &V;
    while(*curr) {
        curr = &(*curr)->next;
    }
    *curr = temp;
    return temp;
}

// Add a node from vertex i to j. 
// first check if i and j exists. If not first add the vertex
// and then add entry of j into adjacency list of i
void Graph::addEdge(int i, int j) {

    VPTR v_i = existVertex(i);   
    VPTR v_j = existVertex(j);   
    if(v_i == NULL) {
        v_i = addVertex(i);
    }
    if(v_j == NULL) {
        v_j = addVertex(j);
    }

    NODEPTR *temp = &(v_i->list);
    while(*temp) {
        temp = &(*temp)->next;
    }
    *temp = new(struct node);
    (*temp)->n = v_j;
    (*temp)->next = NULL;
}
// List all the vertex.
void Graph::listVertex() {
    VPTR temp = V;
    while(temp) {
        cout <<temp->i <<" ";
        temp = temp->next;
    }
    cout <<"\n";

}

// Client program
int main() {
    Graph G;
    G.addEdge(1, 2);
    G.listVertex();

}

With the above code, you can expand to do DFS/BFS etc.

Overall, this code is clear, functional, and follows good C++ practices R

#include <vector>
#include <stdexcept>
#include <iostream>
#include <queue>
using namespace std;

class Graph{
    int V; //NNo.of Vertices
    vector<vector<int>> adjList; //Adjacency Lists

    // Utility for recursive DFS
    void DFSUtil(int u, vector<bool>& visited) const{
        visited[u] = true;
        cout << u << " ";
        for(int v : adjList[u]){
            if(!visited[v]){ //if not visited
                DFSUtil(v, visited);
            }
        }
    }

public:
    //Construct a grpah with V vertices(0..V-1)
    explicit Graph(int vertices) : V(vertices), adjList(vertices){}

    // Add an edge u–v. If directed==false, also adds v–u.
    void addEdge(int u, int v, bool directed = false){
        if(u < 0 || u>= V || v < 0 || v >= V){
            throw out_of_range("Vertex out of Range");
        }
        adjList[u].push_back(v);
        if(!directed){ //if not directed
            adjList[v].push_back(u);
        }
    }

    //Return the neightbours of vertex u
    const vector<int>& getNeighbours(int u) const{
        if(u < 0 || u >= V){
            throw out_of_range("Vertex out of Range");
        }
        return adjList[u];
    }

    //Print the adjacancy list of each vertex
    void printGraph() const{
        for(int u = 0; u < V; u++){
            cout << u << " Vertex: ";
            for(int v : adjList[u]){
                cout << v <<  " ";
            }
            cout << endl;
        }

    }

    // Depth-First Search from start vertex
    void DFS(int start) const{
        if (start < 0 || start >= V){
            throw out_of_range("Star vertex out of range");
        }
        vector<bool> visited(V, false); //{false, false, false,...}
        cout << "DFS starting at " << start << ": ";
        DFSUtil(start, visited);
        cout << endl;
    }

    /*void DFSIterative(int start) const {
    vector<bool> visited(V, false);
    stack<int> st;
    st.push(start);
    cout << "DFS (iterative) starting at " << start << ": ";
    while (!st.empty()) {
        int u = st.top(); st.pop();
        if (visited[u]) continue;
        visited[u] = true;
        cout << u << " ";
        // Push neighbors in reverse order if you want the same visitation order
        for (auto it = adjList[u].rbegin(); it != adjList[u].rend(); ++it)
            if (!visited[*it])
                st.push(*it);
    }
    cout << "\n";
}*/

    //Breadth-First Search from start vertex
    void BFS(int start) const{
        if(start < 0  || start >= V){
            throw out_of_range("Start vertex out of range");
        }
        vector<bool> visited(V, false);
        queue<int> q;

        visited[start] = true;
        q.push(start);
        cout << "BFS is startting at " << start << ": ";

        while(!q.empty()){ //not empty
            int u = q.front(); //front in the queue
            q.pop();
            cout << u << " ";
            
            for(int v : adjList[u]){
                if(!visited[v]){ //if not visited
                    visited[v] = true;
                    q.push(v); //Push every neighbour to the queue 
                }
            }
        }
        cout << endl;
    }
};

int main(){
    Graph g(5); //Creating a grpah with 5 vertices

    //Add some undirected edges
    g.addEdge(0,1);
    g.addEdge(0,4);
    g.addEdge(1,3);
    g.addEdge(1,2);
    g.addEdge(3,4);

    //Print the adjacancy List
    cout << "Graph Adjacancy Lists: \n";
    g.printGraph();

    cout << "Neighbours of vertex 1: \n";
    for(int v : g.getNeighbours(1)){
        cout << v << " ";
    }
    cout << "\n\n";

    //Perform DFS
    g.DFS(1);

    //Perform BFS
    g.BFS(1);
    
    return 0;
}

MST with Prim's Algorithm R

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <limits>
using namespace std;

class Graph{
    int V;
    vector<vector<pair<int,int>>> adjList; //For example, an edge 0 → 1 of weight 10
                                           //And an edge 0 → 2 of weight 20:
                                           //0: (1, w=10) (2, w=20)
                                           
public: 
    explicit Graph(int vertices) : V(vertices), adjList(vertices){}

    //weighted edge
    void addEdge(int u, int v, int w, bool directed = false) {
        // 1) validate
        if (u < 0 || u >= V || v < 0 || v >= V)
            throw out_of_range("Vertex out of range");
    
        // 2) add the “forward” edge u→v
        adjList[u].emplace_back(v, w);
    
        // 3) if undirected, add the “back” edge v→u
        if (!directed)
            adjList[v].emplace_back(u, w);
    }

    //Print the adjacancy list of each vertex
    void printGraph() const {
        for (int u = 0; u < V; ++u) {
            cout << u << ": ";
            for (auto [v, w] : adjList[u])
                cout << "(" << v << "," << w << ") ";
            cout << "\n";
        }
    }

    //Prim's Algorithm for MST
    void primMST(int start = 0) const{
        using T = tuple<int,int,int>;
        priority_queue<T, vector<T>, greater<T>> pq; //Ordered by the weight assending order
        vector<bool> inMST(V, false); //Tracks which vertices are already in the MST.
        vector<int> key(V, numeric_limits<int>::max());
        vector<int> parent(V, -1);

        key[start] = 0;
        pq.emplace(0,start,-1);

        int totalWeight = 0;
        cout << "Edges in MST: \n";
        while(!pq.empty()){
            auto[w, u, p] = pq.top();
            pq.pop();
            
            if(inMST[u]){
                continue;
            }
            inMST[u] = true;
            parent[u] = p;
            totalWeight += w;
            if(p != -1){
                cout << " - " << "(w = " << w << " ) \n";
            }

            for(auto[v,wt] : adjList[u]){
                if(!inMST[v] && wt < key[v]){
                    key[v] = wt;
                    pq.emplace(wt, v, u);
                }
            }
        }
        cout << "Total MST weight = " << totalWeight << endl;
    }
};

int main(){
    Graph g(6); //no.of Vertices
    
    //addEdge(u, v, weight)
    g.addEdge(0,1,3);
    g.addEdge(0,5,1);
    g.addEdge(5,4,4);
    g.addEdge(5,2,5);
    g.addEdge(1,2,2);
    g.addEdge(1,3,1);
    g.addEdge(1,4,10);
    g.addEdge(4,3,5);
    g.addEdge(3,2,3);

    cout << "Weighted Graph \n";
    g.printGraph();
    cout << endl;

    g.primMST(0); // Start from vertex 0
    return 0;
}