1#include <iostream>
2using namespace std;
3// stores adjacency list items
4struct adjNode {
5 int val, cost;
6 adjNode* next;
7};
8// structure to store edges
9struct graphEdge {
10 int start_ver, end_ver, weight;
11};
12class DiaGraph{
13 // insert new nodes into adjacency list from given graph
14 adjNode* getAdjListNode(int value, int weight, adjNode* head) {
15 adjNode* newNode = new adjNode;
16 newNode->val = value;
17 newNode->cost = weight;
18
19 newNode->next = head; // point new node to current head
20 return newNode;
21 }
22 int N; // number of nodes in the graph
23public:
24 adjNode **head; //adjacency list as array of pointers
25 // Constructor
26 DiaGraph(graphEdge edges[], int n, int N) {
27 // allocate new node
28 head = new adjNode*[N]();
29 this->N = N;
30 // initialize head pointer for all vertices
31 for (int i = 0; i < N; ++i)
32 head[i] = nullptr;
33 // construct directed graph by adding edges to it
34 for (unsigned i = 0; i < n; i++) {
35 int start_ver = edges[i].start_ver;
36 int end_ver = edges[i].end_ver;
37 int weight = edges[i].weight;
38 // insert in the beginning
39 adjNode* newNode = getAdjListNode(end_ver, weight, head[start_ver]);
40
41 // point head pointer to new node
42 head[start_ver] = newNode;
43 }
44 }
45 // Destructor
46 ~DiaGraph() {
47 for (int i = 0; i < N; i++)
48 delete[] head[i];
49 delete[] head;
50 }
51};
52// print all adjacent vertices of given vertex
53void display_AdjList(adjNode* ptr, int i)
54{
55 while (ptr != nullptr) {
56 cout << "(" << i << ", " << ptr->val
57 << ", " << ptr->cost << ") ";
58 ptr = ptr->next;
59 }
60 cout << endl;
61}
62// graph implementation
63int main()
64{
65 // graph edges array.
66 graphEdge edges[] = {
67 // (x, y, w) -> edge from x to y with weight w
68 {0,1,2},{0,2,4},{1,4,3},{2,3,2},{3,1,4},{4,3,3}
69 };
70 int N = 6; // Number of vertices in the graph
71 // calculate number of edges
72 int n = sizeof(edges)/sizeof(edges[0]);
73 // construct graph
74 DiaGraph diagraph(edges, n, N);
75 // print adjacency list representation of graph
76 cout<<"Graph adjacency list "<<endl<<"(start_vertex, end_vertex, weight):"<<endl;
77 for (int i = 0; i < N; i++)
78 {
79 // display adjacent vertices of vertex i
80 display_AdjList(diagraph.head[i], i);
81 }
82 return 0;
83}
84