Prim's Algorithm(modified).cpp

#include<iostream>
#include<cstdlib>
#define WHITE 0 //not visited
#define BLACK 1 //visited
#define INF -1
using namespace std;
void create_nodes(int nodes, int** &edges, int* &parents, int* &colors){

    edges=new int*[nodes];
    parents=new int[nodes];
    colors=new int[nodes];

}
void populate_nodes(int nodes, int** &edges, int* &parents, int* &colors, int high, int low){

    for(int i=0; i<nodes; i++){
        edges[i]=new int[nodes];
        for(int j=0; j<nodes; j++){
            if(i!=j){
                edges[i][j]=low+rand()%(high-low+1);
                parents[i]=i;
                colors[i]= WHITE;
            }
            else{
                edges[i][j]=0;
            }
        }
    }
    }
void display_graph(int nodes, int** edges){
    for(int i=0; i<nodes; i++){
        for(int j=0; j<nodes; j++){
            cout<<edges[i][j]<<" ";
        }
        cout<<endl;
    }
}
int minValue(int nodes, int* minWeightOfEdges, int* nonMstList){
    int minValue=INF;
    int minIndex;
    for(int i=0; i<nodes; i++){
        //nonMSTList is not visited && minWeightOfEdges is less than min Value
        if(nonMstList[i]==WHITE && minWeightOfEdges[i]<minValue){
            //update minValue with minWeightofEdges[i]
            minValue=minWeightOfEdges[i];
            minIndex=i;
        }
    }
    return minIndex;
}
void display_MST(int* parent,int nodes, int** edges){
        cout<<"Edge: "<<"Weight: "<<endl;
        for(int i=0; i<nodes; i++){
            cout<<"Edge: "<<parent[i]<<" -> "<<i<<"Weight: "<<edges[i][parent[i]];
        }
    }
void create_MST(int start,int nodes, int** edges, int* parent, int* colors,
                int* nonMstList, int* minWeightOfEdges){
    nonMstList=new int[nodes];
    minWeightOfEdges=new int[nodes];
    int minIndex;
    for(int i=start; i<nodes; i++){
        minWeightOfEdges[i]=INF;
        nonMstList[i]=WHITE;
        minWeightOfEdges[0]=0;
        parent[0]=INF;
        }
    for(int i=start; i<nodes-1; i++){
        minIndex=minValue(nodes,minWeightOfEdges,nonMstList);
        nonMstList[minIndex]=BLACK;
        }
    for(int i=start; i<nodes; i++){
        if(edges[minIndex][i] && nonMstList[i]==WHITE && edges[minIndex][i]<minWeightOfEdges[i]){
            parent[i]=minIndex;
            minWeightOfEdges[i]=edges[minIndex][i];
            }
        }
        display_MST(parent,nodes,edges);
        }
int main(){
    int nodes;
    int high,low;
    cout<<"Enter number of nodes: ";
    cin>>nodes;
    cout<<"Enter range high, low: ";
    cin>>high>>low;
    cout<<endl;
    int **edges;
    int *parents;
    int *colors;
    create_nodes(nodes,edges,parents,colors);
    populate_nodes(nodes,edges,parents,colors,high,low);
    display_graph(nodes,edges);
    int startNode;
    cout<<"Enter Starting Node: ";
    cin>>startNode;
    cout<<endl;
    int *nonMstList;
    int *minWeightOfEdges;
    create_MST(startNode,nodes,edges,parents,colors,
               nonMstList,minWeightOfEdges);
    return 0;
}




LCS.cpp

#include<iostream>
using namespace std;
int maximum(int num1, int num2){
    if(num1>num2){
        return num1;
    }
    else{
        return num2;
    }
    }
int lcs(string line1, string line2, int line1Size, int line2Size){
    int lengthOfLcs[line1Size+1][line2Size+1];
    for(int i=0; i<=line1Size; i++){
        for(int j=0; j<=line2Size; j++){
            if(i==0 && j==0){
                lengthOfLcs[i][j]=0;
            }
            else if(line1[i-1]==line2[j-1]){
                lengthOfLcs[i][j]=lengthOfLcs[i-1][j-1]+1;
            }
            else{
                lengthOfLcs[i][j]=maximum(lengthOfLcs[i-1][j],lengthOfLcs[i][j-1]);
            }
        }
    }
    return lengthOfLcs[line1Size][line2Size];
    }
int main(){
    string line1;
    string line2;
    cout<<"Enter Line 1: ";
    cin>>line1;
    cout<<"Enter Line 2: ";
    cin>>line2;
    int line1Size= line1.size();
    int line2Size= line2.size();
    cout<<"LCS: "<<lcs(line1,line2,line1Size,line2Size);
    return 0;
    }




Kruskal Algorithm.cpp

#include <cstdio>
#include <algorithm>
#include<iostream>
using namespace std;
struct Edge {
    int u;
    int v;
    int weight;
};
class UF{
    int *id;
    int cnt;
    int *sz;
public:
    UF(int N){
        cnt = N;
        id = new int[N];
        sz = new int[N];
        for(int i=0; i<N; i++){
            id[i] = i;
            sz[i] = 1;
        }
    }
    ~UF(){
        delete [] id;
        delete [] sz;
    }
    int find(int p){
        int root = p;
        while (root != id[root]){
            root = id[root];
        }
        while (p != root){
            int newp = id[p];
            id[p] = root;
            p = newp;
        }
        return root;
    }
    void merge(int x, int y){
        int i = find(x);
        int j = find(y);
        if (i == j) return;
        if(sz[i] < sz[j]){
             id[i] = j; sz[j] += sz[i];
        }
        else{
            id[j] = i; sz[i] += sz[j];
        }
        cnt--;
    }
    bool connected(int x, int y){

        return find(x) == find(y);
    }
    int count() {

        return cnt;
    }
};
bool comp(Edge *a, Edge *b){
    return a->weight < b->weight;
}
int main(){
    int V;
    int E;
    int i;
    int N;
    int u;
    int v;
    int cost;
    Edge **edges;
    Edge **mst;
    scanf("%d %d", &V, &E);
    edges = new Edge*[E];
    for(i=0; i<E; i++){
        edges[i] = new Edge;
        scanf("%d %d %d", &(edges[i]->u), &(edges[i]->v), &(edges[i]->weight));
    }
    sort(edges, edges + E, comp);
    UF uf(V);
    mst = new Edge*[V-1];
    for(N=i=cost=0; i<E && N<V-1; i++){
        u = edges[i]->u; v = edges[i]->v;
        if(!uf.connected(u, v)){
            uf.merge(u, v);
            mst[N++] = edges[i];
            cost += edges[i]->weight;
        }
    }
    cout<<"Total cost of MST : %d\n"<<cost;
    cout<<"Edges in MST :\n";
    for(i=0; i<N; i++){
        cout<<("%d %d %d\n", mst[i]->u, mst[i]->v, mst[i]->weight);
    }
    return 0;
}