Graphs
Some data structures to keep in my mind.
- BinaryHeap: Complete binary tree
- MaxHeap: Parent > Both Children
- IndexMaxHeap
- MinHeap: Parent < Both Children
- IndexMinHeap
- Priority queue (MaxHeap)
- BinarySearchTree
- Not always complete binary tree
- Value: leftChild < Parent < rightChild
- DenseGraph
- SparseGraph
Code snippets are taken from Play with Algorithm
1. Dense Graph
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
| #include <iostream>
#include <vector>
#include <cassert>
using namespace std;
// 稠密图 - 邻接矩阵
class DenseGraph{
private:
int n, m;
bool directed;
vector<vector<bool>> g;
public:
DenseGraph( int n , bool directed ){
this->n = n;
this->m = 0;
this->directed = directed;
for( int i = 0 ; i < n ; i ++ )
g.push_back( vector<bool>(n, false) );
}
~DenseGraph(){
}
int V(){ return n;}
int E(){ return m;}
void addEdge( int v , int w ){
assert( v >= 0 && v < n );
assert( w >= 0 && w < n );
if( hasEdge( v , w ) )
return;
g[v][w] = true;
if( !directed )
g[w][v] = true;
m ++;
}
bool hasEdge( int v , int w ){
assert( v >= 0 && v < n );
assert( w >= 0 && w < n );
return g[v][w];
}
void show(){
for( int i = 0 ; i < n ; i ++ ){
for( int j = 0 ; j < n ; j ++ )
cout<<g[i][j]<<"\t";
cout<<endl;
}
}
class adjIterator{
private:
DenseGraph &G;
int v;
int index;
public:
adjIterator(DenseGraph &graph, int v): G(graph){
this->v = v;
this->index = -1;
}
int begin(){
index = -1;
return next();
}
int next(){
for( index += 1 ; index < G.V() ; index ++ )
if( G.g[v][index] )
return index;
return -1;
}
bool end(){
return index >= G.V();
}
};
};
|
2. Sparse Graph
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
| #include <iostream>
#include <vector>
#include <cassert>
using namespace std;
// 稀疏图 - 邻接表
class SparseGraph{
private:
int n, m;
bool directed;
vector<vector<int>> g;
public:
SparseGraph( int n , bool directed ){
this->n = n;
this->m = 0;
this->directed = directed;
for( int i = 0 ; i < n ; i ++ )
g.push_back( vector<int>() );
}
~SparseGraph(){
}
int V(){ return n;}
int E(){ return m;}
void addEdge( int v, int w ){
assert( v >= 0 && v < n );
assert( w >= 0 && w < n );
g[v].push_back(w);
if( v != w && !directed )
g[w].push_back(v);
m ++;
}
bool hasEdge( int v , int w ){
assert( v >= 0 && v < n );
assert( w >= 0 && w < n );
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v][i] == w )
return true;
return false;
}
void show(){
for( int i = 0 ; i < n ; i ++ ){
cout<<"vertex "<<i<<":\t";
for( int j = 0 ; j < g[i].size() ; j ++ )
cout<<g[i][j]<<"\t";
cout<<endl;
}
}
class adjIterator{
private:
SparseGraph &G;
int v;
int index;
public:
adjIterator(SparseGraph &graph, int v): G(graph){
this->v = v;
this->index = 0;
}
int begin(){
index = 0;
if( G.g[v].size() )
return G.g[v][index];
return -1;
}
int next(){
index ++;
if( index < G.g[v].size() )
return G.g[v][index];
return -1;
}
bool end(){
return index >= G.g[v].size();
}
};
};
|
