I've started to learn about graphs and how to represent them in code. Here is my attempt of making an adjacency list for an undirected graph. I'm looking for suggestions on how to improve it and what could've been done better.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

struct vertex {
int name=0;
set<vertex> edges;                                  

bool operator< (vertex const &rhs) const {       //needed for set
    return name<rhs.name;
}
bool operator== (vertex const &rhs) const {      //needed for find
    return name == rhs.name;
}

};

class graph {
private:

    std::vector<vertex> vertices;

public:
graph(int size = 0) { vertices.resize(size+1); };

int V;

void addVertex(vertex a) {
    vertices[a.name]=a;
}

void addEdge(int a, int b) {
    vertex f,s; 
    f.name = a;
    s.name = b;

    if(!exists(f, vertices))                //checks if vertex was already given
    addVertex(f);                       

    if (!exists(s, vertices))
    addVertex(s);

    vertices[a].edges.emplace(s);
    vertices[b].edges.emplace(f);
}
void printGraph() {
    for (int i = 1; i<vertices.size(); i++) {

            cout << vertices[i].name << " -> ";
            for (auto it2 : vertices[i].edges) {
                cout << it2.name << " -> ";
            }

            cout << endl;

    }
}

bool exists(vertex a, vector<vertex> b) {               
    auto it = find(b.begin(), b.end(), a);
    return (it != b.end());
}

};


int main() {
int v;
cin >>v;            //enter number of vertices

graph Graph(v);

int e;              //enter number of edges
cin >>e;

while (e--) {

    int a, b;
    cin >> a >> b;      //input vertices on the end of an edge
    Graph.addEdge(a, b);
}
Graph.printGraph();

return 0;
}

Each vertex has a name, its number, which is also his position in the "vertices" vector to make it easier to access. Because of that, vertices[0] is not used. Each time you input an edge between two vertices it checks if they are already in the vector and adds them. If they are not, then it adds the vertex to the set of vertices ("edges" set).

EDIT: I'm wanted to use this code to learn searching amd shortest path algorithm's (BFS, DFS, Dijkstra, Floyd-Warshall ...)for the competition

  • So each vertex is identified by an int, which is also their place in the vector<vertex>. Why does graph::exists need to use std::find to look for a vertex? Wouldn't b.size()>a.name && b[a.name].name == a.name suffice? – Cris Luengo Dec 21 '17 at 23:50
  • Normally yes, but the size of the vector is fixed by the user input or the default being 0 so the first part is always true if the graph is used. Second part works well, thanks – zeroth Dec 21 '17 at 23:59
  • What is the problem you are actually trying to solve? Your data structure should be different depending on the graph problem you care about. There is no single universal choice that is suitable for each problem. – Juho Dec 27 '17 at 10:34

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.