поиск в глубину.cpp

#include <iostream>
#include <vector>
#include <stack> // íåîáõîäèì äëÿ èñïîëüçîâàíèÿ ñòåêà

using namespace std;

// Îïðåäåëåíèå ñòðóêòóðû âåðøèíû ãðàôà
struct Vertex {
    int id; // èäåíòèôèêàòîð âåðøèíû
    bool visited; // ôëàã, ïîêàçûâàþùèé, áûëà ëè âåðøèíà ïîñåùåíà
    vector<int> adjacentVertices; // ñïèñîê èäåíòèôèêàòîðîâ ñìåæíûõ âåðøèí
};

// Ôóíêöèÿ ðåêóðñèâíîãî îáõîäà ãðàôà â ãëóáèíó
void dfsVisit(vector<Vertex>& graph, int vertexId) {
    graph[vertexId].visited = true; // ïîìå÷àåì âåðøèíó, êàê ïîñåùåííóþ
    cout << "Ïîñåùåííàÿ âåðøèíà: " << vertexId << endl; // âûâîäèì èäåíòèôèêàòîð ïîñåùåííîé âåðøèíû â êîíñîëü

    for (int adjacentVertexId : graph[vertexId].adjacentVertices) { // ïåðåáèðàåì èäåíòèôèêàòîðû ñìåæíûõ âåðøèí òåêóùåé âåðøèíû
        if (!graph[adjacentVertexId].visited) { // åñëè ñìåæíàÿ âåðøèíà íå áûëà ïîñåùåíà
            dfsVisit(graph, adjacentVertexId); // ðåêóðñèâíî âûçûâàåì ôóíêöèþ îáõîäà ãðàôà äëÿ ñìåæíîé âåðøèíû
        }
    }
}

// Ôóíêöèÿ ïîèñêà â ãëóáèíó
void dfs(vector<Vertex>& graph, int startVertexId) {
    // Ñáðîñ ôëàãîâ ïîñåùåíèÿ âåðøèí
    for (Vertex& vertex : graph) { // ïåðåáèðàåì âñå âåðøèíû ãðàôà
        vertex.visited = false; // ñáðàñûâàåì ôëàã ïîñåùåíèÿ ó êàæäîé âåðøèíû
    }

    // Îáõîä ãðàôà â ãëóáèíó íà÷èíàÿ ñ çàäàííîé âåðøèíû
    dfsVisit(graph, startVertexId);
}

int main() {
    // Ñîçäàíèå ãðàôà
	setlocale(0,"Russian");
    int numVertices;
    cout << "Ââåäèòå êîëè÷åñòâî âåðøèí: ";
    cin >> numVertices;
    
    vector<Vertex> graph(numVertices);

    for(int i=0; i<numVertices; i++) {
        graph[i].id = i+1;
        graph[i].visited = false;
        int numAdjacent;
        cout << "Ââåäèòå êîëè÷åñòâî ñìåæíûõ âåðøèí äëÿ âåðøèíû " << i+1 << ": ";
        cin >> numAdjacent;
        
        for(int j=0; j<numAdjacent; j++) {
            int adjacentVertexId;
            cout << "Ââåäèòå èäåíòèôèêàòîð ñîñåäíåé âåðøèíû " << j+1 << ": ";
            cin >> adjacentVertexId;
            graph[i].adjacentVertices.push_back(adjacentVertexId);
        }
    }
     
    // Âûâîä ãðàôà
    cout << "Ãðàô:" << endl;
    for (Vertex vertex : graph) { // ïåðåáèðàåì âñå âåðøèíû ãðàôà
        cout << "Âåðøèíà " << vertex.id << " -> "; // âûâîäèì èäåíòèôèêàòîð òåêóùåé âåðøèíû â êîíñîëü
        for (int adjacentVertexId : vertex.adjacentVertices) { // ïåðåáèðàåì èäåíòèôèêàòîðû ñìåæíûõ âåðøèí òåêóùåé âåðøèíû
            cout << adjacentVertexId << " "; // âûâîäèì èäåíòèôèêàòîðû ñìåæíûõ âåðøèí òåêóùåé âåðøèíû â êîíñîëü
        }
        cout << endl; // ïåðåõîäèì íà ñëåäóþùóþ ñòðîêó
    }

    // Îáõîä ãðàôà â ãëóáèíó, íà÷èíàÿ ñ âåðøèíû 0
    cout << endl << "Ïîèñê â ãëóáèíó:" << endl;
    dfs(graph, 0); // çàïóñêàåì ïîèñê â ãëóáèíó, íà÷èíàÿ ñ âåðøèíû ñ èäåíòèôèêàòîðîì 0
    
    cin.get();
    return 0;
}