Data Structure and Algorithm - Graph - Minimal Spanning Tree - Definition


A (Free) tree T is sample graph such that if u and v are two vertex in T, then there is a unique path from to v. A tree in which a particular vertex is designed as a root called a rooted tree.
If a weight is assigned to the edges in T, T is called a Weighted Tree. If T is a weighted tree, the weight of T denote by W(T), is the sum of the weight of all the edges in T.
A tree T is called a Spanning Tree fo graph G if T is a sub-graph of G such that V(T) = V(G) ( means the number of vertices in T equal to number of vertices in G ), that is all t the vertices of G are in T.

Theorem : A graph G has a spanning if an only if G is connected.
From this theorem it follow in order to determine must be connected.

Let G be a weighted graph. A Minimal Spanning Tree of G is a spanning tree with minimum weight.

Algorithm :


---

V(G) = { V1 , V2 , V3 .... Vn } 

1. Set V(T) = { source } /* initial source with the V1*/    refer to vertex Vk
2. Set E(T) = { empty }  /* initial is null or empty set */ refer to edge (Vj,Vk)
3. for i=1 to n
1. minWeight = infinity /* largest number bigger than every number */
2. for j=1 to n
1. if Vj is in V(T) then
1. for k=1 to n 
1. if(Vk is not in T) && (weight[Vj][Vk] < minWeight){
1. endVertex = Vk
2. edge = (Vj,Vk)
3. minWeight = weight[Vj][Vk] 
3. V(T) = V(T) or { endVertex }
4. V(E) = V(E) or { edge }

---




Data Structure and Algorithm - Stack - stackAsLinkdedlist.h source code

stackAsLinkedlist.h as template


---

#include <iostream>
#include <string.h>
#include <assert.h>
using namespace std;
// Stack as Linkedlist

template <class Type>
class Node{
    public:
        Type data;
        Node *link;
        Node *back;
        Node(int data){
            this->data = data;
            link = NULL;
            back = NULL;
        }
};

template<class Type>
class stackType
{
private:
     int stackTop; //variable to point to the top of the stack
     Node<Type> *newnode;
     Node<Type> *tail;
public:
    //Function to initialize the stack to an empty state.
    //Postcondition: stackTop = 0
    void initializeStack(){
        tail = NULL;         
        stackTop = 0;
    }
   
    //Function to determine whether the stack is empty.
    //Postcondition: Returns true if the stack is empty;
    // otherwise, returns false.
    bool isEmptyStack(){
        return (stackTop == 0);
    }
    //Function to remove all the elements from the stack.
    //Postcondition: stackTop = 0
    void destroyStack(){
        for(int i=0;i<stackTop;i++)
           pop();
        stackTop = 0;
    }
   
    //Function to add newItem to the stack.
    //Precondition: The stack exists and is not full.
    //Postcondition: The stack is changed and newItem
    // is added to the top of stack.
    void push(Type newItem){
                newnode = new Node<Type>(newItem);
                if(stackTop > 0){
                    tail->link = newnode;
                    newnode->back = tail;
                    tail = newnode;
                } 
                tail = newnode;
                stackTop++;
    }
   
    //Function to return the top element of the stack.
    //Precondition: The stack exists and is not empty.
    //Postcondition: If the stack is empty, the program
    // terminates; otherwise, the top element
    // of the stack is returned.
    Type top(){
        assert(stackTop!=0);    // if stackTop = 0 then exit program
        return tail->data;
    }
   
    //Function to remove the top element of the stack.
    //Precondition: The stack exists and is not empty.
    //Postcondition: The stack is changed and the top
    // element is removed from the stack.
    void pop(){
        if(isEmptyStack()){
            cout<<"Stack is Empty..."<<endl;
        }else{
                if(stackTop == 1){
                    Node<Type> *delnode;
                    delnode = tail;
                    tail = NULL;
                    delete delnode;
                }else{
                    tail = tail->back;
                    delete tail->link;
                    tail->link = NULL;
                }
            stackTop--;
        }
    }
     // number of stacks
    int Nstack(){
         return stackTop;
     }   
    //constructor
    stackType(){
        stackTop = 0;
        tail = NULL;
    }
 
    //destructor
    ~stackType(){
         destroyStack();
    }
};

---