Module: Busca en profundidad. SFD


Problem

1/12

DFS: Principio (C++)

Theory Click to read/hide

DFS DFS
La búsqueda en profundidad (DFS) es uno de los principales algoritmos de los gráficos. El algoritmo se ejecuta en O(N + M).
 
Algoritmo
Para empezar, comenzamos desde la parte superior, consideramos los elementos secundarios de esta parte superior y, si nunca los hemos ingresado, comenzamos DFS desde ellos.


Problem

Escriba un procedimiento void dfs (int v) que atraviese la profundidad de un gráfico no dirigido desde el vértice inicial S y genere todos los vértices en orden transversal, comenzando en el vértice S separados por un espacio en una línea.

La primera línea contiene tres números N  - el número de vértices en el gráfico, M - el número de aristas, S - el inicio vértice. En las siguientes líneas M, 2 variables Ui y Vi se suministran , descripción de los bordes del gráfico. Todos los números en la entrada no exceden 1000.

Muestra todos los vértices en orden de recorrido por DFS.

En el programa anterior, g[i][j] significa que hay un borde entre los vértices i y j, y en el array used marcamos si hemos visitado este pico. 

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!