Граф гэж юу вэ?
- Wikipedia: Ирмэг болон оройгоос бүтсэн бүтцийг граф гэнэ.
- Би: заа
Граф нь зүйлсийн холбоо хамаарлыг дүрсэлсэн нэг хэлбэр гэж хэлж болно. Жишээ нь найзуудын хамаарлыг авж үзье. A нь B-тэй найз, B нь C-тэй найз, C нь D-тэй найз ба D нь A-тай мөн B-тэй найз гэвэл. Бид тухайн хүмүүсийг орой гэж хэлээд хоорондын найзын холбоосыг ирмэг гээд
иймэрхүү байдлаар дүрсэлж болохнээ. Тэгвэл энэхүү граф нь 4 оройтой 5 ирмэгтэй холбоост граф байх нь. Холбоост граф гэдэг нь нэг оройгоос нөгөө оройд ирмэгүүдээр дамжин хүрэх боломжтой графыг хэлнэ. Найзуудын хувьд хамгийн том графын сүлжээг бид Facebook-с харж болохнээ.
Аа харин instagram, twitter-н хувьд арай өөр граф байна. Учир нь A нь B-г дагалаа гэдэг нь B нь A-г дагадаг гэсэн үг биш билээ. Үүндээр нэг жишээ авбал A нь B-г дагадаг, B-нь C-г дагадаг, C-нь A, B-г дагадаг, D-нь бүгдийг нь дагадаг гэе.
Графыг computer-т
Энэхүү бүтцийг яаж computer-т хадгалах вэ? Бид тоо, тэмдэгт, array гэх мэт олон төрлийн бүтэц харсан ба үүнийгээ ашиглан хэрхэн хадгалж болох тухай ярилця. Мэдээж та бүхэн өөрсдөө хэлбэр гаргаад дүрслэх бүрэн боломжтой.
Матриц хэлбэр
Граф нь N оройтой гэвэл NxN Матриц буюу 2 хэмжээст array-р дүрсэлж болно. тухайн матрицийг A гэвэл A[i][j] буюу
i-р мөрний j-р элэмэнти нь i-р оройгоос j-р орой луу шууд холбогдсон ирмэг байгаа эсэхийг илэрхийлнэ. Заа тэгээд
A[i][j] нь 0 гэвэл ирмэг байхгүй 1 гэвэл байгаа хэрвээ жинтэй граф байвал тухайн ирмэгийн жингээр утга оноох нь бий.
Ашигтэй тал нь бид хоёр оройн хооронд ирмэг байгаа эсэхийг шууд мэдэж чадна, мөн математик тооцоолол хийхэд хялбар.
Сул тал нь бол санах ойн хувьд хэтэрхий том болох боломжтой. Жишээ нь төсөөлийлдөө FB дээр хүн ихдээ л 5000 найзтай байж болно. Тэгхэд хэдэн тэрбум хэрэглэгч байгаашүүдээ. N^2 эрэмбийн ирмэгтэй харьцуулахад хажууд нь хамаагүй бага ба бидний матрицын ихэнхи газар нь 0 байхнээ. Ер нь амьдрал дээрх холбоог авж үзэхэд бид бүх хүнтэй найз биш шүүдээ. Миний хувьд бол Монголын 3сая хүнэээс үсрээл 300 хүний нэрийг мэднэ гэж бодож байна.
Хөршийн холбоос
Санах ойгоо хэрхэн бууруулж болох вэ? A матрицийг хураангуйгаар хадгалах ба ингэхдээ
A[i] гэсэн array-нь i-р оройтой шууд ирмэгээр холбогдсон оройнуудын жагсаалтыг хадгалах юм.
Ингэснээр бидний санах ой N^2-с ирэмгийн тооруу бууж багаслаа.
Бид үүнийг vector ашиглан хадгалж болно. Учир нь хэмжээгээ өөрчилж чаддаг тул бидэнд ашигтай.
Мэдээж санах ойн хувьд багассан ч гэлээ зарим тохиолдолд тийм ч ашигтай бүтэц биш юм. Жишээ нь бид хоёр орой холбогдсон эсэхийг шууд мэдэж чадахгүй.
Граф дээр гүйх
Мэдээж бид дүрсэлж болон хадгалаад л болчихгүй. Граф дээр олон зүйлс хийж болно. Жишээ нь ямар нэг граф өгөгдөхөд
- граф нь хэдэн тусдаа хэсэгт байгаа вэ?
- нэг оройгоос нөгөө оройд хамгийн багадаа хэдэн орой дамжин очих вэ?
- нэг оройгоос очиж болох бүх боломжит оройг ол?
гэх мэд маш олон зүйлс яригдах ба хэдүүлээ жишээ хэдэн гүйлт хийцгээе
BFS
Түвшний нэвтрэлт(BFS-Breadth first search)-н тухай. Ерөнхий санаа нь тухайн оройг 0-р түвшин гэе. Тэгээд тухайн оройн хөрш оройнуудыг 1-р түвшин. Хөршийн хөрш оройг 2р түвшин гэх мэт нэг түвшин нэмээд графаар аялахыг хэлж байгаа.
Бодлого
Бидэнд граф, мөн хоёр орой өгөгдөх ба энэ хоёр оройн хооронд хамгийн багадаа хэдэн ширхэг оройгоор дамжин очих вэ? гэсэн бодлогыг бодоцгооё
Бид X гэсэн орой дээр байгаа. Y орой хүрэх хамгийн богино замыг олцгооё. X орой дээр 0 зам туулж ирсэн гэж үзэж болно. Мөн энэ оройг 0-р түвшин гэе. Тэгвэл 1 гэсэн түвшинтэй орой гэж ямар оройг хэлэх вэ? Энэ оройнууд бол X оройтой шууд ирмэгээр холбогдсон оройнууд юм. Тэгвэл 1-р түвшинтэй орой дээр 1 гэсэн зам туулж ирнэ. Тэгвэл 2-р түвшин гэдэг нь 1-р түвшний оройтой шууд ирмэгээр холбогдсон оройнууд байх юм. Энэд нэг анхаарах зүйл байгаа нь өмнөх түвшинд энэ орой байсан бол бид энэ оройг 2-р түвшин гэж хэлэх нь буруу юм. Тиймээс өмнө нь ирээгүй орой буюу шинэ оройд л түвшний утга өгөх нь зүйтэй. Энэ мэтчилэн бид X орой буюу 0-р түвшнээс Y орой таартал түвшинг нэмсээр байх болно. Ингээд Y орой дээр ирэх үед энэ түвшин нь X оройгоос Y орой хүртэлх хамгийн бага замын урт байх юм.
Энгийнээр төсөөлбөл бид графын ирмэгүүдийг хоолой гэж төсөөлье. Тэгвэл бид X оройгоос ус асгасан гэж үзье. Энэ ус нь эхлээд X оройгоос гарсан бүх хоолойгоор урсана. Дараа нь тэр оройнуудаас гарсан хоолойнуудаар урсана. Ямар нэг орой дээр ус анх удаа ирж байгаа бол X оройгоос ирж болох хамгийн бага зам туулж ирсэн гэсэн үг. Харин анх удаа биш бол энэ орой дээр ус аль хэдийнээ ирж амжсан тул энэ явалт нь ашиггүй. Гол санаа нь нэг нэг түвшнээр ахиж байгаад оршино.
A-с түвшний нэвтрэлт явахад
Кодыг нь хэрхэн бичих вэ? Бид queue гэсэн бүтцийг ашиглан бичнэ(Яагаад vector эсвэл өөр бүтэц биш вэ?). Queue нь хос байх ба эхнийх нь одоо явж байгаа оройг харин дараагийнх нь одоо явж байгаа түвшинг авна. Queue-д хамгийн эхлээд X, 0 гэсэн хосыг нэмж өгнө. Бид queue-ын хамгийн эхний элементийг авах буюу X, 0 гэсэн хосыг авна. Энэ нь X орой дээр хамгийн багадаа 0 гэсэн утгаар ирж чадсан гэж үзэж байгаа тул X оройг ирсэн гэж тэмдэглэнэ. Дахиж энэ оройгоос явах шаардлагагүй(ус урсгах шаардлагагүй. Усаа хэмнэ). Харин дараа нь бид X оройтой шууд ирмэгээр холбогдсон бүх оройг queue-д нэмж өгөх ба нэмэхдээ эхний утга нь тэр орой харин хоёр дахь утга нь 1 байх болно. Энэ оройнуудын түвшин 1. Ингээд энэ оройгоос бүгд урсаж чадсан. Дараагийн түвшинлүү орох ёстой тул үүнийг queue-ээс хасах хэрэгтэй. Харин дараа нь давталт эхнээсээ эхэлнэ. 1-р түвшинтэй хамгийн эхний орой гарж ирнэ. Энэ оройтой шууд холбогдсон өмнө нь очоогүй бүх оройг 2 гэсэн утгатай хос болгон queue-д нэмнэ. Тэгээд үүнийг хасаад. Дараагийн 1-р түвшний оройруу шилжинэ. Гэх мэт Y оройтой таартал явах юм. Энэ алгоритм нь өгөгдсөн оройгоос бүх холбоотой орой хүртэлх хамгийн богино замыг олж байгаа юм.
// Түвшний нэвтрэлт. BFS
#include <queue>
#include <iostream>
using namespace std;
int n, m; // оройн тоо, ирмэгийн тоо
bool vis[50000]; // ирсэн ирээгүйг хадгалах массив.
vector<int> adj[50000]; // графын мэдээллийг хадгалах вектор.
queue< pair<int,int> > q; // bfs явах queue
int main() {
cin >> n >> m; // орой, ирмэгийн тоонуудыг унших.
for(int i = 1; i <= m; i++) {
int u, v; // i-р ирмэгийг тодорхойлох 2 орой.
// u болон v орой холбогддог гэсэн утгатай тул
cin >> u >> v;
adj[u].push_back( v );
adj[v].push_back( u );
}
int x, y; // x-ээс y хүртэл
cin >> x >> y; // хүсэлтээ унших
q.push( make_pair( x, 0 ) ); // анх x оройдээр 0 утгаар
while( !q.empty() ) { // хоосон биш л бол үргэлжилнэ.
int nowU = q.front().first; // одоо явж байгаа орой.
int nowW = q.front().second; // одоо явж байгаа оройн түвшин
vis[nowU] = 1; // nowU оройг ирсэн гэж тэмдэглэнэ.
if( nowU == y ) {
// nowU орой нь бидний хайсан Y орой бол энэ хүрээд зогсоно.
cout << nowW << endl; // хамгйин бага зардал.
return 0; // программыг зогсоож болно гэсэн үг юм.
}
q.pop(); // дараагийн элемэнтээс явах ёстой тул үүнийг устгана.
for(int i = 0; i < adj[nowU].size(); i++) {
int v = adj[nowU][i]; // одоо байгаа оройтой шууд ирмэгээр холбогдсон орой.
if( !vis[v] ) { // v орой тэмдэглэгдээгүй бол очиж ёстой.
q.push( make_pair( v, nowW+1 ) ); // энэ оройдээр одоо байгаа
// түвшиндээр нэмэх нь 1-ээр ирнэ.
}
}
}
cout << "Ochih bolomjgui!\n"; // хэрвээ бүрэн зогсоогүй бол очиж
// чадаагүй буюу очих боломжгүй гэсэн үг.
return 0;
}
DFS
DFS(Depth First Search)-н тухай буюу гүний нэвтрэлт гэх алгоритмын тухай бичих болно. DFS гол санаа нь тухайн оройгоос эхлээд таарсан хамгийн эхний хөрш оройруугаа очоод тэрхүү хөршийн хамгийн эхний хөрш орой руу дараа нь очно. Тэгээд тэрний хамгийн эхний хөрш гэхд мэтээр буюу эхний хүрж болох гүндээ хүрээд буцаад дараагийн хүрж болох гүнрүү явдаг.
Бид энэхүү санааг sqaure maze-шиг төсөөлж болно. Shining, Pan’s Labyrinth, Harry Potter and the Goblet of Fire гэх мэт кинондээр гардаг шиг. Нэг замаараа яваад гацвал буцаад дараагийн замаар явах юм. Гэхдээ мэдээж амьдрал дээр явсан эсэхээ санахад хэцүүлдээ бид гэхдээ computer-т бичиж байнашүүдээ.
Энэхүү коддээр DFS-г recursive ашиглан бичсэн бөгөөд stack ашиглан бичээд үзээрэй.
Бодлого
Бидэнд нэг граф өгөгдсөн ба энэ графт хэдэн компонент буюу хэдэн салангид хэсэг байгааг ол.
Бид 1-р оройгоос энэ оройтой холбогдсон эхний орой луу очъё. Дараа нь тэр оройтой холбогдсон гэхдээ 1-р оройгоос ялгаатай эхний орой луу очъё. Хэрвээ 1-р орой дээр очих юм бол хязгааргүй үргэлжилнэ. Дараа нь тэр оройгоос түүнтэй холбогдсон гэхдээ өмнө нь очоогүй орой луу очно. Энэ мэт бид нэг орой дээр иртэл үүнтэй холбогдсон бүх орой дээр өмнө нь ямар нэгэн байдлаар ирсэн бол яах вэ? Энэ тохиолдолд бид энэ орой дээр ирсэн орой луу буцна гэсэн үг юм. Тэгээд тэр оройн 2дахь өмнө очоогүй орой луу явна. Гэх мэт цааш яваад гацлаа. Тэгвэл дахиад буцна. Гэх мэт үргэлжилсээр дуусахад 1-р оройтой ямар нэгэн байдлаар холбогдсон бүх орой дээр очсон байх болно. Энэхүү бүх орой нь нийлээд 1 холбоот хэсэг бөгөөд 1-р component болно. Хэрвээ ямар нэг i-р орой энэ компонентод орж чадаагүй бол энэ нь тусдаа өөр компонент байгаа бөгөөд энэ оройгоос dfs бичиж холбоост component-г олно. Хэрвээ үгүй бол энэ нь 1-р оройтой ямар нэгэн байдлаар холбогдсон ба эхний компонентод орсон гэсэн үг. Гэх мэт N оройн хувьд явах бөгөөд компонентын тоо гэдэг бол dfs хэдэн удаа хийсэн бэ? гэсэн үг болно.
A-с гүний нэвтрэлт явахад
#include <vector>
#include <iostream>
using namespace std;
int n, m; // орой болон ирмэгийн тоо
int comp; // бидний хариу буюу компонентийн тоо
bool vis[200000]; // ирсэн ирээгүйг хадгалах массив
vector<int> adj[200000]; // графын мэдээллийг хадгалах вектор
void dfs(int u) {
// одоо бид u гэсэн орой дээр ирж байгаа тул
vis[u] = 1; // ирсэн гэж тэмдэглэнэ
for(int v:adj[u]) {
// v:adj[u] гэдэг нь v гэсэн тоо нь adj[u] гэсэн векторт байгаа
// бүх элемэнтийн утгыг авна гэсэн үг ба эхнээс нь дуустал явна
if( !vis[v] ) {
// v гэсэн орой дээр өмнө нь ямар нэгэн байдлаар очоогүй бол
// энэ оройгоос цааш явах ёстой гэсэн үг
dfs(v);
}
}
}
int main() {
cin >> n >> m;
while( m-- ) {
int u, v; // u, v 2 орой хоорондоо шууд ирмэгээр
// холбогддог гэсэн үг
cin >> u >> v;
adj[u].push_back( v );
adj[v].push_back( u );
}
for(int i = 1; i <= n; i++) {
if( !vis[i] ) {
// Энэ нь I-р орой дээр өмнө ямар нэгэн байдлаар очиж чадаагүй
// гэсэн үг тул энэ оройг агуулсан нэг компонент байх нь
// тодохрой тул компонентын тоо нь 1-р нэмэгдэнэ
comp++;
dfs( i ); // энэ оройтой ямар нэгэн байдлаар холбогдсон бүх
// орой нь энэ компонетэд орно.
}
}
cout << comp << endl; // хариуг хэвлэнэ.
return 0;
}
Хураангүй
Граф нь маш том ухагдхуун бөгөөд маш бага зүйлийг бичлээ. Ирмэг болон оройн хоорондын хамаарал дээр Dense, sparse graph-н тухай дэлгэрүүлээд уншаарай.
Кодэндээр алдаа эсвэл асуух, хуваалцах зүйл байвал comment бичээрэй.