PRACTICAL 7: WRITE A PROGRAM TO IMPLEMENT BINARY SEARCH TREE AND IMPLEMENT ALL TRAVERSAL TECHNIQUES. 1. Program: // C++ program to demonstrate insertion // in a BST recursively. #include <iostream> using namespace std; class BST { int data; BST *left, *right; public: // Default constructor. BST(); // Parameterized constructor. BST(int); // Insert function. BST* Insert(BST*, int); 51
// Inorder traversal. void Inorder(BST*); }; // Default Constructor definition. BST ::BST() : data(0) , left(NULL) , right(NULL) { } // Parameterized Constructor definition. BST ::BST(int value) { data = value; left = right = NULL; } // Insert function definition. BST* BST ::Insert(BST* root, int value) { if (!root) 52
{ // Insert the first node, if root is NULL. return new BST(value); } // Insert data. if (value > root->data) { // Insert right node data, if the 'value' // to be inserted is greater than 'root' node data. // Process right nodes. root->right = Insert(root->right, value); } else { // Insert left node data, if the 'value' // to be inserted is greater than 'root' node data. // Process left nodes. root->left = Insert(root->left, value); } // Return 'root' node, after insertion. 53
return root; } // Inorder traversal function. // This gives data in sorted order. void BST ::Inorder(BST* root) { if (!root) { return; } Inorder(root->left); cout << root->data << endl; Inorder(root->right); } // Driver code int main() { BST b, *root = NULL; root = b.Insert(root, 50); b.Insert(root, 30); b.Insert(root, 20); b.Insert(root, 40); b.Insert(root, 70); 54
b.Insert(root, 60); b.Insert(root, 80); b.Inorder(root); return 0; } // OUTPUT: 20 30 40 50 60 70 80 55
PRACTICAL 8: WRITE A PROGRAM TO IMPLEMENT HEAP SORT. 1. Program: // C++ program for implementation of Heap Sort #include <iostream> using namespace std; // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap void heapify(int arr[], int n, int i) { int largest = i; // Initialize largest as root int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) 56
largest = r; // If largest is not root if (largest != i) { swap(arr[i], arr[largest]); // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } // main function to do heap sort void heapSort(int arr[], int n) { // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i = n - 1; i > 0; i--) { // Move current root to end swap(arr[0], arr[i]); // call max heapify on the reduced heap 57
heapify(arr, i, 0); } } /* A utility function to print array of size n */ void printArray(int arr[], int n) { for (int i = 0; i < n; ++i) cout << arr[i] << \" \"; cout << \"\\n\"; } // Driver code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); heapSort(arr, n); cout << \"Sorted array is \\n\"; printArray(arr, n); } OUTPUT: 58
Sorted array is 5 6 7 11 12 1 59
PRACTICAL 9: WRITE A PROGRAM TO IMPLEMENT BREADTH FIRST SEARCH. 1. Program: // Program to print BFS traversal from a given // source vertex. BFS(int s) traverses vertices // reachable from s. #include<iostream> #include <list> using namespace std; // This class represents a directed graph using // adjacency list representation class Graph { int V; // No. of vertices // Pointer to an array containing adjacency // lists list<int> *adj; public: Graph(int V); // Constructor 60
// function to add an edge to graph void addEdge(int v, int w); // prints BFS traversal from a given source s void BFS(int s); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. } void Graph::BFS(int s) { // Mark all the vertices as not visited bool *visited = new bool[V]; for(int i = 0; i < V; i++) 61
visited[i] = false; // Create a queue for BFS list<int> queue; // Mark the current node as visited and enqueue it visited[s] = true; queue.push_back(s); // 'i' will be used to get all adjacent // vertices of a vertex list<int>::iterator i; while(!queue.empty()) { // Dequeue a vertex from queue and print it s = queue.front(); cout << s << \" \"; queue.pop_front(); // Get all adjacent vertices of the dequeued // vertex s. If an adjacent has not been visited, // then mark it visited and enqueue it for (i = adj[s].begin(); i != adj[s].end(); ++i) 62
{ if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } } // Driver program to test methods of graph class int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); cout << \"Following is Breadth First Traversal \" << \"(starting from vertex 2) \\n\"; 63
g.BFS(2); return 0; } OUTPUT: Following is Breadth First Traversal (starting from vertex 2) 2031 64
PRACTICAL 10: WRITE A PROGRAM TO IMPLEMENT DEPTH FIRST SEARCH. 1. Program: // C++ program to print DFS traversal from // a given vertex in a given graph #include <bits/stdc++.h> using namespace std; // Graph class represents a directed graph // using adjacency list representation class Graph { public: map<int, bool> visited; map<int, list<int>> adj; // function to add an edge to graph void addEdge(int v, int w); // DFS traversal of the vertices // reachable from v void DFS(int v); 65
}; void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. } void Graph::DFS(int v) { // Mark the current node as visited and // print it visited[v] = true; cout << v << \" \"; // Recur for all the vertices adjacent // to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) DFS(*i); } // Driver code int main() 66
{ // Create a graph given in the above diagram Graph g; g.addEdge(0, 1); g.addEdge(0, 9); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(9, 3); cout << \"Following is Depth First Traversal\" \" (starting from vertex 2) \\n\"; g.DFS(2); return 0; } // OUTPUT: Following is Depth First Traversal (starting from vertex 2) 20193 67
PRACTICAL 11: WRITE A PROGRAM TO IMPLEMENT DIJKSTRA’S ALGORITHM. 1. Program: // A C++ program for Dijkstra's single source shortest path algorithm. // The program is for adjacency matrix representation of the graph #include <limits.h> #include <stdio.h> // Number of vertices in the graph #define V 9 // A utility function to find the vertex with minimum distance value, from // the set of vertices not yet included in shortest path tree int minDistance(int dist[], bool sptSet[]) { // Initialize min value int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; 68
return min_index; } // A utility function to print the constructed distance array void printSolution(int dist[]) { printf(\"Vertex \\t\\t Distance from Source\\n\"); for (int i = 0; i < V; i++) printf(\"%d \\t\\t %d\\n\", i, dist[i]); } // Function that implements Dijkstra's single source shortest path algorithm // for a graph represented using adjacency matrix representation void dijkstra(int graph[V][V], int src) { int dist[V]; // The output array. dist[i] will hold the shortest // distance from src to i bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest // path tree or shortest distance from src to i is finalized // Initialize all distances as INFINITE and stpSet[] as false for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; 69
// Distance of source vertex from itself is always 0 dist[src] = 0; // Find shortest path for all vertices for (int count = 0; count < V - 1; count++) { // Pick the minimum distance vertex from the set of vertices not // yet processed. u is always equal to src in the first iteration. int u = minDistance(dist, sptSet); // Mark the picked vertex as processed sptSet[u] = true; // Update dist value of the adjacent vertices of the picked vertex. for (int v = 0; v < V; v++) // Update dist[v] only if is not in sptSet, there is an edge from // u to v, and total weight of path from src to v through u is // smaller than current value of dist[v] if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; } 70
// print the constructed distance array printSolution(dist); } // driver program to test above function int main() { /* Let us create the example graph discussed above */ int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, { 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; dijkstra(graph, 0); return 0; } OUTPUT: 71
Vertex Distance from Source 00 14 2 12 3 19 4 21 5 11 69 78 8 14 72
PRACTICAL 12: WRITE A PROGRAM TO IMPLEMENT SORTING USING RECURSION. 1. Program: // C/C++ program for recursive implementation // of Bubble sort #include <bits/stdc++.h> using namespace std; // A function to implement bubble sort void bubbleSort(int arr[], int n) { // Base case if (n == 1) return; // One pass of bubble sort. After // this pass, the largest element // is moved (or bubbled) to end. for (int i=0; i<n-1; i++) if (arr[i] > arr[i+1]) swap(arr[i], arr[i+1]); 73
// Largest element is fixed, // recur for remaining array bubbleSort(arr, n-1); } /* Function to print an array */ void printArray(int arr[], int n) { for (int i=0; i < n; i++) printf(\"%d \", arr[i]); printf(\"\\n\"); } // Driver program to test above functions int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr)/sizeof(arr[0]); bubbleSort(arr, n); printf(\"Sorted array : \\n\"); printArray(arr, n); return 0; } OUTPUT: 74
Sorted array : 11 12 22 25 34 64 90 75
Search
