FW-UnWheighted(g[N,N]) : for k=0 to N : for i=0 to N : for j=0 to N : g[i,j] = g[i,j] || (g[i,k] AND g[k,j])

FW-wheighted(g[N,N]) : for k=0 to N : for i=0 to N : for j=0 to N : if g[i,j] > g[i,k] + g[k,j] : g[i,j] = g[i,k] + g[k,j]

FW-wheighted-paths(g[N,N]) : New empty-string paths[N,N] for i=0 to N : for j=0 to N : paths[i,j] = i + "->" + j for k=0 to N : for i=0 to N : for j=0 to N : if g[i,j] > g[i,k] + g[k,j] : g[i,j] = g[i,k] + g[k,j] paths[i,j] = paths[i,k] + "->" + paths[k,j] return paths

isConnected-UnDirected-graphs(g[N,N]) : FW(g) for i=1 to N : if g[0,i] = false : return false return true

isConnected-Directed-graphs(g[N,N]) : FW(g) for i=0 to N : if g[0,i] = ∞ : return false return true

Has-Negative-Cycles-Directed(g[N,N]) : FW(g) for i=0 to N : if g[i,i] < 0 : return true return false

Has-Negative-Cycles-UnDirected(g[N,N]) : for i=0 to N : for j=0 to N : if g[i,j] < 0: return true return false

Degrees-of-vertices(g[N,N]) : New D[N] = {0,0,..,0} for i=0 to N : for j=0 to N : if i ≠ j AND g[i,j] ≠ ∞: D[i]++ D[j]++ sort(D) return D

Degrees-of-vertices(g[N,N]) : New D[N] = {0,0,..,0} for i=0 to N : for j=0 to N : if g[i,j] = true: D[i]++ D[j]++ sort(D) return D

Bottles-Problem(b1, b2) : mat = Bottles-Problem-Create-Matrix(b1, b2) return Bottles-Problem-Get-Paths(mat, max(b1, b2))

Bottles-Problem-Create-Matrix(b1, b2) : size = (b1+1)*(b2+1) max = max(b1, b2) new mat[size, size] for i=0 to b1 : for j=0 to b2 : index = getindex(max, i, j) 1. mat[index, getIndex(max, 0, j)] = 1 2. mat[index, getIndex(max, i, 0)] = 1 3. mat[index, getIndex(max, b1, j)] = 1 4. mat[index, getIndex(max, i, b2)] = 1 5. mat[index, getIndex(max, min(b1, i+j), i+j-min(b1, i+j))] = 1 6. mat[index, getIndex(max, i+j-min(b2, i+j) , min(b2, i+j))] = 1 return mat getIndex(n, i, j) : return (n+1) * i + j

Bottles-Problem-Get-Paths(mat[size, size], n) : New paths[size, size] for i=0 to size : x1, y1 = getPairFromIndex(n, i) for j=0 to size : x2, y2 = getPairFromIndex(n, i) if mat[i, j] ≠ ∞ : paths[i, j] = "("+x1+","+y1+") → ("+x2+","+y2+")" for k=0 to size : for i=0 to size : for j=0 to size : if mat[i,j] > mat[i,k] + mat[k,j] : mat[i,j] = mat[i,k] + mat[k,j] paths[i,j] = paths[i,k] + "→" + paths[k,j] return paths getPairFromIndex(n, i) : return { i/(n+1), i%(n+1) }

Best-basic(A[N]) : maxSum = tempSum = -∞ for i=0 to N : tempSum += A[i] maxSum = max(maxSum, tempSum) tempSum = max(tempSum, 0) return maxSum

Best(A[N]) : maxSum = tempSum = -∞ start = end = 0 for i=0 to N : tempSum += A[i] if maxSum < tempSum : maxSum = tempSum end = i if tempSum < 0: tempSum = 0 start = i+1 return {maxSum, start, end}

Best-Cycle(A[N]) : totalSum = sum(A) return max(Best(A), totalSum - Best(-A))

Best-Cycle(A[N]) : totalSum = sum(A) max1, start1, end1 = Best(A) max2, start2, end2 = Best(-A) if max1 > totalSum + max2 : return {max1, start1, end1} else return {totalSum + max2, end2 + 1, start2 - 1}

Gas-Stations-Problem(A[N], B[N]) : C[N] sum = 0 for i=0 to N : C[i] = A[i] - B[i] sum += C[i] if sum < 0 : return "No solution" return Best-Cycle(C)

Super-Best-basic(A[rows,cols]): maxSum = 0 for i=0 to rows : New help[cols] for j=i to rows : for k=0 to cols : help[k] += A[j,k] maxSum = max(maxSum, Best-basic(help)) return maxSum

Super-Best(A[rows,cols]) : maxSum, start_x, start_y ,end_x, end_y = 0 for i=0 to rows : New help[cols] for j=i to rows : for k=0 to cols : help[k] += A[j,k] tempSum, tempStart, tempEnd = best(help) if maxSum < tempSum : maxSum = tempSum start_x = tempStart end_x = tempEnd start_y = i end_y = j return {maxSum, start_x, start_y, end_x, end_y}

Huffman(C) : Q = C while |Q| > 1 : New node z z.left = x = q.extractMin() z.right = y = q.extractMin() z.freq = x.freq + y.freq Q.insert(z) return Q.extrctMin()

Huffman-process(root = Huffman(C)) : if(root.left == null AND root.right == null) : print(root.char) else: print('0' + Huffman-process(root.left) print('1' + Huffman-process(root.right)

Huffman-sorted(C) : Q1 = C Q2 = ∅ while |Q1| + |Q2| > 1 : New node z z.left = x = getMin(Q1,Q2) z.right = y = getMin(Q1,Q2) z.freq = x.freq + y.freq Q2.insert(z) return getMin(Q1, Q2) getMin(Q1,Q2): if Q1 = ∅ : return Q2.dequeue() if Q2 = ∅ : return Q1.dequeue() if Q1.front < Q2.front : return Q1.dequeue() else return Q2.dequeue()

MST-Kruskal(G) : T = ∅ for each v in V : makeSet(v) sort E by weights for each (u,v) in E : if findSet(u) ≠ findSet(v) : T.add((u,v)) union(u, v) return T

MST-Reversed-Kruskal(G) : T = E Q = E while |T| > |V|-1 : e = Q.extractMax() G.removeEdge(e) if isConnected = false : G.addEdge(e) return T

MST-Prim(G) : T = ∅ for each v in V : v.key = ∞ v.prev = null V[0].key = 0 Q = V while Q ≠ ∅ : u = Q.extractMin() if u.prev ≠ null : T.add((u, u.prev)) for each v in adj[u] : if v in Q AND v.key > w(u,v) : v.key = w(u,v) v.prev = u return T

MST-Boruvka(G) : T = ∅ for each v in V : makeSet(v) while |T| < |V|-1 : New cheapest[|V|] := array of edges for (u,v) in E : g1 = findSet(u) g2 = findSet(v) if g1 ≠ g2 : if w(cheapest[g1]) > w(u,v) : w(cheapest[g1]) = w(u,v) if w(cheapest[g2]) > w(u,v) : w(cheapest[g2]) = w(u,v) for i=0 to |v| : if cheapest[i] ≠ null : T.add(cheapest[i]) union(cheapest[i].u, cheapest[i].v) return T

BFS(G, s) : for each v in V : v.color = WHITE, v.dist = ∞, v.prev = null s.color = GRAY, s.dist = 0, s.prev = -1 Q = {s} while Q ≠ ∅ : u = Q.dequeue() for each v in adj[u] : if v.color = WHITE : v.color = GRAY v.dist = u.dist + 1 v.prev = u Q.enqueue(v) u.color = BLACK

DFS(G) : for each v in V : v.color = WHITE for each v in V : if v.color = WHITE : DFS-VISIT(G, v) DFS-VISIT(G, n) : n.color = GRAY for each v in adj[n] : if v.color = WHITE : DFS-VISIT(G, v) n.color = BLACK

Is-Edge-On-Cycle(G, e) : u = e.u v = e.v G.removeEdge(e) BFS(v) return (u.color ≠ WHITE)

DFS-Number-Of-Connected-Components(G) : counter = 0 for each v in V : v.color = WHITE for each v in V : if v.color = WHITE : counter++ DFS-VISIT(G, v) return counter

DFS-Has-Cycle(G) : for each v in V : v.color = WHITE for each v in V : if v.color = WHITE : if DFS-VISIT(G, v) = true : return true return false

DFS-VISIT(G, n) : n.color = GRAY for each v in adj[n] : if v.color = GRAY : return true if v.color = WHITE : if DFS-VISIT(G, v) = true : return true n.color = BLACK return false

Has-Euler-Cycle(G) : for each v in V : if v.degree % 2 ≠ 0 : return "No euler Cycle detected" if isConnected(G) : return Euler-Cycle(G)

Euler-Cycle(G) : select some vertex s from G list C = ∅ stack = {s} while stack ≠ ∅ : v = stack.peek() if v.degree = 0 : C.add(stack.pop()) else : u = first of adj[v] stack.push(u) G.remove(u,v) G.remove(v,u) return C 

BFS-isConnected(G) : select some vertex s from G BFS(G, s) for each v in V : if v.color ≠ BLACK : return false return true 

Euler-HasEuler-path(G) : counter = 0 for each v in V : if v.degree % 2 ≠ 0 : counter++ return isConnected(G) = true AND counter = 2

Diameter-Fire(T) : n = |V|, radius = 0, leaves = ∅ for each v in V : if v.deg = 1 : leaves.add(v) while n > 2 : future = ∅ for each leaf in leaves : leaf.deg = 0 n-- for each v in adj[leaf] : if --v.deg = 1 : future.add(v) radius++ leaves = future diameter = radius*2 + |leaves|-1 centers[] = leaves return {centers, radius, diameter}

Diameter-DFS(T) : maxDist = 0, MaxDistVertex = 0 DFS(T, 0) for each v in V: if maxDist < v.dist : maxDist = v.dist MaxDistVertex = v DFS(T, MaxDistVertex) for each v in V: if maxDist < v.dist : maxDist = v.dist return maxDist

Diameter-Path-DFS(T) : maxDist = 0, MaxDistVertex = 0 DFS(T, 0) for each v in V: if maxDist < v.dist : maxDist = v.dist MaxDistVertex = v DFS(T, MaxDistVertex) for each v in V: if maxDist < v.dist : maxDist = v.dist MaxDistVertex = v path = ∅ while MaxDistVertex != -1 : path.add(MaxDistVertex) MaxDistVertex = MaxDistVertex.prev return path

is-Vertex-on-Diameter(T, v) : diameter = Diameter(T) BFS(v) maxDist1 = maxDistIndex = 0 for each v in V : if maxDist1 < v.dist : maxDist1 = v.dist maxDistIndex = v while maxDistIndex.prev ≠ v : maxDistIndex = maxDistIndex.prev remove((v, maxDistIndex)) BFS(v) maxDist2 = 0 for each v in V : if maxDist2 < v.dist : maxDist2 = v.dist return (diameter == maxDist1 + maxDist2)

Dijkstra(G, s) : for v in V : v.dist = ∞ s.dist = 0 Q = V while Q ≠ ∅ : u = Q.extractMin() //by dists for v in adj[u] : if v.dist > u.dist + w(u,v) : v.dist = u.dist + w(u,v) v.prev = u

GenerateTreebyDegrees(deg[N]) : sort(deg) j = 0 while deg[j] = 1 : j++ New Tree[N,N] = {false} for i=0 to N-2 : Tree[i,j] = true Tree[j,i] = true if --deg[j] = 1 : j++ Tree[N-2,N-1] = true Tree[N-1,N-2] = true return Tree

AHU-Tree-Isomorphism(T1, T2) : r1 = T1.root r2 = T2.root if r1 = null AND r2 = null : r1 = findCenter(T1) // by Fire Algorithm r2 = findCenter(T2) New global List<String> childrenCodes[|V|] code1 = findCode(r1) code2 = findCode(r2) return (code1 == code2)

findCode(u) u.color = BLACK if u is a leaf : return "10" for each v in adj[u] : if v.color = WHITE : // then v is child of u childrenCodes[u].add(findCode(v)) Sort(childrenCodes[u]) temp = "" for each s in childrenCodes[u] : temp += s return "1"+temp+"0"