Categories
- A ll Codes (310)
- ACM (222)
- ACM Technique (18)
- ACM-ICPC (57)
- Adhoc/Brute Force (3)
- Algorithm (83)
- Algo Unsolved (3)
- Asymptotic Notation (3)
- Geometry (2)
- Graph (6)
- All Pair Shortest Path (1)
- BFS (1)
- DFS (1)
- Single Source Shortest Path (2)
- Bellman Ford (1)
- Dijkstra (1)
- Topological Sort (1)
- Number Theory (6)
- Euler GCD (1)
- GCD (1)
- LCM (1)
- Prime factorization (1)
- Sieve of Erastosthenes (1)
- Trial Division (1)
- Recursion (3)
- Fibonacci (1)
- Tower of Hanoi (1)
- Searching (3)
- Binary Search (2)
- Linear Search (1)
- Sorting (13)
- Bubble Sort (1)
- Bucket Sort (1)
- Counting Sort (1)
- Heap Sort (1)
- Insertion Sort (1)
- Merge Sort (3)
- Quicksort (2)
- Radix Sort (1)
- Selection Sort (3)
- Tree (6)
- AVL Tree (1)
- B+ Tree (1)
- Binary Search Tree (4)
- Competitive Programming (1)
- Data Structure (7)
- Linked List (1)
- Queue (2)
- Circular Queue (1)
- Stack (1)
- Future Reference (1)
- Problem Solution (101)
- Codeforces (3)
- DevSkill (1)
- HackerEarth (17)
- HackerRank (4)
- Lightoj (2)
- SPOJ (1)
- Unsolved (1)
- URI Online Judge (34)
- UVa (18)
- Programming Contest (2)
- Programming Problem Solving (18)
- Challenge (1)
- CS Courses (165)
- Art of Effective Living (1)
- Artificial Intelligence (13)
- Assembly Language (3)
- Compiler Design (1)
- Computer Architecture (3)
- Data Communication (1)
- Data Mining (23)
- WEKA (2)
- Database (10)
- SQL (8)
- Digital Image Processing (5)
- Embedded Systems (2)
- Arduino (2)
- Games Development (1)
- Graphics (9)
- OpenGL (7)
- Mathematics (26)
- Numerical Method (18)
- Bisection Method (4)
- Numerical Method (18)
- Microprocessor (1)
- OOP (53)
- Operating System (11)
- Bash/Shell Scripting (7)
- CPU Scheduling (1)
- Simulation and Modelling (1)
- Web Engineering (1)
- DevOps (1)
- Experience (3)
- Events (1)
- Food Review (1)
- Travel (1)
- Financial Knowledge (1)
- Fitness (15)
- Body Transformation (2)
- Bodybuilding (7)
- Cycling (2)
- Fat Loss (2)
- Fitness Motivation (5)
- Health (2)
- Mental Health (1)
- My Gym (2)
- My Life Chart (3)
- My Life Style (3)
- Weight loss (1)
- Graphics Design (1)
- Photoshop (1)
- HigherStudy (87)
- EducationUSA (2)
- English Learning (9)
- Pronunciation (3)
- German Learning (29)
- Germany (9)
- Grammar (10)
- GRE (17)
- IELTS (26)
- Handwriting Improvement (1)
- Listening (4)
- Reading (1)
- Speaking (2)
- Writing Task (3)
- TOEFL (2)
- HTML/CSS (1)
- Job (56)
- CSE (2)
- CV/Resume (4)
- Interview (26)
- Fresher/Intern (3)
- Java (14)
- Software Engineering (3)
- Masters of Science (39)
- Advanced Formal Modelling (3)
- Cloud Computing (3)
- Data Mining (14)
- Implementation of Database (1)
- Introductory Data Analysis(IDA) (9)
- Excel (3)
- LaTeX (1)
- Machine Learning (3)
- Mathematics (1)
- Pattern Oriented Software Architecture(POS) (2)
- Real Time Computing (1)
- MSSQL (3)
- Stored Procedures (1)
- T-SQL (1)
- Open Source (6)
- Linux (4)
- Ubuntu 15.04 (1)
- Ubuntu 18.04 (1)
- Ubuntu14.04 (1)
- Ubuntu (2)
- Linux (4)
- Philosophy of Life (170)
- Learning (2)
- Life (10)
- Life Motivation (126)
- Business/Money (6)
- Career/Earning (12)
- Depression (3)
- Fearless Motivation (1)
- Life Quotes (2)
- Life Story/Journey (1)
- Passion (1)
- People Skill/Networking (14)
- Stress (2)
- Study Motivation (58)
- Success Hacks (74)
- Healthy Habit (15)
- Never Quit (36)
- Patience (23)
- Social Skills/Communicative Skills (5)
- Time Management (4)
- Life Productivity (11)
- Life Rules (5)
- Life Skills (4)
- Lifefact (4)
- Lifelessons (8)
- Lifestyle (1)
- Love (8)
- Motivation (17)
- Motivational Posts (7)
- Music (5)
- Poems (2)
- Love (1)
- Poetry (1)
- Ramadan (1)
- Romance (4)
- Sadness (2)
- Sarcasm (2)
- Thoughts (2)
- Pore Abar Bujhbo (8)
- Presentation (8)
- Programming (336)
- Language (305)
- C (152)
- Array (24)
- C library function (3)
- C Refresh (106)
- Function (17)
- logic (1)
- Logic Logic (4)
- Logics (1)
- Memory Management (1)
- Pointer (19)
- String (21)
- Structured Programming (1)
- C# (40)
- C++ (35)
- Vector (1)
- Java (46)
- Javascript (12)
- PHP (18)
- Python (17)
- C (152)
- R (1)
- R programming (3)
- Language (305)
- Project (2)
- Project Report (1)
- Research (53)
- BigData (3)
- Data Science (15)
- Machine Learning (23)
- Natural Language Processing(NLP) (5)
- Plagiarism Checker (2)
- Research Papers (5)
- Research Topic (3)
- Statistics (4)
- Sentiment Analysis (3)
- Software Development (84)
- .NET (34)
- Xamarin (1)
- Android (10)
- ASP.NET (10)
- Debate (2)
- Design Patterns Implementations (7)
- Laravel (4)
- Object Notation (4)
- Regex (2)
- Software Development Life Cycle(SDLC) (4)
- Training (9)
- LICT (9)
- unity3d (1)
- Version Control/SVN (4)
- XML (1)
- .NET (34)
- Tech Tips (21)
- Desktop (1)
- Fix (1)
- Laptop (1)
- Laptop(ল্যাপটপ) (1)
- HP (1)
- Techie Talk (15)
- Tech Debate (2)
- VPS (2)
- Uncategorized (66)
- University Life (3)
- 7th semester (1)
- 9th semester (1)
- Web Links (1)
- বাংলা (10)
- অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং (1)
- রিসার্চ (1)
- সি প্রোগ্রামিং (2)
- হার্ডডিস্ক পার্টিশান (1)
Random Quote
Random Quotes
-
Category Archives: Graph
Bellman Ford
It works on negative cycle.
Implemented Code:
Time Complexity:
O([E].[V])
Reference:
http://cyberlingo.blogspot.com/2015/07/bellman-ford-algorithm.html
Posted in Algo Unsolved, Bellman Ford, Single Source Shortest Path
Tagged not greedy
Dijkstra
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<bits/stdc++.h> using namespace std; int main(){ int cost[10][10],path[10][10],i,j,n,p,v,min,index=1; int distance[10],row,column; cout<<"Enter no. of nodes: "; cin>>n; cout<<"Enter cost matrix: \n"; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cin>>cost[i][j]; } } printf("Enter the node you want to visit:"); cin>>v; printf("Enter the path for the selected node:"); cin>>p; cout<<"Enter the path matrix: \n"; for(i=1;i<=p;i++) { for(j=1;j<=n;j++) { cin>>path[i][j]; } } for(i=1;i<=p;i++){ distance[i]=0; row=1; for(j=1;j<=n;j++) { if(row!=v) { column=path[i][j+1]; distance[i]=distance[i]+cost[row][column]; } row=column; } } min=distance[1]; for(i=1;i<=p;i++) { if(distance[i]<=min) { min=distance[i]; index=i; } } cout<<"The minimum distance is:"; cout<<min; for(i=1;i<=n;i++){ if(path[index][i]!=0) { printf("-->%d",path[index][i]); } } } |
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
Enter no. of nodes: 5 Enter cost matrix: 0 4 0 8 0 4 0 3 0 0 0 3 0 4 0 8 0 4 0 7 0 0 0 7 0 Enter the node you want to visit:5 Enter the path for the selected node:2 Enter the path matrix: 1 2 3 4 5 1 4 5 0 0 The minimum distance is:15-->1-->4-->5 |
Complexity:
O(E+V^2)
We are using here adjacency matrix list
Posted in Dijkstra, Graph, Single Source Shortest Path
Topological Sort
https://www.youtube.com/watch?v=Q9PIxaNGnig/
code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
// A Java program to print topological sorting of a DAG import java.io.*; import java.util.*; // This class represents a directed graph using adjacency // list representation class Graph { private int V; // No. of vertices private LinkedList<Integer> adj[]; // Adjacency List //Constructor Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i<v; ++i) adj[i] = new LinkedList(); } // Function to add an edge into the graph void addEdge(int v,int w) { adj[v].add(w); } // A recursive function used by topologicalSort void topologicalSortUtil(int v, boolean visited[], Stack stack) { // Mark the current node as visited. visited[v] = true; Integer i; // Recur for all the vertices adjacent to this // vertex Iterator<Integer> it = adj[v].iterator(); while (it.hasNext()) { i = it.next(); if (!visited[i]) topologicalSortUtil(i, visited, stack); } // Push current vertex to stack which stores result stack.push(new Integer(v)); } // The function to do Topological Sort. It uses // recursive topologicalSortUtil() void topologicalSort() { Stack stack = new Stack(); // Mark all the vertices as not visited boolean visited[] = new boolean[V]; for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function to store // Topological Sort starting from all vertices // one by one for (int i = 0; i < V; i++) if (visited[i] == false) topologicalSortUtil(i, visited, stack); // Print contents of stack while (stack.empty()==false) System.out.print(stack.pop() + " "); } // Driver method public static void main(String args[]) { // Create a graph given in the above diagram Graph g = new Graph(6); g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); System.out.println("Following is a Topological " + "sort of the given graph"); g.topologicalSort(); } } |
Output:
1 2 |
Following is a Topological sort of the given graph 5 4 2 3 1 0 |
Time Complexity: O(V+E)
Space Complexity: O(V)
V for vertex E for edge
code courtesy:
I understood the theory but need to understand the code well later
Posted in Graph, Topological Sort
Algorithm: BFS(Breadth First Search)
Theory:
http://scanftree.com/Data_Structure/Breadth-First-Search
Bangla:
Video:
code implementation:
Some other links may help:
code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
//bfs implementation for undirected unweighted graph #include<fstream> #include<queue> #include<vector> #include<iostream> using namespace std; int main() { int n,m,start; int a,b; cin>>n>>m>>start; vector<int> samp; vector<vector<int> > conn(n+1,samp); //conn taking custom value in vector to make it sizeable //loading adjacency matrix for(int i=0; i<m; i++) { cin>>a>>b; conn[a].push_back(b); conn[b].push_back(a); } bool visited[n+1]; //visited node 1 to last for(int i=0; i<n+1; i++) { visited[i]=false; //making each and every node false } queue<int> Q; //creating a queue Q.push(start); //pushing the starting node in the queue visited[start]=true; //make the starting node only true int siz=0; int lev=0; while(!Q.empty()) { cout<<"LEVEL:"<<lev<<endl; siz=Q.size(); while(siz--) { int first=Q.front(); Q.pop(); cout<<first<<endl; for(int j=0; j<conn[first].size(); j++) { if(!visited[conn[first][j]]) { visited[conn[first][j]]=true; //making true which have visited Q.push(conn[first][j]); //pushing the value in the queue } } } lev++; //level increasing in each iteration } return 0; } |
Input:
1 2 3 4 5 6 7 8 9 10 11 |
9 10 1 //here 1 is starting node that can be any value 1 2 1 3 3 4 3 5 1 6 4 6 4 9 9 8 1 7 7 3 |
Output:
Another code tried to write from the pseudocode is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include<iostream> #include<queue> #include<bits/stdc++.h> using namespace std; //void BFS(int); int WHITE=1,GRAY=2,BLACK=3,inf=31000,NIL=-1; int num_e,num_v; queue<int> Q; int adj[20][20],color[20],d[20],p[20]; void initialization() { int k,j; for(k=0; k<20; k++) { for(j=0; j<20; j++) { adj[k][j]=0; } } } void build_adj_matrix() { int i,a,b; cin>>num_v; cin>>num_e; for(i=1; i<=num_e; i++) { cin>>a>>b; adj[a][b]=1; adj[b][a]=1; } } void BFS(int s) { int i,u,v; for(i=1; i<=num_v; i++) { color[i]=WHITE; d[i]=inf; p[i]=NIL; } color[s]=GRAY; d[s]=0; p[s]=NIL; Q.push(s); while(!Q.empty()) { int u=Q.pop(); for(v=1; v<=num_v; v++) { if(adj[u][v]==1) { if(color[v]==WHITE) { color[v]=GRAY; d[v]=d[u]+1; p[v]=u; Q.push(v); } } } color[u]=BLACK; } } void distance_output() { int i; cout<<"Shortest path from source vertex"; for(i=1; i<=num_v; i++) { cout<<"to node "<<i<<"is "<<d[i]; } } void path_print(int s,int v) { if(v==s) { cout<<s<<endl; } else if(p[v]==NIL) { cout<<"No path from"<<s<<"to "<<v<<"exists"; } else { path_print(s,p[v]); cout<<v<<endl; } } int main() { int source,destination; initialization(); build_adj_matrix(); cin>>source; cin>>destination; BFS(source); distance_output(); path_print(source,destination); return 0; } |
reference from java code: http://www.programmingboss.com/2014/06/breadth-first-search-bfs-in-java.html
ppt slide: https://drive.google.com/file/d/0B0sCkwd_qKgJSzZyUWVYZU5GWlk/edit
Posted in A ll Codes, Algorithm, BFS, C, C Refresh
Depth Firtst Search(DFS) Algorithm Explanation and Implementation in C++
Discovery Time and Finishing Time Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
//dfs using adjacency list in directed graph #include<iostream> using namespace std; int WHITE=1,GREY=2,BLACK=3,INF=310000,NIL=-1; int num_v,num_e,time=0; int adj[20][20],color[20],p[20],d[20],f[20]; void DFS_visit(int); void initialization() { int k,j; for(k=0; k<20; k++) { for(j=0; j<20; j++) { adj[k][j]=0; } } } void build_adj_matrix() { int i,a,b; cout<<"Enter number of vertices: "<<endl; cin>>num_v; cout<<"Enter number of edges: "<<endl; cin>>num_e; cout<<"Enter edges: "<<endl; for(i=1; i<=num_e; i++) { cin>>a>>b; adj[a][b]=1; } } void dfs() { int i,u; for(i=1; i<=num_v; i++) { color[i]=WHITE; p[i]=NIL; } for(u=1; u<=num_v; u++) { if(color[u]==WHITE) { DFS_visit(u); } } } void DFS_visit(int u) { int i,v; color[u]=GREY; time=time+1; d[u]=time; for(v=1; v<=num_v; v++) { if(adj[u][v]==1) { if(color[v]==WHITE) { p[v]=u; DFS_visit(v); } } } color[u]=BLACK; time=time+1; f[u]=time; } void distance_output() { int i; cout<<"Discovery time and finish time:\n"; for(i=1; i<=num_v; i++) { cout<<"Node "<<i<<" is "<<d[i]<<"/"<<f[i]<<" \n"; } } int main() { initialization(); build_adj_matrix(); dfs(); distance_output(); return 0; } |
input/output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Enter number of vertices: 4 Enter number of edges: 4 Enter edges: 2 3 2 1 1 4 3 4 Discovery time and finish time: Node 1 is 1/4 Node 2 is 5/8 Node 3 is 6/7 Node 4 is 2/3 |
pseudo:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
void DFS_visit(int u){ int i,v; colour[u]=GREY; time=time+1; d[u]=time; for(v=1;v<=num_v;v++) { if(adj[u][v]==1){ if(color[v]==WHITE){ p[v]=u; DFS_visit(v); } } } color[u]=BLACK; time=time+1; f[u]=time; } |
Pseudocode from shafayet vai’s blog:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
procedure DFS(G, source): U ← source time ← time+1 d[u] ← time color[u] ← GREY for all edges from u to v in G.adjacentEdges(v) do if color[v] = WHITE DFS(G,v) end if end for color[u] ← BLACK time ← time+1 f[u] ← time return |
Reference:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm
http://www.dotnetlovers.com/Article/182/implementation-of-depth-first-searchdfs
Another code to find the order of the node:
References:
One of my classmates blog link: http://programminghelpbd.blogspot.com/2014/06/breadth-first-search-dfs-in-java.html
and this ppt : https://drive.google.com/file/d/0B0sCkwd_qKgJZEJzS1pWeXNmNUE/edit
CLRS website: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm
Shafayet Ashraf: http://www.shafaetsplanet.com/planetcoding/?p=973
saurabhschool youtube link : https://www.youtube.com/watch?v=gCNsAKkUHPM
Youtube video of Mifta Sintaha:
and here is also a good implementation:
http://electrofriends.com/source-codes/software-programs/cpp-programs/cpp-data-structure/c-programs-for-the-implementation-of-depth-first-searchdfs-for-a-given-graph/comment-page-1/#comments
Java array basics: http://www.tutorialspoint.com/java/java_arrays.htm
Another code to find the order of vertices:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include<iostream> #include<conio.h> #include<stdlib.h> using namespace std; int adj[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10]; main() { int m; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES \n"; for(k=1; k<=m; k++) { cin >>i>>j; adj[i][j]=1; } cout <<"enter initial vertex:"; cin >>v; cout <<"ORDER OF VISITED VERTICES: "; cout << v <<" "; visited[v]=1; k=1; while(k<n) { for(j=n; j>=1; j--) if(adj[v][j]!=0 && visited[j]!=1 && visit[j]!=1) { visit[j]=1; stk[top]=j; top++; } v=stk[--top]; cout<<v << " "; k++; visit[v]=0; visited[v]=1; } } |