|
3. Graflarda kórik ótkeriw
Grafni kórikten ótkeriw (Graph traversal) - bul berilgen túyinnen baslap barlıq túyinlerdi bir retten kórip shıǵıw ámeli bolıp tabıladı.
Kórikten ótkeriw eki usılı ámeldegi:
Tereńligine (tubiga) qaray qıdırıw (Depth-First Search - DFS)
Keńligine (enine) qaray qıdırıw (Breadth-First Search - BFS)
Bul usıllar berilgen X túyinnen baslap qandayda bir konteynerni qollaǵan halda barlıq túyinlerdi kórip shıǵadı.
Tereńlikke qaray kóriwde stek strukturası qollanıladı.
Keńlikke qaray kóriwde bolsa gezek strukturasınan paydalanıladı.
Tubiga qaray kórikti otırǵızıw psevdokodi tómendegishe ámelge asıriladı
Kirisiw: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Shıǵıw : tóbelikten DFS 2: 2 0 1 3
DFS diagramması :
Algoritm :
Túyin hám kelilgen qatar indeksin alatuǵın rekursiv funktsiyanı jaratıń.
Ámeldegi túyindi kelgen retinde belgileń hám túyindi baspadan shıǵarıń.
Barlıq qońsılas hám belgilenmagan túyinlerdi aylanıp ótiń hám qońsılas túyin kórsetkishi menen rekursiv funktsiyanı shaqırıń.
// den DFS ótkeriliwin baspadan shıǵarıw ushın C ++ programması
// berilgen qana daǵı berilgen tóbelik
#include
using namespace std;
// Grafik klassi jóneltirilgen grafikanı ańlatadı
// qońsılas diziminen paydalanıp
class Graph {
int v; // Tóbelikler sanı
// óz ishine alǵan qatarǵa kórsetkish
// qońsılas dizimler
list* adj;
// DFS tárepinen qollanılatuǵın rekursiv funktsiya
void DFSUtil (int v, bool visited[]);
public:
Graph (int v); // Konstruktor
// grafikka shet qosıw funktsiyası
void addEdge (int v, int w);
// tóbeliklerdiń DFS ótiwi
// v den paydalanıw múmkin
void DFS (int v);};
Graph::Graph (int v) {
this->v = v;
adj = new list[v];}
void Graph::addEdge (int v, int w) {
adj[v].push_back (w); }// v dıń dizimine w ni áskerg.
void Graph::DFSUtil (int v, bool visited[]) {
// Ámeldegi túyindi kelgen retinde belgileń hám
// onı baspadan shıǵarıń
visited[v] = true;
cout << v << " ";
// Qońsılas bolǵan barlıq tóbelikler ushın tákirarlang
// bul tóbelikke
list::iterator i;
for (i = adj[v]. begin (); i! = adj[v]. end (); ++i)
if (! visited[*i])
DFSUtil (*i, visited);}
// tóbeliklerdiń DFS aralıǵinda v ga erisiw múmkin.
// Bul rekursiv DFSUtil () den paydalanadı
void Graph::DFS (int v) {
// Barlıq tóbeliklerdi kelilmagan dep belgileń
bool* visited = new bool[v];
for (int i = 0; i < v; i++)
visited[i] = false;
// Rekursiv járdemshi funktsiyanı shaqırıń
// DFS-ni basıp ótiwdi baspadan shıǵarıw ushın
DFSUtil (v, visited);}
int main () {
// Joqarıdaǵı diagrammada berilgen grafikanı jaratıń
Graph g (4);
g. addEdge (0, 1);
g. addEdge (0, 2);
g. addEdge (1, 2);
g. addEdge (2, 0);
g. addEdge (2, 3);
g. addEdge (3, 3);
cout << " Tómendegi birinshi traversal tereńligi"
" (tóbelik 2 den baslap ) \n";
g. DFS (2);
return 0;
}
Nátiyje: Tómendegi birinshi traversal tereńligi (tóbelik 2 den baslap ) : 2013
Keńlik boyınsha birinshi qıdırıw yamasa grafik ushın BFS
Grafika ushın keńlik birinshi ótiw (yamasa qıdırıw ) terektiń birinshi keńlik boylap háreketleniwine uqsaydı ( bul xabardıń 2-usılına qarang ). Tereklerden ayrıqsha bolıp esaplanıw, grafikalar cikllerdi óz ishine alıwı múmkin, sol sebepli biz taǵı bir túyinge keliwimiz múmkin. Túyindi bir neshe ret qayta islewge jol qoymaw ushın biz logikalıq kelilgen qatardan paydalanamız. Ápiwayılıq ushın barlıq tóbeliklerge baslanǵısh tóbelikten erisiw múmkin dep shama etiledi.
Mısalı, tómendegi qanada biz ótiwdi 2-shi tepadan baslaymız. 0 -ne shıńǵa kelip, onıń barlıq qońsılas tóbelerin izleymiz. 2 de 0 ge teń bolǵan vertex bolıp tabıladı. Eger biz kelgen tóbelerdi belgilemasak, ol halda taǵı 2 qayta isletilinip, ol tawsılmaytuǵın processga aylanadı. Tómendegi grafikdıń birinshi keńligi 2, 0, 3, 1 ge teń.
Tómende berilgen derekten ápiwayı Breadth First Traversal programmasınıń ámelleri keltirilgen.
// Berilgeninen BFS ótiwin baspadan shıǵarıw programması
// derek vertex. BFS (int s) tóbeliklerdi kesip ótedi
// lardan paydalanıw múmkin.
#include
#include
using namespace std;
// Bul klass járdeminde jóneltirilgen grafikanı ańlatadı
// qońsılas diziminiń kórgezbesi
class Graph{
int v; // tóbelikler sanı
// Jaqınlıqtı óz ishine alǵan qatarǵa kórsetkish
// dizimler
list *adj;
public:
Graph (int v); // Konstruktor
// qanaǵa shet qosıw funktsiyası
void addEdge (int v, int w);
// berilgen derekten BFS ótkeriliwin baspadan shıǵaradı
void BFS (int s);};
Graph::Graph (int v) {
this->v = v;
adj = new list[v];}
void Graph::addEdge (int v, int w) {
adj[v].push_back (w);} // v dıń dizimine w ni áskerg.
void Graph::BFS (int s) {
// Barlıq tóbeliklerdi kelilmagan dep belgileń
bool *visited = new bool[v];
for (int i = 0; i < v; i++)
visited[i] = false;
// BFS ushın gezek jaratıw
list queue;
// Ámeldegi túyindi kelgen retinde belgileń jáne onı dizimnen ótkeriń
visited[s] = true;
queue.push_back (s);
// 'i' barlıq qońsılas jaylardı alıw ushın isletiledi
// tóbelik tóbeleri
list::iterator i;
while (! queue. empty ()) {
// Tóbelikti náwbetten alın jáne onı baspadan shıǵarıń
s = queue. front ();
cout << s << " ";
queue.pop_front ();
// Dequiatsiyalangan barlıq qońsılas tóbeliklerdi alın
// vertex s. Eger qońsılas jayǵa kelilmagan bolsa,
// keyin kelgenligin belgileń jáne onı dizimnen ótkeriń
for (i = adj[s]. begin (); i! = adj[s]. end (); ++i) {
if (! visited[*i]) {
visited[*i] = true;
queue.push_back (*i);}}}}
// Grafik klassi usılların sınap kóriw ushın aydawshı programması
int main ()
{
// Joqarıdaǵı diagrammada berilgen grafikanı jaratıń
Graph g (4);
g. addEdge (0, 1);
g. addEdge (0, 2);
g. addEdge (1, 2);
g. addEdge (2, 0);
g. addEdge (2, 3);
g. addEdge (3, 3);
cout << " Tómendegi keńlik birinshi traversal "
<< " (tóbelik 2 den baslap ) \n";
g. BFS (2);
return 0;
}
Paydalanilg’an adebiyatlar
AdamDrozdek. Data structure and algorithms in C++. Fourth edition. 2013. Chapter 8. 391-490 betlar.
A computer science portal for geeks. http://www.geeksforgeeks.org/data-structures/#Graph
http://www.tutorialspoint.com/data_structures_algorithms/graph_data_structure.htm
Do'stlaringiz bilan baham: |
