Hamiltonion Cycle

// hamiltionian cycle - backtracking

#include<stdio.h>
#include<conio.h>

// ttl vertices
#define V 5
void printSolution(int path[]);

bool isSafe(int v, bool graph[V][V], int path[], int pos)
{
        // check if added vertex is adjacent vertex of previously added vertex
    if (graph[path[pos - 1]][v] == 0)
        return false;

    // check if vertex has already been included
    for (int i = 0; i < pos; ++i)
    if (path[i] == v) return false;

    return true;
}

bool hamCycleUtil(bool graph[V][V], int path[], int pos)
{
    //base case
    if (pos == V)
    {
        if (graph[path[pos - 1]][path[0]] == 1) // if there exist an edge bw last included to firstvertex
            return true;
        else
            return false;


    }

    //try different verticies as next candidate in hamiltonian cycle
    for (int v = 1; v < V; ++v)
    {
        if (isSafe(v, graph, path, pos))
        {
            path[pos] = v;
            //recur to contruct rest of the path
            if (hamCycleUtil(graph, path, pos + 1) == true)
                return true;

            //else backtrack
            path[pos - 1];
        }

    }

    //if no vertex can be added to cycle ,return false
    return false;
}


bool hamCycle(bool graph[V][V])
{
    int *path = new int[V];
    for (int i = 0; i < V; i++)
        path[i] = -1;

    /* Let us put vertex 0 as the first vertex in the path. If there is
    a Hamiltonian Cycle, then the path can be started from any point
    of the cycle as the graph is undirected */
    path[0] = 0;
    if (hamCycleUtil(graph, path, 1) == false)
    {
        printf("\nSolution does not exist");
        return false;
    }

    printSolution(path);
    return true;
}

/* A utility function to print solution */
void printSolution(int path[])
{
    printf("Solution Exists:"
        " Following is one Hamiltonian Cycle \n");
    for (int i = 0; i < V; i++)
        printf(" %d ", path[i]);

    //  print the first vertex again to show the complete cycle
    printf(" %d ", path[0]);
    printf("\n");
}

// driver program to test above function
int main()
{
    /* Let us create the following graph
    (0)--(1)--(2)
    |   / \   |
    |  /   \  |
    | /     \ |
    (3)-------(4)    */
    bool graph1[V][V] = { { 0, 1, 0, 1, 0 },
    { 1, 0, 1, 1, 1 },
    { 0, 1, 0, 0, 1 },
    { 1, 1, 0, 0, 1 },
    { 0, 1, 1, 1, 0 },
    };

    // Print the solution
    hamCycle(graph1);

    /* Let us create the following graph
    (0)--(1)--(2)
    |   / \   |
    |  /   \  |
    | /     \ |
    (3)       (4)    */
    bool graph2[V][V] = { { 0, 1, 0, 1, 0 },
    { 1, 0, 1, 1, 1 },
    { 0, 1, 0, 0, 1 },
    { 1, 1, 0, 0, 0 },
    { 0, 1, 1, 0, 0 },
    };

    // Print the solution
    hamCycle(graph2);
    getchar();
    return 0;
}

Back Tracking - m coloring problem

#include<stdio.h>

//total vertices of ours graph
#define V 4

void printSol(int color[]);




// utility function to check whther assighning a color to vertex is safe
bool isSafe(int v, bool graph[V][V], int color[], int c)
{
    //check for adjacent vertices which dont have same color as 'c'
    for (int i = 0; i < V; ++i)
    {
        if (graph[v][i] && c == color[i])
            return false ;
    }
    return true;
}

//recursive util to solve m coloring prblm

bool graphColornUtil(bool graph[V][V], int m, int color[], int v)
{
    //base case if all vertices are colored
    if (v == V)
        return true;

    //consider all colors for this vertex v
    for (int c = 1; c <= m; ++c)
    {
        if (isSafe(v, graph, color,c))
        {
            color[v] = c;
            if (graphColornUtil(graph, m, color, v + 1) == true)
                return true;
            //backtrack
            color[v] = 0;

        }
    }

    return false; // if no color can be assighned
}


bool graphColoring(bool graph[V][V], int m)
{
    // Initialize all color values as 0. This initialization is needed
    // correct functioning of isSafe()
    int *color = new int[V];
    for (int i = 0; i < V; i++)
        color[i] = 0;

    // Call graphColoringUtil() for vertex 0
    if (graphColornUtil(graph, m, color, 0) == false)
    {
        printf("Solution does not exist");
        return false;
    }

    // Print the solution
    printSol(color);
    return true;
}

/* function to print solution */
void printSol(int color[])
{
    printf("Sol Exists:"
        " Following r the assigned colors \n");
    for (int i = 0; i < V; i++)
        printf(" %d ", color[i]);
    printf("\n");
}

// driver program to test above function
int main()
{
    /* Create following graph and test whether it is 3 colorable
    (3)---(2)
    |      /   |
    |    /     |
    | /       |
    (0)---(1)
    */

    //adjaceny matrix
    bool graph[V][V] = { { 0, 1, 1, 1 },
    { 1, 0, 1, 0 },
    { 1, 1, 0, 1 },
    { 1, 0, 1, 0 },
    };
    int m = 3; // Number of colors
    graphColoring(graph, m);
    getchar();
    return 0;
}

Bellman-Ford's single source shortest path algorithm

// program for Bellman-Ford's single source shortest path algorithm.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include<conio.h>

// a structure to represent a weighted edge in graph
struct Edge
{
    int src, dest, weight;
};

// a structure to represent a connected, directed and weighted graph
struct Graph
{
    // V-> Number of vertices, E-> Number of edges
    int V, E;

    // graph is represented as an array of edges.
    struct Edge* edge;
};

// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;

    graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));

    return graph;
}

// A utility function used to print the solution
void printArr(int dist[], int n)
{
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < n; ++i)
        printf("%d \t\t %d\n", i, dist[i]);
}

// The main function that finds shortest distances from src to all other
// vertices using Bellman-Ford algorithm.  The function also detects negative
// weight cycle
void BellmanFord(struct Graph* graph, int src)
{
    int V = graph->V;
    int E = graph->E;
    int dist[5];

    // Step 1: Initialize distances from src to all other vertices as INFINITE
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX;
    dist[src] = 0;

    // Step 2: Relax all edges |V| - 1 times. A simple shortest path from src
    // to any other vertex can have at-most |V| - 1 edges
    for (int i = 1; i <= V - 1; i++)
    {
        for (int j = 0; j < E; j++)
        {
            int u = graph->edge[j].src;
            int v = graph->edge[j].dest;
            int weight = graph->edge[j].weight;
            if (dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }

    // Step 3: check for negative-weight cycles.  The above step guarantees
    // shortest distances if graph doesn't contain negative weight cycle. 
    // If we get a shorter path, then there is a cycle.
    for (int i = 0; i < E; i++)
    {
        int u = graph->edge[i].src;
        int v = graph->edge[i].dest;
        int weight = graph->edge[i].weight;
        if (dist[u] + weight < dist[v])
            printf("Graph contains negative weight cycle");
    }

    printArr(dist, V);

    return;
}

// Driver program to test above functions
int main()
{
    /* Let us create the graph given in above example */
    int V = 5;  // Number of vertices in graph
    int E = 8;  // Number of edges in graph
    struct Graph* graph = createGraph(V, E);

    // add edge 0-1 (or A-B in above figure)
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = -1;

    // add edge 0-2 (or A-C in above figure)
    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 4;

    // add edge 1-2 (or B-C in above figure)
    graph->edge[2].src = 1;
    graph->edge[2].dest = 2;
    graph->edge[2].weight = 3;

    // add edge 1-3 (or B-D in above figure)
    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 2;

    // add edge 1-4 (or A-E in above figure)
    graph->edge[4].src = 1;
    graph->edge[4].dest = 4;
    graph->edge[4].weight = 2;

    // add edge 3-2 (or D-C in above figure)
    graph->edge[5].src = 3;
    graph->edge[5].dest = 2;
    graph->edge[5].weight = 5;

    // add edge 3-1 (or D-B in above figure)
    graph->edge[6].src = 3;
    graph->edge[6].dest = 1;
    graph->edge[6].weight = 1;

    // add edge 4-3 (or E-D in above figure)
    graph->edge[7].src = 4;
    graph->edge[7].dest = 3;
    graph->edge[7].weight = -3;

    BellmanFord(graph, 0);
    getchar();
    return 0;
}

Warshall Algorithm - All pairs shortest path

//programme for floyd warshall algroithms -  all pair shortest path 
// Complexity - O(V ^ 3) where V is total vertices
#include<stdio.h>
#include<conio.h>

//number of vertices in ours graphh 
#define V 4 

/*
* Define Indefinite as large as possible to represent vertices
* not connected to eachother
*/

#define INF 99999

// a function to print solution matrix of  all pair shortest paths
void printSolution(int dist[][V]);

//solves the all- pair shortest path problem 
void floydWarshell(int graph[][V]){

//dist[][] will be the output matrix tht will  have shortest
//path 
int dist[V][V], i, j, k;

//initial solution matrix same as graph matrix
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];

for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
// If vertex k is on the shortest path from
// i to j, then update the value of dist[i][j]
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}

// Print the shortest distance matrix
printSolution(dist);








}


void printSolution(int dist[][V])
{
printf("Following matrix shows the shortest distances"
" between every pair of vertices \n");
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (dist[i][j] == INF)
printf("%7s", "INF");
else
printf("%7d", dist[i][j]);
}
printf("\n");
}
}



int main()
{
/* create the following weighted graph
     10
(0)------->(3)
|             /|\
   5   |              |1
|              | 
       \|/             |
      (1)------->(2)
     3         
 
*/
int graph[V][V] = 
{
{ 0, 5, INF, 10 },
{ INF, 0, 3, INF },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 }
};

// Print the solution
floydWarshell(graph);
getchar();
return 0;
}