weighted graph c 2b 2b

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