Today we revisit a few graph algorithms.
The breadth first search
BFS(G,s)
 for each vertex, initialize color, parent and distance
 set the start vertex color to gray
 enqueue the start vertex
 while the queue is not empty
       for each of the adjacent vertices of the dequeued vertex
        if its not been visited
               color the vertex as gray and set its parent and distance
               enqueue this vertex
       color the vertex as visited

DFS(G)
for each vertex u belonging to the graph, initialize it
for each vertex u belonging to the graph,
      if color of vertex is white,
          DFS-Visit(the vertex)

DFS-Visit(G,u)
for each adjacent vertex
     DFS-Visit(G,u)

MST-Kruskal
// This joins two distinct trees
A = null
for each vertex v in G
     Make-Set(v)
sort the edges of G, E into non-decreasing order by weight
for each such edge (u,v)
     if Find-set(u) <> Find-set(v)
        A = A union (u,v)
         Union(u,v)
return A

MST-Prim
// this grows a tree
A = null
for each vertex v in G, initialize the key and the parent
Initialize a min-priority queue Q with vertices
while the Queue is not empty
       extract the vertex with the minimum edge distance connecting it to the tree
       for each adjacencies v of this vertex u
              set the key to the weight(u,v) and parent

Dijkstra's shortest path algorithm
Other than source vertex, mark all as max distance no parent
Initialize a min-priority queue Q with vertices
while the Queue is not empty
     extract the minimum vertex u of Q
             add it to the shortest path
             for all vertices adjacent to u,
                   relax the vertices

All-Pairs-shortest-path (predecessor matrix, src, dest)
if src==dest
    print src
else if parent(dest) == null
    print "no path"
else all-pairs-shortest-path(predecessor matrix, I, parent-srcdest)
    print dest

Floyd-Warshall gives shortest path weighs matrix
dij with no intermediary vertices  =  edge weight
        = min(dij k-1 , dik k-1 + djk k-1 ) when # intermediary vertices k >=1

for k = 1 to n
   D for k be a new nxn matrix
   for I = 1 to n
      for j = 1 to n
         dij(k) = min(dij(k-1), dik(k-1) + dkj(k-1))

return Dn

int BuyOrSellOnce(List<int> prices, ref int start, ref int end)
{
int min = 0;
int min_index = start;
int max_index = start;
int max_profit = -1;
for (int i = start; i < end; i++)
{
if (prices[i] < min)
     min = prices[i]
if (prices[i] - min > max_profit){
    max_profit = prices[i] - min;
    max_index = i;
   }
}
start = max_index+1;
end = prices.Count -1;
return max_profit;
}
int BuyOrSellManyTimes(List<int>prices)
{
int start = 0;
int end = prices.Count-1;
int max_profit = -1;
int profit = BuyOrSellOnce(prices, start, end);
while (profit != -1) {
max_profit += profit;
profit == BuyOrSellOnce(prices, start, end);
}
return max_profit;
}

int main() {
//code
int* p = new int[5];
p[0] = 3;
p[1] = 1;
p[2] = 2;
p[3] = 4;
p[4] = 5;
printf(getminindex(p,5))
return 0;
}


int getminindex(int[] p, int n)
{
int min = 0;
for (int i = 0; i < n; i++ )
   for (int j = i+1; j < n; j++)
   {
     if (p[j] >= p[i] && j - i > min)
            min = j-i;
   }
return min;

}