Traveling Salesperson problem:Given n cities, a salesperson starts at a specified city (source), visit all n-1 cities only once and return tio the the city from where he has started.…
Sum of SubsetsSubset-Sum Problem is to find a subset of a given set S= {s1, s2… sn} of n positive integers whose sum is equal to a given positive integer…
Depth First Search:Depth-first search starts visiting vertices of a graph at an arbitrary vertex by marking it as having been visited. On each iteration, the algorithm proceeds to an unvisited…
Breadth First Search:BFS explores graph moving across to all the neighbors of last visited vertex traversals i.e., it proceeds in a concentric manner by visiting all the vertices that are…
Kruskal’s algorithm:Kruskal‟s algorithm finds the minimum spanning tree for a weighted connected graph G=(V,E) to get an acyclic subgraph with |V|-1 edges for which the sum of edge weights is…
Single Source Shortest Paths Problem:For a given vertex called the source in a weighted connected graph, find the shortest paths to all its other vertices. Dijkstra‟s algorithm is the best…
#include #include int w[10],p[10],v[10][10],n,i,j,cap,x[10]={0}; int max(int i,int j) { return ((i>j)?i:j); } int knap(int i,int j) { int value; if(v[i][j]
Warshall’s algorithm:The transitive closure of a directed graph with n vertices can be defined as the n-by-n boolean matrix T={tij}, in which the element in the ith row(1<=i<=n) and jth…
Topological Ordering:This method is based on decrease and conquer technique a vertex with no incoming edges is selected and deleted along with no incoming edges is selected and deleted along…
Quicksort is a divide and conquer algorithm which relies on a partition operation: to partition an array,an element, called a pivot is choosen,all smaller elements are moved before the pivot, and…