I’ve started to learn about graphs and how to represent them in code. Below 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, it’s 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 ads them if they are not, then it adds the vertex to the set of vertices (“edges” set).