Raqamli texnologiyalar vazirligi

Iterativ DFS

DFS texnikasi uchun yuqorida ko'rsatilgan dastur rekursiv xarakterga ega va u funktsiya chaqiruvi to'plamidan foydalanadi. Biz ya'ni DFS amalga oshirish uchun yana bir o'zgarish bor." Iterative depth-first search". Bunda biz tashrif buyurilgan uchlarni ushlab turish uchun aniq to'plamdan foydalanamiz.

#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:\n";
gidfs.DFS();
return 0;
}

Xulosa

Mavzuni o’rganish davomida Depth-first search (DFS) ya’ni Tubiga qidiruv algoritmi ko’rib chiqildi.Uning afaziliklari kamchiliklariga kelsak:
Depth-first search