Module: Recherche en profondeur. DFS


Problem

1/12

DFS : début (C++)

Theory Click to read/hide

DFS DFS
La recherche en profondeur d'abord (DFS) est l'un des principaux algorithmes sur les graphes. L'algorithme s'exécute en O(N + M).
 
Algorithme
Pour commencer, nous partons du sommet, considérons les enfants de ce sommet, et si nous ne les avons jamais saisis, nous démarrons DFS à partir d'eux.


Problem

Écrivez une procédure void dfs (int v) qui traverse la profondeur d'un graphe non orienté à partir du sommet de départ S et génère tous les sommets dans l'ordre de parcours, en commençant par le sommet S séparés par un espace sur une ligne.

La première ligne contient trois nombres N  - le nombre de sommets dans le graphe, M - le nombre d'arêtes, S - le début sommet. Dans les lignes M suivantes, 2 variables Ui et Vi sont fournis , description des arêtes du graphe. Tous les nombres dans l'entrée ne dépassent pas 1000.

Afficher tous les sommets dans l'ordre de traversée par DFS.

Dans le programme ci-dessus, g[i][j] signifie qu'il y a une arête entre les sommets i et j, et dans le tableau utilisé nous marquons si nous avons visité ce pic. 

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <iostream>
#include <vector>

using namespace std;

vector < vector < int > > g;
vector < bool > used;

void dfs(int v) 
{            
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m, s, u, v;

	cin >> n >> m >> s;

	g.resize(n);
	used.resize(n);

	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		g[u - 1].push_back(v - 1);
		g[v - 1].push_back(u - 1);
	}

	dfs(s - 1);
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!