DFS Algorithm Implementation

void dfs(int at){ if(vis[at]) return ; else{ vis[at]=1; for(int i=0; i<vt[at].size(); i++){ int v=vt[at][i]; dfs(v); } } }

Floyd Warshsall - Implementation (C++)

/* Bismillahir Rahmanir Rahim Implementation of "Floyd Warshall" (C++) All pair shortest path */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) #define ll long long using namespace std; ll dis[300][300]; int main(){ ll n, e, u, v, w; cin>>n>>e; for(ll i=1; i<=n; i++){ for(ll j=1; j<=n; j++){ if(i==j)dis[i][j]=0; else dis[i][j]=1000000009; } } fi(0, e-1){ cin>>u>>v>>w; dis[u][v]=w; } for(ll k=1; k<=n; k++){ for(ll i=1; i<=n; i++){ for(ll j=1; j<=n; j++){ dis[i][j]=min(dis[i][j], (dis[i][k]+dis[k][j])); } } } for(ll i=1; i<=n; i++){ for(ll j=1; j<=n; j++) cout<<dis[i][j]<<" "; cout<<endl; } return 0; }

Dijkstra Algorithm - Implementation with C++

/* Bismillahir Rahmanir Rahim Dijkstra algorithm implementation(C++) Shortest path for all nodes from given node */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fd(n, m) for(int i=n; i>=m; i--) using namespace std; vector<int>vt[1009], cost[1009]; int dis[1009]; struct node{ int u, w; node(int a, int b){ u=a, w=b; } bool operator < (const node & p)const{ return p.w<w; } }; void dijkstra(int st){ priority_queue<node>q; memset(dis, 63, sizeof(dis)); dis[st]=0; q.push(node(st, 0)); while(!q.empty()){ node top=q.top(); q.pop(); int u=top.u; int sz=vt[u].size(); fi(0, sz-1){ int v=vt[u][i]; if(dis[u]+cost[u][i]<dis[v]){ dis[v]=dis[u]+cost[u][i]; q.push(node(v, dis[v])); } } } } int main(){ int n, e, u, v, w, m; cin>>n>>e; while(e--){ cin>>u>>v>>w; vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } cin>>m; // from this node dijkstra(m); fi(1, n)cout<<m<<" to "<<i<<" = "<<dis[i]<<endl; return 0; }

Kruskal's Algorithm - Implementation with C++

/* Bismillahir Rahmanir Rahim Implementation of (MST)Kruskal's algorithm with C++ */ #include<bits/stdc++.h> #define fi(i, n) for(int i=0; i<n; i++) using namespace std; struct node{ // structure int u, v, cost; }; int pr[101], edge, n; node one[100]; bool comp(node f, node s){ // sort of structure return f.cost<s.cost; } int find(int p){ // Disjoint Set if(pr[p]==p)return p; else return find(pr[p]); } int mst(int st){ // minimum-cost spanning tree fi(i, n) pr[i]=i; int cnt=0, xx, sm=0, yy; fi(i, edge){ xx=find(one[i].u); // parent of one[i].u yy=find(one[i].v); if(xx!=yy){ pr[yy]=xx; cnt++; sm+=one[i].cost; } if(cnt==n-1) break; } return sm; } int main(){ int u, v, cost; /* input start */ cin>>n>>edge; fi(i, edge){ cin>>u>>v>>cost; one[i].u=u; one[i].v=v; one[i].cost=cost; } sort(one, one+edge, comp); cout<<mst(1)<<endl; return 0; }

BFS Algorithm - Implementation with C++

/* Bismillahir Rahmamir Rahim Implementing BFS algorithm with c++ */ #include<bits/stdc++.h> using namespace std; vector<int>vt[100]; queue<int>q; int cost[100][100], dis[100], visit[100]; void bfs(int st){ for(int i=0; i<=100; i++){ dis[i]=100009, visit[i]=0; } int p, y, cst; dis[st]=0; q.push(st); while(!q.empty()){ p=q.front(); q.pop(); if(!visit[p]){ for(int i=0; i<vt[p].size(); i++){ y=vt[p][i]; cst=cost[p][y]+dis[p]; if(cst<dis[y]){ dis[y]=cst; q.push(y); } } visit[p]=1; } } } int main(){ int n1, n2, edge, c, x; cin>>edge; for(int i=0; i<edge; i++){ cin>>n1>>n2>>c; vt[n1].push_back(n2); vt[n2].push_back(n1); cost[n1][n2]=cost[n2][n1]=c; } bfs(1); while(cin>>x) cout<<dis[x]<<endl; return 0; }