Мени

Дубинско прво претраживање (ДФС) Ц ++ програм за прелазак преко графа или стабла

  • Главни
  • Остало
  • Дубинско прво претраживање (ДФС) Ц ++ програм за прелазак преко графа или стабла

depth first search c program traverse graph

Испробајте Наш Инструмент За Елиминисање Проблема

Овај приручник покрива дубинску прву претрагу (ДФС) у Ц ++-у, у којем се графикон или стабло прелази у дубину. Научићете и ДФС алгоритам и имплементацију:

Дубинско прво претраживање (ДФС) је још једна техника која се користи за прелазак стабла или графа.

ДФС започиње коријенским чвором или почетним чвором, а затим истражује суседне чворове тренутног чвора улазећи дубље у графикон или стабло. То значи да се у ДФС чворови истражују дубински док се не наиђе на чвор без деце.

Једном када се достигне чвор листа, ДФС се враћа натраг и започиње истраживање још неких чворова на сличан начин.

=> Овде припазите на водич за обуку за почетнике Ц ++.

Дубинско прво претраживање

Шта ћете научити:

Дубина прво претраживање (ДФС) у Ц ++

За разлику од БФС-а у којем чворове истражујемо у ширини, у ДФС-у чворове истражујемо дубински. У ДФС-у користимо структуру података стека за складиштење чворова који се истражују. Ивице које нас воде до неистражених чворова називају се „ивице откривања“, док се ивице које воде до већ посећених чворова називају „ивице блокова“.

Даље, видећемо алгоритам и псеудо-код за ДФС технику.

ДФС алгоритам

  • Корак 1: У стек уметните основни чвор или почетни чвор стабла или графикона.
  • Корак 2: Отворите горњу ставку из низа и додајте је на посећену листу.
  • Корак 3: Пронађите све суседне чворове чвора означеног као посећено и додајте оне који још нису посећени у стек.
  • 4. корак : Понављајте кораке 2 и 3 док се стек не испразни.

Псеудоцоде

Псеудо-код за ДФС дат је у наставку.

Псеудо-код за ДФС

Из горњег псеудо-кода примећујемо да се алгоритам ДФС позива рекурзивно на сваком вертексу како би се осигурало да су сви врхови посећени.

Прелази са илустрацијама

Хајде да илуструјемо ДФС-ов прелазак графика. Ради јасноће користићемо исти графикон који смо користили на илустрацији БФС.

ДФС илустрације са прелазима

Нека је 0 почетни чвор или изворни чвор. Прво га означавамо као посећено и додајемо на листу посећених. Затим гурнемо све његове суседне чворове у стог.

Потисните све суседне чворове у стеку

Даље, узимамо један од суседних чворова за обраду, тј. Врх стека који је 1. Означавамо га као посећен додавањем на посећену листу. Сада потражите суседне чворове 1. Како је 0 већ на посећеној листи, игноришемо је и посетимо 2 која је врх стека.

ДФС илустрација - 3. корак

Даље, чвор 2 означавамо као посећен. Његов суседни чвор 4 је додат у стек.

ДФС илустрација 4. корак

Даље, означавамо 4 који је врх стека као посећен. Чвор 4 има само чвор 2 као суседни који је већ посећен, па га зато игноришемо.

ДФС илустрација 5. корак

У овој фази у стеку је присутан само чвор 3. Његов суседни чвор 0 је већ посећен, па га зато игноришемо. Сада означавамо 3 као посећене.

ДФС илустрација 6. корак

Сад је стек празан, а посећена листа приказује редослед преласка дубине првог графикона.

Ако посматрамо дати граф и редослед преласка, примећујемо да за алгоритам ДФС заиста прелазимо граф у дубину и затим га поново враћамо да бисмо истражили нове чворове.

Примена дубинске претраге

Применимо технику ДФС преласка помоћу Ц ++.

#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited()); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list(V); } // function to add an edge to graph void addEdge(int v, int w){ adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited()) { // current node v is visited visited(v) = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList(v).begin(); i != adjList(v).end(); ++i) if(!visited(*i)) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool(V); for (int i = 0; i < V; i++) visited(i) = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited(i) == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'<

Излаз:

Прелазак дубине за дати графикон:

0 1 2 4 3

Поново смо користили графикон у програму који смо користили у илустративне сврхе. Видимо да се алгоритам ДФС (одвојен у две функције) позива рекурзивно на сваком врху у графикону како би се осигурало да су сви врхови посећени.

Рунтиме Аналисис

Временска сложеност ДФС-а је иста као и БФС тј. О (| В | + | Е |) где је В број врхова, а Е број ивица у датом графикону.

Слично БФС-у, у зависности од тога да ли је граф слабо насељен или густо насељен, доминантни фактор ће бити врхови односно ивице у израчунавању временске сложености.

Итеративни ДФС

Имплементација приказана горе за ДФС технику је рекурзивне природе и користи стек позива функција. Имамо још једну варијацију за примену ДФС-а, тј. Итеративно претраживање по дубини ”. У овоме користимо експлицитни стек да бисмо задржали посећене врхове.

У наставку смо приказали примену итеративног ДФС-а. Имајте на уму да је примена иста као БФС, осим фактора да користимо структуру стек података уместо реда.

#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list(V); } void addEdge(int v, int w) // add an edge to graph { adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited(s)) { cout << s << ' '; visited(s) = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList(s).begin(); i != adjList(s).end(); ++i) if (!visited(*i)) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited(i)) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal: '; gidfs.DFS(); return 0; }

Излаз:

Излаз из поновљеног дубинског преласка:

0 3 2 4 1

Користимо исти графикон који смо користили у нашој рекурзивној имплементацији. Разлика у излазу је зато што користимо стек у итеративној имплементацији. Како стекови прате ЛИФО редослед, добијамо другачији редослед ДФС-а. Да бисмо добили исти низ, можда бисмо желели да уметнемо врхове обрнутим редоследом.

БФС вс ДФС

До сада смо разговарали о обилазним техникама за графиконе, тј. БФС и ДФС.

Погледајмо сада разлике између њих двоје.

БФСДФС
Штандови за „претраживање по ширини“Стоји за „Дубинско прво претраживање“
Чворови се истражују по ширини, ниво по ниво.Чворови се истражују дубински док не постоје само чворови листова, а затим се враћају назад да би се истражили други непосећени чворови.
БФС се изводи уз помоћ структуре података о реду.ДФС се изводи помоћу структуре података стека.
Спорије у перформансама.Бржи од БФС-а.
Корисно у проналажењу најкраће путање између два чвора.Користи се углавном за откривање циклуса на графиконима.

Примене ДФС-а

  • Откривање циклуса на графикону: Ако пронађемо задњу ивицу док изводимо ДФС на графикону, можемо закључити да графикон има циклус. Стога се ДФС користи за откривање циклуса у графикону.
  • Проналажење путање: С обзиром на два темена к и и, пут између к и и можемо пронаћи помоћу ДФС-а. Почињемо са теменом к, а затим гурамо све темене на путу до стека док не наиђемо на и. Садржај стека даје пут између к и и.
  • Најмањи распон дрвећа и најкраћи пут: ДФС обилазак неутегнутог графа даје нам минимално обухватно стабло и најкраћи пут између чворова.
  • Тополошко сортирање: Тополошко сортирање користимо када треба да распоредимо послове из задатих зависности међу пословима. У пољу рачунарства користимо га углавном за решавање зависности симбола у повезивачима, сериализацију података, заказивање упутстава итд. ДФС се широко користи у тополошком сортирању.

Закључак

У последњих неколико водича истражили смо више о две технике преласка за графиконе, тј. БФС и ДФС. Видели смо разлике као и примене обе технике. БФС и ДФС у основи постижу исти исход посете свим чворовима графикона, али се разликују по редоследу излаза и начину на који се то ради.

Такође смо видели примену обе технике. Док БФС користи ред, ДФС користи стекове за примену технике. Овим закључујемо туторијал о техникама преласка за графиконе. Такође можемо користити БФС и ДФС на дрвећу.

софтвер за преузимање видео записа са веб локација

У нашем предстојећем упутству научићемо више о обухватању дрвећа и неколико алгоритама за проналажење најкраће путање између чворова графикона.

=> Погледајте овде како бисте истражили целу листу водича за Ц ++.

Препоручено читање

^