Graph
A graph is a data structure that consists of nodes connected to each other through edges. Nodes are also called vertices. Graphs are used to represent networks. These networks may include paths in a city or a telephone network, among others.
Example of Graph
In the image above, you can see an example of a graph. There are 4 nodes (1, 2, 3, 4) that are connected to each other. The vertices and edges are shown. I tried to make it simple so you can understand it easily.
My Graph
When I tried to implement the same example in code, my graph had so many bugs. But I kept trying, and I got something like this (shown in the image above). It’s still connected, right? The code was messy, so I tried to make it as short and simple as possible so you can understand.
Graph Code
In this code, you can see the main function snippets. I’m adding the adjacency list and then adding it to the edges, which have source and destination nodes. I know it might be a bit confusing, so let’s see each step one by one, starting from the beginning.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
// Constructor
Node(int v) : data(v), next(nullptr) {}
};
This is a common piece of code we’ve seen before when implementing arrays, linked lists, stacks, and queues. At the top, it includes boilerplate code like input/output headers. In the Node structure, I added an integer value and a pointer to the next node, along with a constructor to initialize the value and set the next pointer to null.
struct Edge {
// source and destination
int src, dest;
Edge(int s, int d) : src(s), dest(d) {};
};
This is the structure for the edge, which holds the source and destination values as integers. In the constructor, I initialized src and dest to s and d, respectively.
// add
void addEdge(Node* adj[], Edge e) {
Node* n = new Node(e.dest);
n->next = adj[e.src - 1];
adj[e.src - 1] = n;
}
This is the add function. Here, I only added the function for adding edges; you can add remove and print functions yourself. Try it 🙂, In this function, I add an edge to the graph. It takes an array of nodes and an edge as input (adj and e). I create a new node with the destination value of the edge, set the next pointer of the new node to the current head of the source node, and finally update the head of the source node to the new node. For example, n->next = adj[e.src - 1] will adjust the index and add the new node to the adjacency list.
int main() {
int V = 4;
Node* adj[V];
for (int i = 0; i < V; i++) {
adj[i] = nullptr;
}
In the main function, I set V to 4 to create 4 nodes (1, 2, 3, 4). Then, I initialized an adjacency list of nodes and set all adj[i] to null, making it empty at the start.
Edge e1(1, 2);
e1.addEdge(adj, e1);
Edge e2(1, 3);
e2.addEdge(adj, e2);
Edge e3(1, 4);
e3.addEdge(adj, e3);
Edge e4(2, 3);
e4.addEdge(adj, e4);
Edge e5(2, 4);
e5.addEdge(adj, e5);
Edge e6(3, 4);
e6.addEdge(adj, e6);
In this code, I created edges and added them to the adjacency list, connecting the nodes to each other.
for (int i = 0; i < V; i++) {
Node* n = adj[i];
// Adjusting index to start from 1 instead of 0
cout << i + 1 << " -> ";
while (n) {
cout << n->data << " ";
n = n->next;
}
cout << endl;
}
}
Finally, I printed the graph to show the connections between nodes and edges. It’s not perfect, but you can modify it to make it better. The key is to keep it simple and easy to understand. This was my attempt.
This concludes today’s tutorial. See you in the next one 😊
Check out the full video tutorial:
