Обхождане на граф в дълбочина. DFS.

Visual Basic, C#, C++, Python и др.
Потребителски аватар
[BG][SSA]Troll
Модератор
Мнения: 26
Регистриран: вт юли 10, 2018 9:35 pm
Баланс: Locked
Местоположение: Велико Търново

пон авг 13, 2018 3:24 pm

Това е другият алгоритъм за обхождане на графи. Depth First Search или DFS обхожда графа в дълбочина, като за разлика от BFS е рекурсивен алгоритъм и е значително по-кратък. Ето видео в което съм обяснил как бачка DFS-то и пиша кода: Трябва да си влязъл в системата, за да можеш да виждаш линковете.
Ето го и кода:

Код: Трябва да си влязъл в системата, за да можеш да виждаш линковете

#include <bits/stdc++.h>

using namespace std;

vector<int>gr[500];
int n,m;
bool used[500];
void init()
{
	scanf("%d %d",&n,&m);
	int a,b;
	for(int i=0;i<m;i++)
	{
		scanf("%d %d",&a,&b);
		gr[a].push_back(b);
		gr[b].push_back(a);
	}
}
void dfs(int start)
{
	cout<<start;
	used[start]=1;
	for(int i=0;i<gr[start].size();i++)[size=150][/size]
	{
		if(!used[gr[start][i]])
		{
			dfs(gr[start][i]);
		}
	}
}
int main()
{
	init();
	dfs(1);
}
Надявам се урокът да ви е бил полезен ако имате въпроси пишете ми на ЛС.

Отговори

Върни се в “Системно Програмиране”

  • Информация
  • Кой е на линия

    Потребители, разглеждащи този форум: Няма регистрирани потребители и 0 госта