算法笔记

正好有人借 593 的笔记,稍微整理了一下 =-=(还是可能有些许错误的)

Analysis of algorithms

$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
for(int i = 0; i < n; i++){//O(n)
f();//O(1)
}

//O(n)
for (int i = 0; i < n; i++) {
}
for (int i = 5; i < n; i++) {
}

//O(n)
for (int i = 5; i < n; i+=7) {
}

for i <- 1 to sqrt(n) //O(sqrt(n))

for i <- sqrt(n) to n //O(n)

for i <- n to n/2 //O(n)

for i <- n to n step n/2 //O(1)

1 < logn < sqrt(n) < n < n^2

for (int i = 1; i < n; i *= 3) { } //O(logn)
for (int i = 1; i < n; i = i * 3 + 8) { }//O(logn)
for (int i = 1; i < n; i *= 2) { // 1, 2, 4, 8, …. log2(n)
}
for (int i = 1; i < n; i *= 3) { // 1, 3, 9, 27, …. log3(n)
}
for (int i = 1; i < sqrt(n); i *= 3 {} //O(log sqrt(n))

//O(n*n) = O(n^2)
for (int i = 0; i < n; i++) //O(n)
for (int j = 0; j < n; j++) { //O(n)
}
}

//O(n+n) = O(n)
for (int i = 0; i < n; i++) //O(n)
}
for (int j = 0; j < n; j++) { //O(n)
}

//sum(1...n)=O(n^2)
for (int i = 0; i <= n; i++) //O(n)
for (int j = 0; j <= i; j++) { // 1 + 2 + 3 + … + n-1 + n
}
}

//O(n*sqrt(n))
for (int i = 0; i <= n; i++) { //O(n)
for (int j = 0; j < sqrt(n); j++) { //O(sqrt(n))
}
}

for (int i = 0; i <= n; i++) { //O(n)
for (int j = 0; j < n-sqrt(n); j++) {
}
}

//O(n log2n)
for (int i = 0; i < n; i++) { // O(n)
 for (int j = 1; j < n; j *= 2) { // O(log2n)
 }
}

//n(1+1/2+1/4+1/8+...)
//\sum(1/2^i)=1
//O(n)
for (int i = 1; i <= n; i *= 2) { // O(log2n)
 for (int j = 1; j < i; j++) { // O(1 + 2 + 4 + 8 + …. + n)
 }
}

//O(n+m) if n ≈ m O(2n) = O(n)
for (int i = 0; i < n; i++) { //O(n)
}
for (int j = 0; j < m; j++) { //O(m)
cout << i * j; //O(1)
}

for (int i = 1; i < n; i *= 2) //O(log n)
for (int j = 1; j < n; j++) //O(n)
System.out.println(i*j);

for (int j = 1; j < n; j++) //O(n)
for (int i = 1; i < n; i *= 2) //O(log n)
System.out.println(i*j);

for (int i = 0; i < n; i++) //O(n)
for (int j = i; j < n; j++) // n + (n-1) + (n-2) + … 1
print(“x”);

sum ← 912851; //O(1)
for i ← 1 to n
for j← 3 to i // 0 + 0 + 1 + 2 + 3 + … n-3 = O(n^2)
sum ← sum + i*j;
end
end

int f(int n) {
if (n <= 0)//O(1)
return 1;
return n * f(n-1);
}
f(5)=5*f(4)=5*4*f(3)...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//Fibo
int fibo(int n) { //O(n)
int a = 1, b = 1, c;
for (int i = 0; i < n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}

int fibo2(int n) { //O(2^n)
if (n <= 2)
return 1;
return fibo2(n-1) + fibo2(n-2);
}

Sorting

Selection Sort

1
2
3
4
5
6
7
8
9
10
11
void selectionSort(int x[], int n) { //O(n2)
for (int j = n - 1; j > 0; j--) {
int pos = 0;
for (int i = 1; i <= j; i++) {
if (x[i] > x[pos])
pos = i;
}
if (j != pos)
swap(x[pos], x[j]);
}
}

Insertion Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InsertionSort(int x[], int n) {
for (int i = 1; i < n; i++) {
int temp = x[i];
for (int j = i - 1; j >= 0; j--)
if (x[j] > temp)
x[j+1] = x[j];
else {
x[j+1] = temp;
break;
}
}
x[0] = temp; //TODO: BAD edge case here
}
}

worst case 1 + 2 + … + (n - 1) = $O(n^2)$

best case 1 + 1 + … + 1 = $\Omega(n)$

Quick Sort

  1. pick a pivot(a value in the middle)

    1. pivot ← (x[left] + x[right]) / 2
    2. pivot ← (x[left] + x[right] + x[(left+right)/2]) / 3
    3. pivot ← x[random] random is unpredictable
  2. Do not use…

    1. pivot ← x[left]
    2. pivot ← x[right]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
quicksort(int[] x, int left, int right) {
if (right - left < 2)
return;
int pivot = (x[left] + x[right])/2;
int i = left, j = right;

while (i < j) { //O(n)
while (x[i] < pivot)
i++;
while (x[j] >= pivot)
j--;
if (i < j) {
swap(x[i], x[j]);
}
}
//i == j
quicksort(x, left, i-1 ); // logn
quicksort(x, i, right);
}

quicksort(x, 0, x.length-1);

Worst case (pathological) $O(n^2)$

Heap Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
makeheap(x)     
for i ← n/2 to 0
makesubheap(x, i)
end

makesubheap(x, i)
if x[2i+1] > x[2i+2]
if x[i] < x[2i+1]
swap(x[i], x[2i+1])
makesubheap(x, 2i+1)
end
else
if x[i] < x[2i+2]
swap(x[i], x[2i+2])
makesubheap(x, 2i+2)
end
end

heapsort(x)
makeheap(x)
for i ← n-1 to 1
swap(x[0], x[i])
makesubheap(x, i-1)
end
end
//makeheap = (n/2-1) log n + rebuild heap (n-1) log n = O(n log n)

Merge Sort

work each time: n

number of iterations log n

O(n log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// merge lists a,b of size n into list c of size 2n
merge(a, b, c) {
  i ← 0 // position in a
  j ← 0 // position in b
  k ← 0 // position in c
  while i < n and j < n
      if a[i] < b[j]
             c[k] ← a[i]
             i ← i + 1
      else
             c[k] ← b[j]
             j ← j + 1
      end
      k ← k + 1
end
}

Shuffling

1
2
3
4
5
6
Fisher-Yates(x) // O(N)
for i← x.length-1 to 0
pick ← random(0, i)
swap(x[i], x[pick])
end
end

Searching

search(x, target)

$O(n),\Omega(1), avg = n/2$

sort:O(n log n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
binarySearch(x, target)
L ← 0
R ← x.length-1
while (L < R)
mid ← (L + R) / 2
if x[mid] > target
R ← mid - 1
else if x[mid] < target
L ← mid + 1
else
return mid
end
return NOTFOUND
end

L = 0

R = 19

S = (R-L) / = 19 * .6 = 11.4 =

function f(x) = 4 - x2

L = -2 R = 1 D = R-L = 3

S = (R-L)/ 1.618 = 1.85

X = R - 1.85 = -.85

Y = L + 1.85 = -.15

L = -.85

S =(R-L)/ 1.618 = 1.143

X = -.15

Y = L + S = -.85 + 1.143 = .293

R = .293

Number Theoretic Algorithms

gcd

1
2
3
4
5
6
gcd(a,b)
if b == 0
return a
end
return gcd(b, a mod b)
end

$O(logn),\Omega(1)$

lcm

1
2
//O(log n)
lcm(a,b) = a * b / gcd(a,b) // 1 + log(n)

powermod

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//raise x to the power n
bruteforcepower(x, n)
prod ← 1
for x ← 1 to n
prod ← prod * x
end
return prod
end

//O(log n)
//raise x to the power n
power(x, n)
prod ← 1
while n > 0
if (n mod 2 != 0)
prod ← prod * x
end
x ← x * x
n ← n / 2
end
return prod
end

//xn mod m
powermod(x, n, m)
prod ← 1
while n > 0
if (n mod 2 != 0)
prod ← prod * x mod m
end
x ← x * x mod m
n ← n / 2
end
return prod
end

Fermat

if a^p-1 mod p == 1⇒ p is probably prime

if a^p-1 mod p != 1⇒ p is definitely NOT prime

Miller-Rabin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MillerRabin(n, k)
WitnessLoop: for i ← 1 to k // k trials
a← random[2, n − 2]
x ← a^d mod n
if x = 1 or x = n − 1 then
continue WitnessLoop
for j ← 1 to s − 1
x ← x2 mod n
if x = 1 then
return false composite (Carmichael?)
if x = n − 1 then
continue WitnessLoop
end
return false (composite)
return probably prime

brute force trial division

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//O(n)		Ω(1)
bool isPrime(int n) {
for (int i = 2; i < n/2; i++) {
if (n % i == 0)
return false;
}
return true;
}

//O(√n) Ω(1)
bool isPrime(int n) {
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0)
return false;
}
return true;
}

Eratosthenes’ Sieve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ImprovedEratosthenes(n)
for i ← 2 to n
isPrime[i] ← true
end
for i ← 4 to n step 2
isPrime[i] ← false
end
for i ← 3 to n step 2
if isPrime[i]
for j ← i*i to n step 2i
isPrime[j] ← false
end
end
end

GrowArray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class GrowArray {
private:
int* data;
int len;
int capacity;
void grow(){
int* old = data;
data = new int[2*capacity + 1];
for (int i = 0; i < len; i++) // memcpy(data, old, len* sizeof(int))
data[i] = old[i];
delete old;
capacity = 2 * capacity;
}
public:
GrowArray() { data = nullptr; len = 0; capacity = 0;}
void addEnd(int v) { // O(1)
if (len >= capacity)
grow();
data[len++] = v;
cout<<v<<endl;
}
};
 
int main() {
const int n = 1000000;
GrowArray a;
for (int i = 0; i < n; i++)
a.addEnd(i);
}

Linkedlist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class LinkedList {
private:
class Node {
int val;
Node* next;
Node* prev;
};
Node* head;
Node* tail;
public:
LinkedList() : head(nullptr), tail(nullptr) {} // O(1)
~LinkedList() { // O(1)
while (head != nullptr) {
Node* temp = head;
head = head->next;
delete temp;
}
}
void addFirst(int v) { // O(1)
head = new Node {v, head, nullptr};
if (tail == null)
tail = head;
else
head->next->prev = head;
}
void addLast(int v) {
tail = new Node(v, nullptr, tail);
if (head == nullptr)
head = tail;
else
tail->prev->next = tail;
}
void removeFirst() {
Node* temp = head;
head = head->next;
delete temp;
}
}

Stack

1
2
3
4
5
6
7
8
9
10
class Stack {
private:
LinkedList impl; // addFirst O(1), addLast O(n), removeFirst O(1), removeLast O(n)
GrowArray impl; // addFirst O(n) addLast O(1), removeFirst O(n), removeLast O(1)
public:
void push(int v) { impl.addFirst(v); }
int pop() { return impl.removeFirst()}
bool isEmpty() const {}
int size(const {})
};

Queue

1
2
3
4
5
6
7
8
class Queue {
private:
linkedList 2 templ; // has head and tail
public:
void enqueue(int v) {impl.addLast(v)} // O(1)
int dequeue() { impl.removeFirst()} // O(1)
bool isEmpty() const { return impl,isEmpty();}
}

Trees

Binary tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class BinaryTree {
private:
class Node {
public:
int val;
Node* parent;
Node* left; // int* a,b; a is pointer to int, b is just int
Node* right;
Node(int v, Node* L, Node* r) : val(v), left(L), right(R) {}
};
Node * root;
public:
void add(int v) {
if (root == nullptr) {
root = new Node(v, nullptr, nullptr);
return;
}
… }

inorder(node n)
if n == null
return
inorder(n.left)
print (val)
inorder(n.right)
end

preorder(node n)
if n == null
return
print (val)
preorder(n.left)
preorder(n.right)
end

postorder(node n)
if n == null
return
postorder(n.left)
postorder(n.right)
print (val)
end

Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Trie{
private:
class Node{
Node* next[26];
bool isWord;
}
Node root;
public:
Trie() {}// set up the empty trie root contains all null pointers
~Trie() {
Node* p = root;
for (int i = 0; i < 26; i++)
if (p->next[i] != nullptr)
deleteNode(p->next[i]);
}

void insert(String word) {
Node* temp = root;
for (int i = 0; i < word.size; i++)
int index = word[i] - 'a';
if temp->next[index] == nullptr
temp->next[index] = new Node();
temp = temp->next[index];
temp->isWord = true;
}

bool containsPrefix(String word) {
Node* temp = root;
for (i = 0; i < word.size; i++) {
int index = word[i] - 'a';
if (temp->next[index] == nullptr)
return false;
temp = temp->next[index];
}
return true;
}
bool contains(String word) {
Node* temp = root;
for (i = 0; to word.size) {
int index = word[i] - 'a';
if (temp->next[index] == nullptr)
return false;
temp = temp->next[index];
}
return temp->isWord;
}
}
}

Hashing

Hash functions

Linear probing

Linear probing is a strategy for resolving collisions, by placing the new key into the closest following empty cell.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
add(k)
if 2*used >= capacity
grow()
pos ← hash(k)
while table[pos] != EMPTY
pos++
if pos >= table.length
pos = 0
end
end
used++
table[pos] ← k
end

find(k)
pos ← hash(k)
while table[pos] != EMPTY
if table[pos] == k
return true
end
pos++
if pos >= table.length
pos = 0
end
end
return false
end

bool ← remove(k)
pos ← hash(k)
while table[pos] != 0
if table[pos] == k
table[pos] ← 0
// redo everyone potential
// until next 0
return
end
pos++
if pos >= table.length
pos = 0
end
end
return false
end

Quadratic probing*

Linear chaining

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
LinearChaining.add(k)
pos ← hash(k)
p ← table[pos].head
while p != null
if p.k == k
return
p = p.next
end
table[pos].addStart(k)
end

LinearChaning.find(k)
pos ← hash(k)
p ← table[pos].head
while p!= null
if p.k == k
return true
p = p.next
end
return false
end

Perfect hashing

Matrices

Representation (rectangular, diagonal, tridiagonal)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Matrix{
private:
int row,cols;
double* m;
public:
Matrix(int rows, int cols, double val) : rows(rows), cols(cols){
for (int i = 0; i < row * cols; i++)
m[i] = val;
}
~Matrix(){
delete []m
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
\\Lower Triangular Matrix
get(i, j)
if(j > i)
return 0
return m[i*(i+1)/2+j]

\\Diagonal Matrix
get(i, j)
if(i == j)
return m[i]
return 0

\\TriDiagonal Matrix
get(i, j)
if(abs(j-i) > 1)
return 0;
return m[2i+j]

Addition

1
2
3
4
5
6
7
8
9
addition(a, b)
if a.rows != b.rows OR a.cols != b.cols
ERROR
end
for i ← 0 to rows*cols
ans[i] = a[i] + b[i]
end
return ans
end

Multiplication

1
2
3
4
5
6
7
8
9
10
11
12
13
14
mult(a, b)
if a.cols != b.rows
ERROR
end
for k ← 0 to a.rows-1
for i ← 0 to b.cols - 1
sum ← 0
for j ← 0 to a.cols - 1
sum ← sum + a(k,j)*b(j,i)
end
ans(k,i) ← sum
end
end
end

Solving systems (Gauss-Jordan Elimination, partial pivoting)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
partialPivot(A,i)
max ← A(i,i)
maxpos ← i
for j ← i+1 to rows-1
if A(j,i) > max
max ← A(j,i)
maxpos ← j
end
end
//swap rows
GaussianElimination(A,i)
for i ← 0 to rows-2
partialPivot(A,i)
for j ← i+1 to rows-1
s ← - A(j,i)/A(i,i)
A(j,i) ← 0
for k ← i+1 to cols - 1
A(j,k) += s * m(i,j)
end
end
end

Gram-Schmidt orthogonalization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void subtractProj(int i, int j){
double dot = 0;
for (int k = 0; k < rows; k++)
dot += (*this)(k,i) * (*this)(k,j);
//<u.v>
for (int k = 0; k < rows; k++)
(*this)(k,j) -= dot * (*this)(k,j);
}
gramschmidt(){
int n = cols;
double mag = 0;
for (int i = 0; i < n; i++)
mag += (*this)(i,0) * (*this)(i,0);
mag = 1 / sqrt(mag);
for (int i = 0; i < n; i++)
(*this)(i,0) *= mag;
for(int j = 1; j < n; j++){
for (int i = 0; i < j; i++)
subtractProj(i,j);
double mag = 0;
for (int i = 0; i < n; i++)
mag += (*this)(i,j) * (*this)(i,j);
mag = 1/sqrt(mag);
for (int i = 0; i < n; i++)
(*this)(i,j) *= mag;
}
return *this;
}

Strings

Boyer-Moore

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void boyerMoore(const char s[], const char target[]){
int jump[256];
int n = strlen(s);
int len = strlen(target);
for (int i = 0; i < 256; i++)
jump[i] = len;
for (int i = 0; i < len; i++)
jump[target[i]] = len - 1 - i;
for (int i = len - 1; i<n;){
int offset = jump[s[i]];
if(offset > 0)
i += offset;
else{
for (int j = i - len +1, k = 0; j < i; j++, k++)
if(target[k] != s[j])
goto notfound;
cout << "Found:" < i-len +1<<endl;
notfound:
i+=len;
}
}

for i =0 to 255
table[i] = len
for i = 0 to len
table[target[i]] = len - i - 1
i = len-1
while (i < n)
jump ← table[search[i]]
if (jump == 0) { // possible match
// compare the word letter by letter

}
i ← i + jump
end

Finite State*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class FiniteStateMachine {
private:
int currentState;
int next[NUMSTATES][256];
public:
FiniteStateMachine() : currentState(0) {
for (int i = 0; i < 256; i++)
next[0][i] = 1;
for (int i = 'a'; i <= 'z'; i++)
next[0][i] = 0;
for (int i = 'A'; i <= 'Z'; i++)
next[0][i] = 0;


}
void exec(const char inp[]) {
for (int i = 0; inp[i] != '\0'; i++) {
currentState = next[currentState][inp[i]];
if (currentState == 1)
return; // get out when we reach the end state
}
};

LCS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int LCS(string s, string t){
int m = s.size();
int n = t.size();
int dp[m+1][n+1];
for(int i = 0; i < m + 1; i++){
for(int j = 0; j < n + 1; j++){
if(i==0||j==0){
d[i][j]=0;
}
else if(s[i-1]==t[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[m][n];
}

Graphs

Representation: list or matrix

img

find out if v1 is adjacent to v2 = O(E) = O($V^2$) Ω(1)

find out the set of vertices connected to v is O(E)

Storage: O(E) Ω(1)

img

Storage: O(E) Ω(V)

is vertex k adjacent to vertex m? O(V) Ω(1)

find all vertices adjacent to vertex k? O(V) Ω(1)

1
2
isAdjacent(from,to)   //O(V)
allAdjacent(from) //O(V), Ω(1)

img

Space complexity: O(E) = O(V2) Ω(V2) = Θ(V2)

is vertex k adjacent to vertex m? O(1)

find all vertices adjacent to k? O(V)

1
2
3
4
5
6
7
isAdjacent(from,to)   //O(1)
if from < to
return isAdajacent(to, from)
return m[from][to]
end

allAdjacent(from) //O(V), Ω(V) ⇒ θ(V)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class MatrixGraph {
private double [] w;
private int V;
public boolean isAdjacent(int i, int j) { return !isInf(w[i * V + j]); } //O(1)
public boolean[] adjacent(int v) { … } // O(V) Ω(V)
}

class EdgeListGraph {
private static class Edge {
int to;
double w;
}
private LinkedList<Edge>[] v;
public boolean isAdjacent(int i, int j) { … } //O(V) Ω(1)
public boolean[] adjacent(int i) { … } // O(V) Ω(1)
}

DFS

O(V2) worst case (matrix representation, ALWAYS)

Ω(1) best case (with initial vertex not connected to anyone, list)

Ω(V) best case (with initial vertex not connected to anyone, matrix)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
g.DFS2(v,visited) //O(V^2) Ω(1) with list impl
visited[v] ← true
print v
foreach v2 in adjacent(v)// for matrix O(v), for linkedlist O(v) Ω(1)
if NOT visited[v2]
g.DFS2(v2, visited)
end
end
end
g.DFS(v)
visited ← [false, false, ...,] //O(v)
g.DFS2(v,visited)
end

//iteratively
g.DFS(v)
visited ← [false, false, ...,] //O(v)
stack ← empty
stack.push(v)
visited[v] ← true
while NOT stack.empty()
v ← stack.pop();
print v
foreach v2 in adjacent(v)
if NOT visited[v2]
stack.push(v2)
visited[v2] ← true
end
end
end
end

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
g.BFS(v)
visited ← [false, false, ...,] //O(v)
queue ← empty
queue.enqueue(v)
visited[v] ← true
while NOT queue.empty()
v ← queue.dequeue();
print v
foreach v2 in adjacent(v)
if NOT visited[v2]
queue.enqueue(v2)
visited[v2] ← true
end
end
end
end

IsConnected

1
2
3
4
5
6
7
8
bool ← g.isConnected() //O(V^2)
visited ← g.DFS(r)
for i ← 0 to V
if NOT visited[i]
return false
end
return true
end

Bellman-Ford//O(VE)

1
2
3
4
5
6
7
8
9
10
11
BellmanFord(start, end)
cost ← [∞, ∞, ...]
cost[start] ← 0
for v ← 0 to V-1
for each edge e from v
if cost[v2] > cost[v] + adjacent[v2]
cost[v2] ← cost[v] + adjacent[v2]
add to the list to recompute costs from v2
end
end
end

Floyd-Warshall//O(V^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
dist ← |V| × |V| array of minimum distances initialized to ∞

for each vertex v
dist[v][v] ← 0
for each edge (u,v)
dist[u][v] ← w(u,v) //the weight of the edge (u,v)
for k from 1 to V
for i from 1 to V
for j from 1 to V
if dist[i][j] > dist[i][k] + dist[k][j]
dist[i][j] ← dist[i][k] + dist[k][j]
end
end
end
end

Prim//O(V^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Prim(v)
visited ← new Vector(V, false)
visited[v] ← true
for i ← 1 to V-1
for all edges out of the visited set(V,2V,3V, ...) to V-1
min ← ∞
if isAdjacent(v,a) and NOT visited[a]
if getWeight(v,a) < min
min ← getWeight(v,a)
minA ← a
end
end
end
visited[minA] ← trme
v ← minA
end
end

Kruskal//O(E log E)

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

TSP*

Backtracking

Basic

Heap’s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
using namespace std;

class Permute {
private:
int* p;
int N;
public:
Permute(int x[], int N) : p(x), N(N) {
//generate(N-1);
heaps(N-1);
}
void generate(int n) {
if (n == 0) {
doit();
return; // What Sedgewick forgot!!!!
}
for (int c = 0; c <= n; c++) {
swap(p[c], p[n]);
generate(n-1);
swap(p[c], p[n]);
}
}
void heaps(int n) {
if (n == 0) {
doit();
return; // What Sedgewick forgot!!!!
}
for (int c = 0; c <= n; c++) {
generate(n-1);
swap(n % 2 ? p[0] : p[c] , p[n]);
}
}

void doit() const {
for (int i = 0; i < N; i++)
cout << p[i];
cout << '\n';
}
};


int main() {
int x[] = {1, 2, 3, 4};
Permute perm(x, 4);
}