1#include <iostream>
2using namespace std;
3
4struct adjNode {
5 int val, cost;
6 adjNode* next;
7};
8
9struct graphEdge {
10 int start_ver, end_ver, weight;
11};
12class DiaGraph{
13
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;
20 return newNode;
21 }
22 int N;
23public:
24 adjNode **head;
25
26 DiaGraph(graphEdge edges[], int n, int N) {
27
28 head = new adjNode*[N]();
29 this->N = N;
30
31 for (int i = 0; i < N; ++i)
32 head[i] = nullptr;
33
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
39 adjNode* newNode = getAdjListNode(end_ver, weight, head[start_ver]);
40
41
42 head[start_ver] = newNode;
43 }
44 }
45
46 ~DiaGraph() {
47 for (int i = 0; i < N; i++)
48 delete[] head[i];
49 delete[] head;
50 }
51};
52
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
63int main()
64{
65
66 graphEdge edges[] = {
67
68 {0,1,2},{0,2,4},{1,4,3},{2,3,2},{3,1,4},{4,3,3}
69 };
70 int N = 6;
71
72 int n = sizeof(edges)/sizeof(edges[0]);
73
74 DiaGraph diagraph(edges, n, N);
75
76 cout<<"Graph adjacency list "<<endl<<"(start_vertex, end_vertex, weight):"<<endl;
77 for (int i = 0; i < N; i++)
78 {
79
80 display_AdjList(diagraph.head[i], i);
81 }
82 return 0;
83}
1//code by Soumyadeep Ghosh
2//insta : @soumyadepp
3//linked in: https://www.linkedin.com/in/soumyadeep-ghosh-90a1951b6/
4
5#include <bits/stdc++.h>
6using namespace std;
7
8//undirected weighted graph and all functions
9class WeightedGraph
10{
11 vector< pair<int,int> >*adjacency_list;
12 int vertices;
13 public:
14 WeightedGraph(int n)
15 {
16 vertices=n;
17 adjacency_list=new vector< pair<int,int> >[n];
18 }
19 void add_edge(int v1,int v2,int wt);
20 void dfsHelper(int src,bool visited[]);
21 void dfs(int src);
22 void bfs(int src);
23 int minDistance(vector<int>dist,bool visited[]);
24 void djisktra(int src);
25 void display_graph();
26};
27
28int main()
29{
30 //graph of five vertices
31 WeightedGraph wg1(5);
32 //adding edges
33 wg1.add_edge(0,1,10);
34 wg1.add_edge(1,2,20);
35 wg1.add_edge(2,3,30);
36 wg1.add_edge(1,3,40);
37 wg1.add_edge(2,4,100);
38 wg1.add_edge(4,0,10);
39 //displaying the graph
40 wg1.display_graph();
41 //dfs from vertex 0
42 wg1.dfs(0);
43 //bfs from vertex 0
44 wg1.bfs(0);
45 //djikstra
46 for(int i=0;i<5;i++)
47 {
48 djikstra(i);
49 }
50 return 0;
51}
52//function definitions
53
54void WeightedGraph::add_edge(int v1,int v2,int wt)
55{
56 /*push the other vertex into the adjacency list of the given vertex
57 and vice versa. If it would have been a directed graph,
58 only the first line would be enough
59 */
60 adjacency_list[v1].push_back(make_pair(v2,wt));
61 adjacency_list[v2].push_back(make_pair(v1,wt));
62}
63
64void WeightedGraph::dfsHelper(int src,bool visited[])
65{
66 visited[src]=true;
67 cout<<src<<" ";
68 for(vector<int>::iterator it=adjacency_list.begin();i!=adjacency_list.end();it++)
69 {
70 if(!visited[it->first]);
71 dfsHelper(it->first,visited);
72 }
73}
74void WeightedGraph::dfs(int src)
75{
76 bool visited[vertices];
77 for(int i=0;i<vertices;i++)
78 visited[i]=false;
79 dfsHelper(src,visited);
80}
81void WeightedGraph::bfs(int src)
82{
83 bool visited[vertices];
84 for(int i=0;i<vertices;i++)
85 visited[i]=false;
86 cout<<src<<" ";
87 visited[src]=true;
88 queue<int>helper;
89 helper.push(src);
90 while(!helper.empty())
91 {
92 src=helper.front();
93 for(vector<int>::iterator it=adjacency_list[src].begin();it!+adjacency_list[src].end();it++)
94 {
95 if(!visited[it->first])
96 {
97 visited[it->first]=true;
98 cout<<it->first<<" ";
99 helper.push(it->first);
100 }
101 }
102 helper.pop();
103 }
104}
105
106int WeightedGraph::minDistance(vector<int>dist,bool visited[])
107 {
108 int min=INT_MAX;
109 int minIndex=INT_MAX;
110 for(int i=0;i<N;i++)
111 {
112 if(!visited[i]&&dist[i]<=min)
113 {
114 min=dist[i];
115 minIndex=i;
116 }
117 }
118 return minIndex;
119 }
120
121
122void WeightedGraph::djikstra(int src)
123 {
124 vector<int>dist;
125 bool visited[vertices];
126 for(int i=0;i<vertices;i++)
127 {
128 dist.push_back(INT_MAX);
129 visited[i]=false;
130 }
131 visited[src]=true;
132 dist[src]=0;
133 for(int i=0;i<vertices-1;i++)
134 {
135 int k=minDistance(dist,visited);
136 visited[k]=true;
137 for(int j=0;j<vertices;j++)
138 {
139 if(!visited[i]&&dist[i]!=INT_MAX&&adjacency_list[i][j].second+dist[i]<dist[j])
140 {
141 dist[j]=adjacency_list[i][j].second+dist[i];
142 }
143 }
144 }
145 for(int i=0;i<dist.size();i++)
146 cout<<dist[i]<<" ";
147
148 cout<<endl;
149 }
150void WeightedGraph::display_graph()
151{
152 int a,b;
153 //first loop to traverse across vertices
154 for(int i=0;i<vertices;i++)
155 {
156 cout<<"Adjacency list of vertex "<<i<<endl;
157 //second loop to traverse across the adjacency list of some vertex i
158 for(auto it=adjacency_list[i].begin();it!=adjacency_list[i].end();it++)
159 {
160 //set a as the vertex number and b as the weight
161 a=it->first;
162 b=it->second;
163 cout<<"Vertex : "<<a<<" Weight : "<<b<<endl;
164 }
165 cout<<endl;
166 }
167}
168
169//thank you!
170