1.BFS 2.DFS 3.

Traveling salesman problem

#include <stdio.h> #include <stdio.h> #include <stdio.h>
#include <stdbool.h> #include <stdbool.h> #include <limits.h>
#define MAX_VERTICES 5 #define MAX_VERTICES 5 #define MAX_CITIES 10
void bfs(int void dfs(int int tsp(int graph[MAX_CITIES][MAX_CITIES], int visited[], int
graph[MAX_VERTICES][MAX_VERTICES], graph[MAX_VERTICES][MAX_VERTICES], pos, int n, int count, int cost, int ans) {
int startVertex, int numVertices) { int vertex, bool visited[], int numVertices) { if (count == n && graph[pos][0]) {
bool visited[MAX_VERTICES] = {false}; visited[vertex] = true; return (cost + graph[pos][0] < ans) ? cost + graph[pos][0] : ans;
int queue[MAX_VERTICES], front = 0, rear = printf("Visited %d\n", vertex); }
0; for (int i = 0; i < numVertices; i++) { for (int i = 0; i < n; i++) {
visited[startVertex] = true; if (graph[vertex][i] == 1 && !visited[i]) { if (!visited[i] && graph[pos][i]) {
queue[rear++] = startVertex; dfs(graph, i, visited, numVertices); visited[i] = 1;
while (front < rear) { } }} ans = tsp(graph, visited, i, n, count + 1, cost + graph[pos][i],
int currentVertex = queue[front++]; int main() { ans);
printf("Visited %d\n", currentVertex); int visited[i] = 0;
for (int i = 0; i < numVertices; i++) { graph[MAX_VERTICES][MAX_VERTICES] } }
if (graph[currentVertex][i] == 1 && ={ return ans;
!visited[i]) { {0, 1, 1, 0, 0}, }
visited[i] = true; {1, 0, 0, 1, 1}, int main() {
queue[rear++] = i; {1, 0, 0, 0, 1}, int graph[MAX_CITIES][MAX_CITIES] = {
} } }} {0, 1, 0, 0, 0}, {0, 10, 15, 20},
int main() { {0, 1, 1, 0, 0} {10, 0, 35, 25},
intgraph[MAX_VERTICES][MAX_VERTICES] }; {15, 35, 0, 30},
={ bool visited[MAX_VERTICES] = { false }; {20, 25, 30, 0}
{0, 1, 1, 0, 0}, printf("Depth-First Search starting from };
{1, 0, 0, 1, 1}, vertex 0:\n"); int visited[MAX_CITIES] = {0};
{1, 0, 0, 0, 1}, dfs(graph, 0, visited, MAX_VERTICES); visited[0] = 1;
{0, 1, 0, 0, 0}, return 0; int ans = INT_MAX;
{0, 1, 1, 0, 0} } ans = tsp(graph, visited, 0, 4, 1, 0, ans);
}; printf("Minimum cost of visiting all cities: %d\n", ans);
return 0;
printf("Breadth-First Search starting from }
vertex 0:\n"); 4. Insertion Sort
bfs(graph, 0, MAX_VERTICES); #include <stdio.h>
void insertionSort(int arr[], int n) { 6.Prim's Algorithm
for (int i = 1; i < n; i++) { #include <stdio.h>
return 0; #include <limits.h>
} int key = arr[i];
int j = i - 1; #define V 5
while (j >= 0 && arr[j] > key) { int minKey(int key[], int mstSet[]) {
arr[j + 1] = arr[j]; int min = INT_MAX, min_index;
5. Linear Search j--; for (int v = 0; v < V; v++) {
#include <stdio.h> } if (mstSet[v] == 0 && key[v] < min) {
int linearSearch(int arr[], int n, int key) { arr[j + 1] = key; min = key[v];
for (int i = 0; i < n; i++) { } min_index = v;
if (arr[i] == key) return i; } } }
} int main() { return min_index;
return -1; int arr[] = {12, 11, 13, 5, 6}; }
} int n = sizeof(arr) / sizeof(arr[0]); void primMST(int graph[V][V]) {
int main() { insertionSort(arr, n); int parent[V], key[V];
int arr[] = {2, 3, 4, 10, 40}; for (int i = 0; i < n; i++) printf("%d ", int mstSet[V];
int n = sizeof(arr) / sizeof(arr[0]); arr[i]); for (int i = 0; i < V; i++) {
int key = 10; return 0; key[i] = INT_MAX;
int result = linearSearch(arr, n, key); } mstSet[i] = 0;
printf("Element found at index: %d\n", }
result); key[0] = 0;
return 0; parent[0] = -1;
} 7. Matrix Multiplication for (int count = 0; count < V - 1; count++) {
#include <stdio.h> int u = minKey(key, mstSet);
#define MAX 10 mstSet[u] = 1;
void multiplyMatrices(int for (int v = 0; v < V; v++) {
12.Pattern Search first[MAX][MAX], int if (graph[u][v] && mstSet[v] == 0 &&
#include <stdio.h> second[MAX][MAX], int graph[u][v] < key[v]) {
#include <string.h> result[MAX][MAX], int r1, int c1, int r2, parent[v] = u;
int c2) { key[v] = graph[u][v];
void search(char* text, char* pattern) { for (int i = 0; i < r1; i++) }
int M = strlen(pattern); for (int j = 0; j < c2; j++) { }
int N = strlen(text); result[i][j] = 0; }
for (int i = 0; i <= N - M; i++) { for (int k = 0; k < c1; k++)
int j; result[i][j] += first[i][k] * printf("Edge \tWeight\n");
for (j = 0; j < M; j++) second[k][j]; for (int i = 1; i < V; i++)
if (text[i + j] != pattern[j]) break; } } printf("%d - %d \t%d\n", parent[i], i,
if (j == M) printf("Pattern found at int main() { graph[i][parent[i]]);
index %d\n", i); int first[MAX][MAX] = {{1, 2, 3}, {4, 5, }
} 6}};
} int second[MAX][MAX] = {{7, 8}, {9, int main() {
10}, {11, 12}}; int graph[V][V] = {
int main() { int result[MAX][MAX]; {0, 2, 0, 6, 0},
char text[] = multiplyMatrices(first, second, result, 2, {2, 0, 3, 8, 5},
"ABABDABACDABABCABAB"; 3, 3, 2); {0, 3, 0, 0, 7},
char pattern[] = "ABABCABAB"; for (int i = 0; i < 2; i++) { {6, 8, 0, 0, 9},
search(text, pattern); for (int j = 0; j < 2; j++) {0, 5, 7, 9, 0}
return 0; printf("%d ", result[i][j]); };
} printf("\n"); primMST(graph);
} return 0;
return 0; }
}
 8. Floyd’s Algorithm 9. Kth Smallest Number 11. N-Queens
#include <stdio.h> #include <stdio.h> #include <stdio.h>
#include <limits.h> #include <stdlib.h> #include <stdbool.h>
#define V 4 int partition(int arr[], int left, int right) { #define N 4
void floydWarshall(int graph[V][V]) { int pivot = arr[right]; void printSolution(int board[N][N]) {
int dist[V][V]; int i = left - 1; for (int i = 0; i < N; i++) {
for (int i = 0; i < V; i++) for (int j = left; j < right; j++) { for (int j = 0; j < N; j++)
for (int j = 0; j < V; j++) if (arr[j] < pivot) { printf(" %d ", board[i][j]);
dist[i][j] = graph[i][j]; i++; printf("\n");
for (int k = 0; k < V; k++) int temp = arr[i]; } }
for (int i = 0; i < V; i++) arr[i] = arr[j]; bool isSafe(int board[N][N], int row, int col) {
for (int j = 0; j < V; j++) arr[j] = temp; for (int i = 0; i < col; i++)
if (dist[i][k] + dist[k][j] < } } if (board[row][i]) return false;
dist[i][j]) int temp = arr[i + 1]; for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
dist[i][j] = dist[i][k] + arr[i + 1] = arr[right]; if (board[i][j]) return false;
dist[k][j]; arr[right] = temp; for (int i = row, j = col; j >= 0 && i < N; i++, j--)
printf("Shortest distances between every return i + 1; if (board[i][j]) return false;
pair of vertices:\n"); } return true;
for (int i = 0; i < V; i++) { int kthSmallest(int arr[], int left, int right, int k) }
for (int j = 0; j < V; j++) { bool solveNQUtil(int board[N][N], int col) {
printf("%d ", dist[i][j]); if (k > 0 && k <= right - left + 1) { if (col >= N) return true;
printf("\n"); int index = partition(arr, left, right); for (int i = 0; i < N; i++) {
} } if (index - left == k - 1) if (isSafe(board, i, col)) {
int main() { return arr[index]; board[i][col] = 1;
int graph[V][V] = { if (index - left > k - 1) if (solveNQUtil(board, col + 1)) return true;
{0, 5, INT_MAX, 10}, return kthSmallest(arr, left, index - 1, k); board[i][col] = 0; // Backtrack
{INT_MAX, 0, 3, INT_MAX}, return kthSmallest(arr, index + 1, right, k - } }
{INT_MAX, INT_MAX, 0, 1}, index + left - 1); return false;
{INT_MAX, INT_MAX, INT_MAX, } }
0} return INT_MAX; void solveNQ() {
}; } int board[N][N] = {0};
floydWarshall(graph); int main() { if (!solveNQUtil(board, 0)) {
return 0; int arr[] = {12, 3, 5, 7, 19}; printf("Solution does not exist");
} int n = sizeof(arr) / sizeof(arr[0]); return;
int k = 2; }
printf("Kth smallest element is %d\n", printSolution(board);
kthSmallest(arr, 0, n - 1, k)); }
10. Quick Sort return 0;
#include <stdio.h> } int main() {
int partition(int arr[], int low, int high) { solveNQ();
int pivot = arr[high]; return 0;
int i = (low - 1); }
13. Heap Sort
for (int j = low; j < high; j++) { #include <stdio.h>
if (arr[j] < pivot) { void swap(int* a, int* b) {
i++; int temp = *a;
int temp = arr[i];
*a = *b; 14. Merge Sort
arr[i] = arr[j];
*b = temp; #include <stdio.h>
arr[j] = temp;
} void merge(int arr[], int l, int m, int r) {
} }
void heapify(int arr[], int n, int i) { int i, j, k;
int temp = arr[i + 1]; int largest = i, left = 2 * i + 1, right = 2 * i + int n1 = m - l + 1;
arr[i + 1] = arr[high]; 2; int n2 = r - m;
arr[high] = temp;
if (left < n && arr[left] > arr[largest]) int L[n1], R[n2];
return i + 1;
largest = left; for (i = 0; i < n1; i++) L[i] = arr[l + i];
}
if (right < n && arr[right] > arr[largest]) for (j = 0; j < n2; j++) R[j] = arr[m + 1 +
void quickSort(int arr[], int low, int high) { largest = right; j];
if (low < high) { if (largest != i) { i = 0; j = 0; k = l;
int pi = partition(arr, low, high); swap(&arr[i], &arr[largest]); while (i < n1 && j < n2) {
quickSort(arr, low, pi - 1); heapify(arr, n, largest); if (L[i] <= R[j]) arr[k++] = L[i++];
quickSort(arr, pi + 1, high);
} } else arr[k++] = R[j++];
} }
void heapSort(int arr[], int n) { }
int main() {
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, while (i < n1) arr[k++] = L[i++];
int arr[] = {10, 7, 8, 9, 1, 5}; n, i); while (j < n2) arr[k++] = R[j++];
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = n - 1; i >= 0; i--) { }
quickSort(arr, 0, n - 1);
swap(&arr[0], &arr[i]); void mergeSort(int arr[], int l, int r) {
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
heapify(arr, i, 0); if (l < r) {
return 0;
} } int m = l + (r - l) / 2;
}
int main() { mergeSort(arr, l, m);
int arr[] = {12, 11, 13, 5, 6, 7}; mergeSort(arr, m + 1, r);
int n = sizeof(arr) / sizeof(arr[0]); merge(arr, l, m, r);
heapSort(arr, n); } }
for (int i = 0; i < n; i++) printf("%d ", arr[i]); int main() {
return 0; int arr[] = {12, 11, 13, 5, 6, 7};
} int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) printf("%d ",
arr[i]);
return 0;
}
15. Binary Search 16.Warshall’s Algorithm
#include <stdio.h> #include <stdio.h>
int binarySearch(int arr[], int left, int right, int x) #define V 4
{ void warshall(int graph[V][V]) {
while (left <= right) { int reach[V][V];
int mid = left + (right - left) / 2; for (int i = 0; i < V; i++)
if (arr[mid] == x) return mid; for (int j = 0; j < V; j++)
if (arr[mid] < x) left = mid + 1; reach[i][j] = graph[i][j];
else right = mid - 1; for (int k = 0; k < V; k++)
} for (int i = 0; i < V; i++)
return -1; for (int j = 0; j < V; j++)
} reach[i][j] = reach[i][j] || (reach[i][k] &&
int main() { reach[k][j]);
int arr[] = {2, 3, 4, 10, 40}; printf("Transitive closure of the given graph:\n");
int n = sizeof(arr) / sizeof(arr[0]); for (int i = 0; i < V; i++) {
int x = 10; for (int j = 0; j < V; j++)
int result = binarySearch(arr, 0, n - 1, x); printf("%d ", reach[i][j]);
printf("Element found at index: %d\n", printf("\n");
result); } }
return 0; int main() {
} int graph[V][V] = {
{0, 1, 0, 1},
{0, 0, 1, 0},
{1, 0, 0, 1},
{0, 0, 0, 0}
};
warshall(graph);
return 0;
}

18. Dijkstra’s algorithm

#include <stdio.h>
#include <limits.h>
17. Quick Sort with Time Analysis
#include <stdio.h> #define V 5
#include <time.h> int minDistance(int dist[], int sptSet[]) {
int partition(int arr[], int low, int high) { int min = INT_MAX, min_index;
int pivot = arr[high]; for (int v = 0; v < V; v++) {
int i = (low - 1); if (sptSet[v] == 0 && dist[v] < min) {
for (int j = low; j < high; j++) { min = dist[v];
if (arr[j] < pivot) { min_index = v;
i++; } }
int temp = arr[i]; return min_index;
arr[i] = arr[j]; }
arr[j] = temp; void dijkstra(int graph[V][V], int src) {
} int dist[V]; // Output array. dist[i] holds the shortest
} distance from src to i
int temp = arr[i + 1]; int sptSet[V]; // Shortest path tree set
arr[i + 1] = arr[high]; for (int i = 0; i < V; i++) {
arr[high] = temp; dist[i] = INT_MAX;
return i + 1; sptSet[i] = 0;
} }
void quickSort(int arr[], int low, int high) { dist[src] = 0; // Distance from source to itself is always
if (low < high) { 0
int pi = partition(arr, low, high); for (int count = 0; count < V - 1; count++) {
quickSort(arr, low, pi - 1); int u = minDistance(dist, sptSet); // Get the vertex
quickSort(arr, pi + 1, high); with the minimum distance
} sptSet[u] = 1; // Mark the picked vertex as processed
} for (int v = 0; v < V; v++) {
int main() { if (!sptSet[v] && graph[u][v] && dist[u] !=
int arr[] = {10, 7, 8, 9, 1, 5}; INT_MAX && dist[u] + graph[u][v] < dist[v]) {
int n = sizeof(arr) / sizeof(arr[0]); dist[v] = dist[u] + graph[u][v];
clock_t start = clock(); } } }
quickSort(arr, 0, n - 1); printf("Vertex \t Distance from Source\n");
clock_t end = clock(); for (int i = 0; i < V; i++)
for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("%d \t %d\n", i, dist[i]);
printf("\nTime taken: %lf seconds\n", (double)(end - start) }
/ CLOCKS_PER_SEC); int main() {
return 0; int graph[V][V] = {
} {0, 10, 0, 30, 100},
{10, 0, 50, 0, 0},
{0, 50, 0, 20, 10},
{30, 0, 20, 0, 60},
{100, 0, 10, 60, 0}
};
dijkstra(graph, 0);
return 0;
}