QSort:
typedef int TData;
typedef int( *TComparator )( const TData*,const TData* );
void swap ( TData* a, int l, int r ) {
TData k = a[l];
a[l] = a[r];
a[r] = k;
return;
}
int Partition( TData* a, int l, int r, TComparator comp ) {\\ Partition LOLuto
int i = l - 1;
TData v = a[r]; // опорный элемент
for ( int j = l; j <= r - 1; ++j ) {
if ( comp( &a[j], &v )==-1) {
++i;
swap(a, i, j);
}
}
swap( a, i + 1, r );
return i + 1;
}
void quick_sort( TData* a, int l, int r, TComparator comp ) {
int q;
if ( l >= r )
return;
q = Partition( a, l, r, comp );
quick_sort( a, l, q-1, comp );
quick_sort( a, q+1, r, comp );
}
int Compare ( const TData* a,const TData* b ) {
if( *a < *b ) return -1;
else
if ( *a > *b ) return 1;
else return 0;
}
In main(TComparator comp = Compare; quick_sort( a, ,0, N - 1, comp );
void insertion_sort(int *a, int n) {
int i,k,j;
for (i=1;i<n;i++) {
j=i;
while(a[j]<a[j-1] && j>0) {
k=a[j];
a[j]=a[j-1];
a[j-1]=k;
j--;
}
}
}
List:
struct ListNode { int value; struct ListNode *prev; struct ListNode *next; };
struct List { int size; struct ListNode *head; struct ListNode *tail; };
int binsearch(int *a, int v, int l, int h ) {\\или код с футболки!
int mid;
if (h<l)
return -1;
mid=(l+h)/2;
if (a[mid]>v)
return binsearch(a, v, l, mid-1);
else
if (a[mid]<v)
return binsearch(a, v, mid+1, h);
else
return mid;
}
Для строк
int binsearch(char **a, chat* v, int l, int h)
{
int mid;
if (h<l)
return -1;
mid=(l+h)/2;
if (strcmp(a[mid],v)>0)
return binsearch(a, v, l, mid-1);
else
if (strcmp(a[mid],v)<0)
return binsearch(a, v, mid+1, h);
else
return mid;
}
Поиск к-ой статистики ???
int findOrderStatistic(int[] array, int k) { int left = 0, right = array.length; while (true) { int mid = partition(array, left, right); if (mid == k) array[mid]; else if (k < mid) return right = mid; else { k -= mid + 1; left = mid + 1; } } }
Heap SoRT:
typedef int TData;
void Heapify ( TData* mas, int i, int n ){
int left = 2*i+1;
TData largest;
int right = 2*i+2;
if (left <= n && mas[left] > mas[i]) {
largest = left;
}
else { largest = i; }
if ( right <= n && mas[right] > mas[largest] ) {
largest = right;
}
int k;
if ( largest != i ) {
k= mas[i];
mas[i] = mas[largest];
mas[largest] = k;
Heapify( mas, largest, n );
}
}
void heap_build ( TData* mas, int n ) {
for ( int i=n/2-1; i>=0; --i ) { Heapify ( mas, i, n );}
}
void heap_sort ( TData data[], int length ) {
heap_build ( data, length );
TData m;
for ( int i=length-1; i>=0; --i )
{
m = data[0];
data[0]=data[i];
data[i]=m;
length=length-1;
Heapify ( data, 0, length-1 );
}
}
Дерево поиска
struct TreeNode { int key; TreeNode* Left; TreeNode* Right; };
struct BinarySearchTree{
int size;
TreeNode* root;
}
SearchTree Insert( ElementType X, SearchTree T ) { if( T == NULL ) { T = malloc( sizeof( struct TreeNode ) ); if( T == NULL ) FatalError( "Out of space!!!" ); else { T->Element = X; T->Left = T->Right = NULL; } } else if( X < T->Element ) T->Left = Insert( X, T->Left ); else if( X > T->Element ) T->Right = Insert( X, T->Right ); return T; }
Merge sort
typedef int TData;
typedef int ( *TComparator ) ( const TData*, const TData* );
int compare( const TData* a, const TData* b ) {
if ( (*a) == (*b) )
return 0;
if ( ( *a) < (*b) )
return -1;
else
return 1;
}
void merge ( TData* mas, int left, int m, int right, TComparator comp ) {
TData* mas2 = new TData[right-left+1];
int l = left;
int r = m + 1;
int t = 0;
while ( ( l <= m ) && ( r <= right ) ) {
if ( comp ( &mas[l], &mas[r] ) == -1 ) {
mas2[t] = mas[l];
++t;
++l;
}
else{
mas2[t] = mas[r];
++t;
++r;
}
}
while ( r <= right ){
mas2[t] = mas[r];
t++;
r++;
}
while ( l <= m ){
mas2[t] = mas[l];
++t;
++l;
}
for ( int i = 0; i < ( right-left + 1 ); ++i )
mas[left+i] = mas2[i];
delete[] mas2;
}
void sort( TData* mas, int left, int right, TComparator comp ) {
if (left < right) {
int m = (left + right) / 2;
sort( mas, left, m, comp);
sort( mas, m+1, right, comp);
merge( mas, left, m, right, comp );
}
}
Shell – sort:
typedef int ( *TComparator ) ( const TData*, const TData* );
void swap (TData* a, int l, int r) {
TData k = a[l];
a[l] = a[r];
a[r] = k;
return;
}
int Compare (const TData* a, const TData* b) {
return *a-*b;
}
void insertionSort(TData* a, int l, int r, TComparator comp) {
int i, j; TData key;
for( j = l + 1; j < r; ++j) {
key = a[j];
i = j - 1;
while ( i>=l && comp(&a[i],&key) >= 0) {
a[i+1] = a[i];
i--;
}
a[i + 1] = key;
}
};
void Shell_sort(TData* a, int length, TComparator comp) {
int d = length-1, i, j, k;
do {
d = d/2;
i = 0;
j= i+d;
k = -length+1;
while ( j < k )
{
if (comp(&a[i], &a[j]) >= 0)
swap(a, i, j);
i++;
};
}
while (d > 1);
insertionSort(a, 0, length, comp);
};
Стек в виде односвязного списка:
struct MyStackIterator { struct MyStackIterator *Last; /*<Указатель на предыдущий элемент в стеке.*/ MyStackType Value; /*<Значение.*/ }; struct MyStack {/*<Структура описывающая стек.*/ struct MyStackIterator *TopIter; /*<Указатель на последний элемент в стеке.*/ };
Очередь:
struct MyStackIterator { struct MyStackIterator *Last; /*<Указатель на предыдущий элемент в очереди.*/ MyStackType Value; /*<Значение.*/ }; struct MyStack {/*<Структура описывающая стек.*/ struct MyStackIterator *TopIter; /*<Указатель на последний элемент в очереди.*/ struct MyStackIterator *LowIter; /*<Указатель на первый элемент в очереди. Который будет удаляться.*/ };
Дискретная задача о рюкзаке
W – максимальный вес; ans – матрица возможных решений
int knapsack(vector<int>& wts, const vector<int>& cost, int W) {
int n = wts.size();
vector< vector<int> > ans(W + 1, vector<int>(n+1, 0));
for (int j = 1; j <= n; j++) {
for (int w = 1; w <= W; w++) {
if (wts[j-1] <= w) ans[w][j] = max(ans[w][j - 1], ans[w - wts[j-1]][j - 1] + cost[j-1]);
else ans[w][j] = ans[w][j - 1];
}
}
return ans[W][n];
}
Алгоритм Хиршберга для LCS
Реализация:
Char* LCS(x1, n1, x2, x2) {
If( min( n1, n2) == 0 ) return “”; \\пусто
Else if (n1 == 1) {
If( существует j от 0 до n2: x1[0]==x2[j] ) return x1[0];
Else return “”;
} else {
i=n1/2;
g1=LCS_len(i, x1[0..i], n2, x2[0..n2]); //возвращает всю последнюю строку матрицы. Работает за Ө( min(n1,n2) )
//l1[j]=LCS(x1[0..i], x2[0..j])
g2=LCS_len(n1-i, x1[i+1..n1], n2, x2[0..n2]);
double best=DBL_MIN;
for(j=0; j<n2; ++j) {
if(g1[j]+g2[j]>best) {
best=g1[j]+g2[j];
j0=j;
}
}
G1=LCS(i, x1[0..i], j0, x2[0..j0]);
G2=LCS(n1-I, x1[i+1, n1], n2-j0, x2[j+1 .. n2]);
Return G1+G2;
}
}
Китайская теорема об остатках:
for (int i=0; i<k; ++i) {
x[i] = a[i];
for (int j=0; j<i; ++j) {
x[i] = r[j][i] * (x[i] - x[j]);
x[i] = x[i] % p[i];
if (x[i] < 0) x[i] += p[i];
}
}
Алгоритм Евклида
Int gcd(int a, int b){
If(b==0) return a;
Else return gcd(b,a%b);
}
Graham(Q) выпуклая оболочка:
1)
Пусть
— точка из множества Q с минимальной
координатой y или самая левая из таких
точек при наличии совпадений
2)
Пусть
— остальные точки множества Q,
отсортированные в порядке возрастания
полярного угла,
измеряемого против часовой стрелки относительно точки
(если полярные углы нескольких точек совпадают, то по расстоянию до точки )
3) Push( ,S)
4)
Push(
,S)
5) for i = 2 to m do
6)
while
угол, образованный точками NextToTop(S),Top(S)
и
,
образуют не левый поворот
(при движении по ломаной, образованной этими точками, мы движемся прямо или вправо)
7) do Pop(S)
8) Push( ,S)
9) return S
Jarvis(P)
1) p[1] = самая левая нижняя точка множества P;
2) i = 1;
3) do:
p[i+1] = любая точка из P (кроме уже попавших в выпуклую оболочку, но включая p[1]);
(a)for (для каждой точки j из P, кроме уже попавших в выпуклую оболочку, но включая p[1])
p[i+1] = min_polar_angle(p[i+1], P[j]); // минимум через векторное произведение, как описано выше
(b)i = i + 1;
while p[i] != p[1]
4) return p;
Метод заметающей прямой:
Алгоритм:
Сортируем точки отрезков слева направо.
For каждой точки p
Do
if p - левая конечная точка отрезка s
Then{ Insert(T,s)
If(Above(T,s) существует и пересекает s или Below(T,s) существует и пересекает s)
Then return true;}
If p – правая конечная точка отрезка s
{Then if (сущ Above(T,s) и Below(T,s) и Above(T,s) пересекает Below(T,s))
Then return true
Delete(T,s)}
Return False
Триангуляция Делоне
Алгоритм разделяй и властвуй (Воронов-> Далане):
1)Split(s)-> s1,s2 – разделим множество на 2
2)Bulid (s1),Build (s2) – выполнить 2 триангуляции
3)Merge(s1,s2) – слить
Случаи: треугольник –все ясно, 4-ех угольник – выбираем лучший угол и делаем 2 треугольника, 5-угольник и выше – разбиваем на треугольники
В триангуляцию Далане входят все ребра выпуклой оболочки.
Как построить по 4 точкам Далане?
Описываем круг вокруг ABCD, если D на окружности, то a=угол ADC и b=угол ABC и a+b=Pi
Если точка ушла за окружность (удовлетворение Далане) – то a+b<=Pi. Надо вычислить sin и cos
a+b<=Pi sin(a+b)>=0 sina*cosb+cosa*sinb>=0
-- Алгоритм Косарайю (компоненты сильной связанности)
Инвертируем ребра исходного орграфа.
Запускаем поиск в глубину на этом обращенном графе. В результате получаем вектор обхода.
Запускаем поиск в глубину на исходном графе, в очередной раз выбирая непосещенную вершину с максимальным номером в векторе, полученном в п.2.
Полученные деревья из п.3, и являются сильно связными компонентами.
Интерфейс для Асоциативного кнтейнера
template<Key, Value>
class IMap {
public:
virtual ~IMap() =0; //virtual destructor
virtual bool Insert( Key, Value ) =0; //returns true if a new element was inserted or false if an element with the same key existed (new element wasn't inserted)
virtual bool Exist( Key ) const =0; //returns true if element with specified key exists
virtual void Delete( Key ) =0;
virtual void DeleteAll() =0;
virtual int Size() const =0; //returns number of elements.
virtual const Value* Find( Key ) const =0; //returns 0 if there is no element with specified key in container or pointer to element otherwise
virtual Value* Find( Key ) =0;
virtual const Value& operator[]( Key ) const =0; //returns reference to element that was in container in this moment or throw exception othewise
virtual Value& operator[]( Key ) =0; //returns reference to element that was in container in this moment or newly created element with specified key othewise
};
Примеры хэш-функций:
class CHash
{
public:
int Max;
CHash( int _max = 10 ): Max( _max ) {};
int Hash( int );
int Hash( double );
int Hash( CString );
};
int CHash::Hash( int n ) {
return n % Max;
}
int CHash::Hash( double n ) {
if( n < 1 && n > 0 )
return int( n * Max );
else
return int( n ) % Max;
}
int CHash::Hash( CString str ) {
int result = 0, i = 0;
int k = ( str.Length() - 1 ) % Max;
while( i < k ) {
result += ( int )str[i];
i++;
}
return result % Max;
}
Пример Класса Исключений… кидать - CIllegalOperation e( IOT_not_Square ); throw( e );
Ловить конструкцией try {} catch ( CException& ex );
class CException
{
public:
virtual const char* GetDescription () = 0;
};
class COutofRange: public CException
{
public:
virtual const char* GetDescription () {
return "Out of range";
}
};
enum IllegalOperationType{ IOT_not_Square, IOT_null_Determinant, IOT_matrixSizeIsNotMatch };
class CIllegalOperation: public CException
{
public:
CIllegalOperation( IllegalOperationType error ) : type( error ) { };
const IllegalOperationType type;
virtual const char* GetDescription () {
return "Illegal operation";
}
};
КЧД: \\ кому –то сильно не повезет
template< class KeyType = int, class ValueType = string >
class RBTree
{
public:
class Node
{
public:
KeyType Key;
ValueType Value;
Node* l, r, p;
int color;
};
Node *root;
int size;
/////////////////
class Iterator
{
private:
Node* node;
RBTree* owner;
public:
Iterator( Node* n = 0, RBTree* own = 0 ) { node = n; owner = own; }
bool operator!=( Iterator rhs ) { return ( node != rhs.node || owner != rhs.owner ); }
void inc();
const KeyType &Key() const { return node->Key; }
ValueType &Value() { return node->Value; }
void ChangeVal( ValueType V ) { node->Value = V; }
int IsNull() { if( ( !node ) && ( !owner ) ) return 0; else return 1; }
int &Color() { return node->color; }
};
///////////////////
class const_Iterator {
private:
Node *node;
RBTree *owner;
public:
const_Iterator(Node* n = 0, RBTree* own = 0 ) { node = n; owner = own; }
bool operator!=( const_Iterator rhs ) { return ( node != rhs.node || owner != rhs.owner ); }
void inc();
const KeyType &Key() const { return node->Key; }
const ValueType &Value() const { return node->Value; }
int IsNull() { if( ( !node ) && ( !owner ) ) return 0; else return 1; }
int& Color() const { return node->color; }
};
RBTree();
Iterator begin();
Iterator end();
const_Iterator cbegin();
const_Iterator cend();
Iterator find( KeyType k );
void ChangeValue( KeyType K, ValueType V );
int GetSize() { return size; }
void Print();
int Count( KeyType k );
void Clear();
void Insert( KeyType K, ValueType V );
void InsertFixUp( Node* node );
void LeftRotate( Node* x );
void RightRotate( Node* y );
Node* NodeSearch( KeyType K );
void Del( KeyType K );
void DeleteFixUp( Node* node );
};
template< class KeyType = int, class ValueType = string >
void RBTree::Del( KeyType K ) {
Node *x, *y;
Node *z;
z = ( *this ).NodeSearch( K );
if( !z )
return;
x = z;
if( ( !z->l ) || ( !z->r ) )
y = z;
else {
y = z->r;
while( y->l )
y = y->l;
}
if( y->l )
x = y->l;
else
x = y->r;
if( x )
x->p = y->p;
if( y->p )
if( y == y->p->l )
y->p->l = x;
else
y->p->r = x;
else
root = x;
if( y != z ) {
z->Value = y->Value;
z->Key = y->Key;
}
if( ( y->color == 0 ) && ( x != NULL ) )
DeleteFixUp (x);
size--;
delete y;
}
template< class KeyType = int, class ValueType = string >
void RBTree::DeleteFixUp( Node* node ) {
while( ( node != root ) && ( node->color == 0 ) ) {
if( node == node->p->l ) {
Node* x = node->p->r;
if( x->color == 1 ) {
x->color = 0;
node->p->color = 1;
if( node->p )
LeftRotate( node->p );
if( node->p && node->p->r )
x = node->p->r;
}
if( ( x->l && x->l->color == 0 ) && ( x->r && x->r->color == 0 ) ) {
x->color = 1;
node = node->p;
}
else {
if( x->r && x->r->color == 0 ) {
if( x->l )
x->l->color = 0;
x->color = 1;
RightRotate( x );
if( node->p )
x = node->p->r;
}
x->color = node->p->color;
if( node->p )
node->p->color = 0;
if(x->r)
x->r->color = 0;
if(node->p)
LeftRotate( node->p );
node = root;
}
}
else {
Node* x = node->p->l;
if( x->color == 1 ) {
x->color = 0;
if( node->p )
node->p->color = 1;
if( node->p )
RightRotate( node->p );
if( node->p && node->p->l )
x = node->p->l;
}
if ( ( x->r && x->r->color == 0 ) && ( x->l && x->l->color == 0 ) ) {
x->color = 1;
if( node->p )
node = node->p;
}
else {
if( x->l && x->l->color == 0 ) {
if( x->r )
x->r->color = 0;
x->color = 1;
LeftRotate( x );
if( node->p )
x = node->p->l;
}
if( node->p ) {
x->color = node->p->color;
node->p->color = 0;
}
if( x->l )
x->l->color = 0;
if( node->p )
RightRotate( node->p );
node = root;
}
}
}
node->color = 0;
}
template< class KeyType = int, class ValueType = string >
void RBTree::LeftRotate( Node* x ) {
if( ( !x ) || ( !x->r ) )
return;
Node* y = x->r;
x->r = y->l;
if( y->l )
y->l->p = x;
y->p = x->p;
if( !x->p )
root = y;
else
if( x == x->p->l )
x->p->l = y;
else
x->p->r = y;
y->l = x;
x->p = y;
}
template< class KeyType = int, class ValueType = string >
void RBTree::RightRotate( Node* y ) {
if( ( !y ) || ( !y->l ) )
return;
Node* x = y->l;
y->l = x->r;
if( y->l )
y->l->p = y;
x->p = y->p;
if( !y->p )
root = x;
else
if( y == y->p->r )
y->p->r = x;
else
y->p->l = x;
x->r = y;
y->p = x;
}
template< class KeyType = int, class ValueType = string >
void RBTree::Insert( KeyType K, ValueType V ) {
Node* node = new Node;
node->l = node->r = node->p = 0;
node->color = 0;
node->Key = K;
node->Value = V;
if ( !root ) {
root = node;
root->p = 0;
InsertFixUp( node );
size++ ;
return;
}
Node *x = root, *x_parent = 0;
while( x ) {
if( node->Key == x->Key ) {
delete node;
return;
}
else
if( node->Key < x->Key ) {
x_parent = x;
x = x->l;
}
else {
x_parent = x;
x = x->r;
}
}
node->p = x_parent;
if( node->Key < x_parent->Key )
x_parent->l = node;
else
x_parent->r = node;
InsertFixUp( node );
size++;
return;
}
template< class KeyType = int, class ValueType = string >
void RBTree::InsertFixUp( Node* node ) {
node->color = 1;
while( ( node != root ) && ( node->p->color == 1 ) ) {
if ( node->p == node->p->p->l ) {
Node *x = node->p->p->r;
if( x && x->color == 1 ) {
node->p->p->color = 1;
node->p->color = 0;
x->color = 0;
node = node->p->p;
}
else {
if( node->p->r && node == node->p->r ) {
node = node->p;
LeftRotate( node );
}
node->p->color = 0;
if( node->p->p ) {
node->p->p->color = 1;
RightRotate( node->p->p);
}
}
}
else {
Node *x = node->p->p->l;
if( x && x->color == 1 ) {
node->p->p->color = 1;
node->p->color = 0;
x->color = 0;
node = node->p->p;
}
else {
if( node->p->l && node == node->p->l ) {
node = node->p;
RightRotate( node );
}
node->p->color = 0;
if( node->p->p ) {
node->p->p->color = 1;
LeftRotate( node->p->p );
}
}
}
}
root->color = 0;
}
B - Tree
Структура и принципы построения
B-деревом называется дерево, удовлетворяющее следующим свойствам:
Каждый узел содержит хотя бы один ключ. Ключи в каждом узле упорядочены. Корень содержит от 1 до 2t-1 ключей. Любой другой узел содержит от t-1 до 2t-1 ключей. Листья не являются исключением из этого правила. Здесь t - параметр дерева, не меньший 2 (и обычно принимающий значения от 50 до 2000[1]).
У листьев потомков нет. Любой другой узел, содержащий ключи
,
..., 
,
содержит 
сыновей.
При этомПервый сын и все его потомки содержат ключи из интервала
Для
,
i-й сын и все его потомки содержат ключи
из интервала 
-й
сын и все его потомки содержат ключи
из интервала 
Глубина всех листьев одинакова.
Свойство 2 можно сформулировать иначе: каждый узел B-дерева, кроме листьев, можно рассматривать как упорядоченный список, в котором чередуются ключи и указатели на сыновей.
[Править]Поиск
Если ключ содержится в корне, он найден. Иначе определяем интервал и идём к соответствующему сыну. Повторяем, пока не дошли до листа.
[Править]Добавление ключа
Будем называть деревом потомков некоего узла поддерево, состоящее из этого узла и его потомков.
Вначале
определим функцию, которая добавляет
ключ K к дереву потомков узла x. После
выполнения функции во всех пройденных
узлах, кроме, может быть, самого узла x,
будет меньше 
,
но не меньше 
,
ключей.
Если х - не лист,
Определяем интервал, где должен находиться K. Пусть y - соответствующий сын.
Рекурсивно добавляем K к дереву потомков y.
Если узел y полон, то есть содержит ключей, расщепляем его на два. Узел
получает
первые
из
ключей y и первые 
его
потомков, а узел 
-
последние
из
ключей y и последние
его
потомков. Медианный из ключей узла y
попадает в узел х, а указатель на y в
узле x заменяется указателями на
узлы
и
.
Если x - лист, просто добавляем туда ключ K.
Теперь определим добавление ключа K ко всему дереву. Буквой R обозначается корневой узел.
Добавим K к дереву потомков R.
Если R содержит теперь ключей, расщепляем его на два. Узел
получает
первые
из
ключей R и первые
его
потомков, а узел 
-
последние
из
ключей R и последние
его
потомков. Медианный из ключей узла R
попадает вo вновь созданный узел, который
становится корневым. Узлы
и
становятся
его потомками.
[Править]Удаление ключа
Если
корень одновременно является листом,
то есть в дереве всего один узел, мы
просто удаляем ключ из этого узла. В
противном случае сначала находим узел,
содержащий ключ, запоминая путь к нему.
Пусть этот узел - 
.
Если
-
лист, удаляем оттуда ключ. Если в
узле
осталось
не меньше
ключей,
мы на этом останавливаемся. Иначе мы
смотрим на количество ключей в следующем,
а потом в предыдущем узле. Если следующий
узел есть, и в нём не менее
ключей,
мы добавляем в
ключ-разделитель
между ним и следующим узлом, а на его
место ставим первый ключ следующего
узла, после чего останавливаемся. Если
это не так, но есть предыдущий узел, и в
нём не менее
ключей,
мы добавляем в
ключ-разделитель
между ним и предыдущим узлом, а на его
место ставим последний ключ предыдущего
узла, после чего останавливаемся.
Наконец, если и с предыдущим ключом не
получилось, мы объединяем узел
со
следующим или предыдущим узлом, и в
объединённый узел перемещаем ключ,
разделяющий два узла. При этом в
родительском узле может остаться
только 
ключей.
Тогда, если это не корень, мы выполняем
аналогичную процедуру с ним. Если мы в
результате дошли до корня, и в нём
осталось от 1 до
ключей,
делать ничего не надо, потому что корень
может иметь и меньше
ключей.
Если же в корне не осталось ни одного
ключа, исключаем корневой узел, а его
единственный потомок делаем новым
корнем дерева.
Если
-
не лист, а K - его 
-й
ключ, удаляем самый правый ключ из
поддерева потомков
-го
сына
,
или, наоборот, самый левый ключ из
поддерева потомков 
-го
сына
.
После этого заменяем ключ K удалённым
ключом. Удаление ключа происходит так,
как описано в предыдущем абзаце.
Графы ДФС
template< class Value >
vector< int > CGraph< Value >::DFS( int first ) {
vector< int > color( vertexcount );
vector< int > time_in( vertexcount ), time_out( vertexcount );
int dfs_timer = 0;
time_in[first] = dfs_timer++;
color[first] = 1;
void dfs( int n ) {
for( vector< CPair< int, Value > >::iterator it = list[first].begin(); it != list[first].end(); ++i ) {
if( color[ (*i).key ] == 0 )
dfs( (*i).key );
}
}
color[first] = 2;
time_out[first] = dfs_timer++;
vector< int > result;
for( int i = 0; i < dfs_timer; ++i )
for( int j = 0; j < vertexcount; ++j )
if( time_in[j] == i )
result.push_back( j );
return result;
}
template< class Value >
vector< int > CGraph< Value >::ShortestWay( int first, int second ) {
queue< int > q;
q.push( first );
vector< bool > used( vertexcount );
vector< int > result;
used[first] = true;
while ( !q.empty() ) {
int v = q.front();
result.push_back( v );
if( v == second )
return result;
q.pop();
for( unsigned int i = 0; i < list[v].size(); ++i ) {
int to = list[v][i].key;
if ( !used[to] ) {
used[to] = true;
q.push( to );
}
}
}
WayDoesntExist err;
throw err;
}
template< class Value >
vector< int > CGraph< Value >::BFS( int first ) {
queue< int > q;
q.push( first );
vector< bool > used( vertexcount );
vector< int > result;
used[first] = true;
while ( !q.empty() ) {
int v = q.front();
result.push_back( v );
q.pop();
for( unsigned int i = 0; i < list[v].size(); ++i ) {
int to = list[v][i].key;
if ( !used[to] ) {
used[to] = true;
q.push( to );
}
}
}
return result;
}
Топологическая сортировка
Пусть
дан бесконтурный ориентированный
простой граф 
.
Через 
обозначим
множество вершин таких, что 
.
То есть, 
—
множество всех вершин, из которых есть
дуга в вершину 
.
Пусть 
—
искомая последовательность вершин.
пока
выбрать
любую
вершину
такую, что
и
удалить
из всех
Наличие хотя бы одного контура в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину .\\\\\\с хабра
Запускаем обход в глубину, и когда вершина обработана, заносим ее в стек. По окончании обхода в глубину вершины достаются из стека. Новые номера присваиваются в порядке вытаскивания из стека. Цвет: во время обхода в глубину используется 3 цвета. Изначально все вершины белые. Когда вершина обнаружена, красим ее в серый цвет. Когда просмотрен список всех смежных с ней вершин, красим ее в черный цвет.
void dfswithtopologicalsort(int v) { int i; if(used[v]==1) return; used[v]=1; for(i=1;i<=n;i++) { if (a[v][i]==1 && used[i]==0) dfs(i); } stack[j]=v; j++; }