Эйлер тартиби боздиди қуллаҳо
Қирраҳоро метавон аз рӯи вақти даромад ва баромади қуллаҳои ниҳоии ва -и қирраи тасниф кард.
Чунин таснифот аксар вақт дар масъалаҳои гуногун истифода мешавад.
DFS иҷро мешавад, ва ҳамаи қирраҳои вохӯрдашудаи мувофиқи қоидаҳои зерин тасниф мешаванд:
Агар қуллаи боздид нашуда бошад:
Агар қуллаи аллакай боздид шуда бошад:
Қирраҳои бозгашт (Back Edges) — агар аҷдоди бошад, пас қирраи бозгаштӣ мебошад.
Қуллаи аҷдоди мебошад танҳо ва танҳо вақте ки мо аллакай ба даромадаем, аммо ҳанӯз аз он набаромадаем.
Қирраҳои бозгашт даврро анҷом медиҳанд, зеро роҳе аз аҷдоди ба фарзанди (дар дарахти DFS) ва қиррае аз фарзанди ба аҷдоди (қирраи бозгашт) вуҷуд дорад. Ҳамин тавр давр ҳосил мешавад.
Даврҳоро метавон бо ёрии қирраҳои бозгашт ошкор кард.
Қирраҳои мустақим (Forward Edges) — агар фарзанди бошад, пас қирраи мустақим мебошад.
Ба ибораи дигар, агар мо аллакай -ро боздид карда аз он баромада бошем ва ҳамзамон , пас қирраи мустақим мебошад.
Қирраҳои салибӣ (Cross Edges) — агар на аҷдод ва на фарзанди бошад, пас қирраи салибӣ мебошад.
Ба ибораи дигар, агар мо аллакай -ро боздид карда аз он баромада бошем ва ҳамзамон , пас қирраи салибӣ мебошад.
Дар ин ҷо:
Эзоҳ:
Ҳангоми иҷрои DFS ба ҳар як қуллаи ду лаҳзаи вақт мувофиқ карда мешаванд:
Агар ҳангоми DFS қуллаҳоро ба массив бо тартиби даромад (аз рӯи ) сабт кунем, хусусияти калидӣ ба вуҷуд меояд:
Ҳамаи қуллаҳои зердарахти қуллаи як порчаи пайвастаро дар тартиби ташкил медиҳанд.
Қуллаи дар зердарахти қуллаи ҷойгир аст танҳо ва танҳо вақте ки
Ин хусусияти бунёдии рақамгузории DFS мебошад.
DFS чунин сохта шудааст:
Аз ин рӯ:
Бинобар ин қиматҳои -и онҳо дар дохили интервали ҷой мегиранд.
Қуллаи аҷдоди қуллаи мебошад танҳо ва танҳо вақте ки
Хусусияти tin/tout имкон медиҳад масъалаҳоро дар дарахт ба масъалаҳо дар массив оварда расонем.
Зердарахти қулла ба порча табдил меёбад:
Аз ин рӯ бисёр масъалаҳо дар дарахтҳо бо сохторҳо барои массивҳо ҳал мешаванд:
int tim; // timer
int tin[N]; // time when dfs got in to vertex x
int tout[N]; // time when dfs gout out from vertex x
bool used[N]; // true if vertex x was visited
vector<int> v[N]; // edges
void dfs(int x) {
used[x] = true; // mark current vertex as visited
tin[x] = (++timer); // time when x is visited
for (int y: v[x]) {
if (used[y]) { // already visited vertex
if (tout[y] == 0) { // dfs didn't get out yet from vertex y
// back edge
} else if (tin[x] < tin[y]) {
// forward edge
} else {
// cross edge
}
continue;
}
// (x, y) is tree edge
dfs(y);
}
tout[x] = timer; // time when dfs gets out from vertex x
}