Untitled
unknown
plain_text
4 years ago
11 kB
10
Indexable
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
int weight = 0;
struct AdjListNode {
int dest;
int weight;
struct AdjListNode* next;
};
struct AdjList {
struct AdjListNode* head;
};
struct Graph {
int V;
struct AdjList* array;
};
struct AdjListNode* newAdjListNode(int dest, int weight)
{
struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
void addEdge(struct Graph* graph, int src, int dest, int weight)
{
struct AdjListNode* newNode = newAdjListNode(dest, weight);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}
struct MinHeapNode {
int v;
int key;
};
struct MinHeap {
int size;
int capacity;
int* pos;
struct MinHeapNode** array;
};
struct MinHeapNode* newMinHeapNode(int v, int key)
{
struct MinHeapNode* minHeapNode = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
minHeapNode->v = v;
minHeapNode->key = key;
return minHeapNode;
}
struct MinHeap* createMinHeap(int capacity)
{
struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
minHeap->pos = (int*)malloc(capacity * sizeof(int));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHeapNode**)malloc(capacity * sizeof(struct MinHeapNode*));
return minHeap;
}
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)
{
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
void minHeapify(struct MinHeap* minHeap, int idx)
{
int smallest, left, right;
smallest = idx;
left = 2 * idx + 1;
right = 2 * idx + 2;
if (left < minHeap->size && minHeap->array[left]->key < minHeap->array[smallest]->key)
smallest = left;
if (right < minHeap->size && minHeap->array[right]->key < minHeap->array[smallest]->key)
smallest = right;
if (smallest != idx) {
struct MinHeapNode* smallestNode = minHeap->array[smallest];
struct MinHeapNode* idxNode = minHeap->array[idx];
minHeap->pos[smallestNode->v] = idx;
minHeap->pos[idxNode->v] = smallest;
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
int isEmpty(struct MinHeap* minHeap)
{
return minHeap->size == 0;
}
struct MinHeapNode* extractMin(struct MinHeap* minHeap)
{
if (isEmpty(minHeap))
return NULL;
struct MinHeapNode* root = minHeap->array[0];
struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];
minHeap->array[0] = lastNode;
minHeap->pos[root->v] = minHeap->size - 1;
minHeap->pos[lastNode->v] = 0;
--minHeap->size;
minHeapify(minHeap, 0);
return root;
}
void decreaseKey(struct MinHeap* minHeap, int v, int key)
{
int i = minHeap->pos[v];
minHeap->array[i]->key = key;
while (i && minHeap->array[i]->key < minHeap->array[(i - 1) / 2]->key) {
minHeap->pos[minHeap->array[i]->v] = (i - 1) / 2;
minHeap->pos[minHeap->array[(i - 1) / 2]->v] = i;
swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
int isInMinHeap(struct MinHeap* minHeap, int v)
{
if (minHeap->pos[v] < minHeap->size)
return 1;
return 0;
}
void printArr(int arr[], int n)
{
for (int i = 1; i < n; ++i)
printf("%d - %d\n", arr[i], i);
}
void PrimMST(struct Graph* graph)
{
int V = graph->V;
int parent[V];
int key[V];
struct MinHeap* minHeap = createMinHeap(V);
for (int v = 1; v < V; ++v) {
parent[v] = -1;
key[v] = INT_MAX;
minHeap->array[v] = newMinHeapNode(v, key[v]);
minHeap->pos[v] = v;
}
key[0] = 0;
minHeap->array[0] = newMinHeapNode(0, key[0]);
minHeap->pos[0] = 0;
minHeap->size = V;
while (!isEmpty(minHeap)) {
struct MinHeapNode* minHeapNode = extractMin(minHeap);
int u = minHeapNode->v;
weight = weight + minHeapNode->key;
struct AdjListNode* pCrawl = graph->array[u].head;
while (pCrawl != NULL) {
int v = pCrawl->dest;
if (isInMinHeap(minHeap, v) && pCrawl->weight < key[v]) {
key[v] = pCrawl->weight;
parent[v] = u;
decreaseKey(minHeap, v, key[v]);
}
pCrawl = pCrawl->next;
}
}
printf("\nMST :\n\n");
printArr(parent, V);
printf("\nWeight : %d",weight);
}
int main()
{
int V = 9;
struct Graph* graph = createGraph(V);
addEdge(graph,0,1,4);
addEdge(graph,0,7,8);
addEdge(graph,1,0,4);
addEdge(graph,1,2,8);
addEdge(graph,1,7,11);
addEdge(graph,2,1,8);
addEdge(graph,2,3,7);
addEdge(graph,2,5,4);
addEdge(graph,2,8,2);
addEdge(graph,3,2,7);
addEdge(graph,3,4,9);
addEdge(graph,3,5,14);
addEdge(graph,4,3,9);
addEdge(graph,4,5,10);
addEdge(graph,5,2,4);
addEdge(graph,5,3,14);
addEdge(graph,5,4,10);
addEdge(graph,5,6,2);
addEdge(graph,6,5,2);
addEdge(graph,6,7,3);
addEdge(graph,6,8,6);
addEdge(graph,7,0,8);
addEdge(graph,7,1,11);
addEdge(graph,7,6,1);
addEdge(graph,7,8,7);
addEdge(graph,8,2,2);
addEdge(graph,8,6,2);
addEdge(graph,8,7,7);
struct AdjListNode* ptr;
printf("\nAdjacent List : \n\n");
for(int i=0;i<V;i++)
{
printf("%d : ",i);
ptr = graph->array[i].head;
while(ptr!=NULL)
{
printf("(%d, %d) -> ",ptr->dest,ptr->weight);
ptr = ptr->next;
}
printf("\n");
}
PrimMST(graph);
return 0;
}
OUTPUT :
Adjacent List :
0 : (7, 8) -> (1, 4) ->
1 : (7, 11) -> (2, 8) -> (0, 4) ->
2 : (8, 2) -> (5, 4) -> (3, 7) -> (1, 8) ->
3 : (5, 14) -> (4, 9) -> (2, 7) ->
4 : (5, 10) -> (3, 9) ->
5 : (6, 2) -> (4, 10) -> (3, 14) -> (2, 4) ->
6 : (8, 6) -> (7, 3) -> (5, 2) ->
7 : (8, 7) -> (6, 1) -> (1, 11) -> (0, 8) ->
8 : (7, 7) -> (6, 2) -> (2, 2) ->
MST :
0 - 1
5 - 2
2 - 3
3 - 4
6 - 5
7 - 6
//permutation
#include<stdio.h>
#include<stdlib.h>
int comparisons=0;
void swap_sort(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
comparisons++;
}
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int partition_lumoto(int *arr, int lo, int hi)
{
int pivot = arr[hi];
int i=lo-1;
for(int j=lo;j<hi;j++)
{
if(arr[j]<pivot)
{
i++;
swap_sort(&arr[i], &arr[j]);
}
}
swap_sort(&arr[i+1], &arr[hi]);
return (i+1);
}
void quicksort(int *arr, int lo, int hi)
{
if(lo<hi)
{
int q = partition_lumoto(arr,lo,hi);
quicksort(arr,lo,q-1);
quicksort(arr,q+1,hi);
}
}
int duplicate(int *arr, int lo, int hi)
{
for(int i=lo;i<hi;i++)
{
if(arr[i]==arr[hi])
return 0;
}
return 1;
}
void permute(int *arr, int lo, int hi)
{
int i, a[6]; //change value of a[6] here when increasing/decreasing array size
if(lo==hi)
{
printf("[");
for(i=0;i<=hi;i++){
//printf(" %d ", arr[i]);
a[i] = arr[i];}
for(i=0;i<=hi;i++)
printf(" %d ",a[i]);
printf("]\n");
quicksort(a,0,5); //change value of quicksort() here when increasing/decreasing array size
printf("[");
for(i=0;i<=hi;i++)
printf(" %d ",a[i]);
printf("]\n\n");
return;
}
else
{
for(i=lo;i<=hi;i++)
{
if(duplicate(arr,lo,hi))
{
swap(&arr[i], &arr[lo]);
permute(arr,lo+1,hi);
swap(&arr[i], &arr[lo]);
}
}
}
}
int main()
{
int arr[] = {1,2,3,4,5,6};
//quicksort(test,0,4);
permute(arr,0,5); //change value of permute() here when increasing/decreasing array size
printf("Total comparisons : %d", comparisons/120); //change factorial value accordingly
return 0;
}
// matrix multiplication
#include<stdio.h>
#include<stdlib.h>
int costMatrix[100][100]; //2-D array to store the cost for each pair of matrices
int parenthesis[100][100]; //2-D array to store the parenthesis for each pair of matrices
int multiplicationCost (int arr[], int i, int j)
{
if (i == j) //To multiply the same matrix the cost is 0
{
costMatrix[i][j] = 0;
parenthesis[i][j] = 0;
return 0;
}
int count;
int min = 100000; //Initialize the minimum cost to a large value
int min_parenthesis;
for (int k = i; k < j; k++) // k loops from i to j - 1 to represent the different position of the parenthesis
{
count = multiplicationCost(arr, i, k) + multiplicationCost(arr, k + 1, j) + arr[i - 1] * arr[k] * arr[j];
//recursive call to calculate the cost of multiplying the matrices from i to k and k + 1 to j
if (count < min) //update the minimum cost and the parenthesis position if a lower cost is discovered
{
min = count;
min_parenthesis = k;
}
}
parenthesis[i][j] = min_parenthesis; //store the parenthesis position
costMatrix[i][j] = min; //store the minimum cost
return min;
}
//function to print the parenthesis
void printParenthesis(int arr[], int i, int j)
{
if (i == j) //if only one matrix is left, print the matrix
{
printf(" A%d ", i);
return;
}
int k = parenthesis[i][j]; //get the parenthesis position
printf("("); //print the parenthesis
printParenthesis(arr, i, k); // Recursively put brackets around subexpression from i to k
printParenthesis(arr, k + 1, j); // Recursively put brackets around subexpression from k + 1 to j
printf(")"); //print the parenthesis
}
int main()
{
int arr[] = {100, 50, 30, 10}; //input array
int n = sizeof(arr) / sizeof(arr[0]); // size of array
printf ("\nThe input matrices are:\n");
for (int i = 0; i < n - 1; i++)
printf ("A%d: %d x %d\n", i + 1, arr[i] , arr[i + 1]);
//call the function to create the arrays
multiplicationCost(arr, 1, n - 1); //call the function to create the arrays
printf("\nCost Matrix:\n");
for (int i = 1; i < n; i++)
{
for (int j = 1; j < n; j++)
{
printf("%d\t", costMatrix[i][j]);
}
printf("\n");
}
printf("\nParenthesis Matrix:\n");
for (int i = 1; i < n; i++)
{
for (int j = 1; j < n; j++)
{
printf("%d\t", parenthesis[i][j]);
}
printf("\n");
}
printf ("\nThe minimum cost is %d", costMatrix[1][n - 1]);
printf ("\nThe optimal multiplication strategy is: ");
printParenthesis(arr, 1, n - 1); //call the function to print the parenthesis
printf("\n");
return 0;
}
Editor is loading...