// Dynamic
#include<iostream>
using namespace std;
#define MAT_S 3
#define LOOP_C 20

int mat[MAT_S][MAT_S] = { 1, 0, 1,
                     0, 1, 1,
 1, 0, 0 };
long long prv[MAT_S+1], cur[MAT_S+1];
long long set = 0;
int main()
{
int i, j,val;
for(i=0; i<=MAT_S; i++)
{
cur[i] = 0;
}
for (i = 0; i < MAT_S; i++)
{
val = 0;
for (j = 0; j < MAT_S; j++)
{
val += mat[i][j];
}
cur[val]++;
}
printf("\n\n\n Init level %2d total gin = %lld and state is:", 0, set);
for(j = 0; j<=MAT_S; j++)
{
printf("\ncur[%2d] = %lld", j, cur[j]);
}
for(i = 0; i< LOOP_C; i++)
{
for(j = 0; j<= MAT_S; j++)
{
prv[j] = cur[j];
cur[j] = 0;
}
cur[1] += (prv[0] * MAT_S);
for(j = 1; j< MAT_S; j++)
{
cur[j-1] += prv[j] * j;
cur[j+1] += prv[j] * (MAT_S - j);
}
cur[MAT_S -1] += (prv[MAT_S] * MAT_S);
set += prv[MAT_S -1];
printf("\n\n\nAfter level %2d total gin = %lld and state is:", i + 1, set);
for(j = 0; j<= MAT_S; j++)
{
printf("\ncur[%2d] = %lld", j, cur[j]);
}
}
printf("\n\n");
    return 0;
}

// A C / C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

#include <stdio.h>
#include <limits.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;

return min_index;
}

// A utility function to print the constructed distance array
int printSolution(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d \t\t %d\n", i, dist[i]);
}

// Funtion 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 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;

// 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 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];
}

// print the constructed distance array
printSolution(dist, V);
}

// 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, 0, 10, 0, 2, 0, 0},
{0, 0, 0, 14, 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;
}

// A C / C++ program for Prim's Minimum Spanning Tree (MST) algorithm. // The program is for adjacency matrix representation of the graph #include <stdio.h> #include <limits.h> // Number of vertices in the graph #define V 5 // A utility function to find the vertex with minimum key value, from // the set of vertices not yet included in MST int minKey(int key[], bool mstSet[]) {    // Initialize min value    int min = INT_MAX, min_index;    for (int v = 0; v < V; v++)      if (mstSet[v] == false && key[v] < min)          min = key[v], min_index = v;    return min_index; } // A utility function to print the constructed MST stored in parent[] int printMST(int parent[], int n, int graph[V][V]) {    printf("Edge   Weight\n");    for (int i = 1; i < V; i++)       printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]); } // Function to construct and print MST for a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) {      int parent[V]; // Array to store constructed MST      int key[V];   // Key values used to pick minimum weight edge in cut      bool mstSet[V];  // To represent set of vertices not yet included in MST      // Initialize all keys as INFINITE      for (int i = 0; i < V; i++)         key[i] = INT_MAX, mstSet[i] = false;      // Always include first 1st vertex in MST.      key[0] = 0;     // Make key 0 so that this vertex is picked as first vertex      parent[0] = -1; // First node is always root of MST      // The MST will have V vertices      for (int count = 0; count < V-1; count++)      {         // Pick thd minimum key vertex from the set of vertices         // not yet included in MST         int u = minKey(key, mstSet);         // Add the picked vertex to the MST Set         mstSet[u] = true;         // Update key value and parent index of the adjacent vertices of         // the picked vertex. Consider only those vertices which are not yet         // included in MST         for (int v = 0; v < V; v++)            // graph[u][v] is non zero only for adjacent vertices of m            // mstSet[v] is false for vertices not yet included in MST            // Update the key only if graph[u][v] is smaller than key[v]           if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])              parent[v]  = u, key[v] = graph[u][v];      }      // print the constructed MST      printMST(parent, V, graph); } // driver program to test above function int main() {    /* Let us create the following graph           2    3       (0)--(1)--(2)        |   / \   |       6| 8/   \5 |7        | /     \ |       (3)-------(4)             9          */    int graph[V][V] = {{0, 2, 0, 6, 0},                       {2, 0, 3, 8, 5},                       {0, 3, 0, 0, 7},                       {6, 8, 0, 0, 9},                       {0, 5, 7, 9, 0},                      };     // Print the solution     primMST(graph);     return 0; } // A C / C++ program for Bellman-Ford's single source shortest path algorithm. #include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.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[V];     // 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] != INT_MAX && 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] != INT_MAX && 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);     return 0; } // A C++ program to print topological sorting of a DAG #include<iostream> #include <list> #include <stack> using namespace std; // Class to represent a graph class Graph {     int V;    // No. of vertices'     // Pointer to an array containing adjacency listsList     list<int> *adj;     // A function used by topologicalSort     void topologicalSortUtil(int v, bool visited[], stack<int> &Stack); public:     Graph(int V);   // Constructor      // function to add an edge to graph     void addEdge(int v, int w);     // prints a Topological Sort of the complete graph     void topologicalSort(); }; 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. } // A recursive function used by topologicalSort void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack) {     // Mark the current node as visited.     visited[v] = true;     // 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])             topologicalSortUtil(*i, visited, Stack);     // Push current vertex to stack which stores result     Stack.push(v); } // The function to do Topological Sort. It uses recursive topologicalSortUtil() void Graph::topologicalSort() {     stack<int> Stack;     // Mark all the vertices as not visited     bool *visited = new bool[V];     for (int i = 0; i < V; i++)         visited[i] = false;     // Call the recursive helper function to store Topological Sort     // starting from all vertices one by one     for (int i = 0; i < V; i++)       if (visited[i] == false)         topologicalSortUtil(i, visited, Stack);     // Print contents of stack     while (Stack.empty() == false)     {         cout << Stack.top() << " ";         Stack.pop();     } } // Driver program to test above functions int main() {     // Create a graph given in the above diagram     Graph g(6);     g.addEdge(5, 2);     g.addEdge(5, 0);     g.addEdge(4, 0);     g.addEdge(4, 1);     g.addEdge(2, 3);     g.addEdge(3, 1);     cout << "Following is a Topological Sort of the given graph \n";     g.topologicalSort();     return 0; } // 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 list<int> *adj; // Pointer to an array containing adjacency lists public: Graph(int V); // Constructor void addEdge(int v, int w); // function to add an edge to graph void BFS(int s); // prints BFS traversal from a given source 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++) 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 a adjacent has not been visited, then mark it visited // and enqueue it for(i = adj[s].begin(); i != adj[s].end(); ++i) { 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"; g.BFS(2); return 0; }