Обхождане на граф в ширина. BFS.

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

15 юли 2018, 17:33

След като се научихте да представяте граф е време да се научите да го обхождате. За целта в два урока ще ви изложа двата алгоритъма за обхождане. Тук ще поговорим за обхождане в ширина. За целта ще използваме алгоритъмът BFS (Breadth First Search). Какво представлява този алгоритъм. След като сте представили графа започвате от даден връх обхождането, като слагате всичките му съседи в една опашка. После вадите първият връх от опашката и вкарвате съседите му. Тази операция повтаряте, докъто опашката не се изпразни. Така обхождате графа. Ето видео, в което съм онагледил алгоритъма. Трябва да си влязъл в системата, за да можеш да виждаш линковете. Така стига толкова обяснения да преминем към кода.

Това е код, който използва матрица на съседство.

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

#include <iostream>
#include <queue>

using namespace std;

int n,m;
int mat[501][501];
bool used[501];
queue<int>q;

void bfs(int start)
{
	int node;
	q.push(start);
	while(!q.empty())
	{
		node=q.front();
		q.pop();
		for(int i=1;i<=n;i++)
		{
			if(mat[node][i]!=0)
			{
				if(!used[i])
				{
					q.push(i);
				}
			}
		}
		used[node]=1;
	}
}
int main()
{
	
	cin>>n>>m;
	int a,b;
	for(int i=0;i<m;i++)
	{
	cin>>a>>b;
	mat[a][b]=1;
	mat[b][a]=1;
	} 
	bfs(1);
}
Това е код, който използва списък на съседство.

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

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n,m;
bool used[501];
queue<int>q;
vector<int>gr[501];
void bfs(int start)
{
	int node;
	q.push(start);
	while(!q.empty())
	{
		node=q.front();
		q.pop();
		for(int i=0;i<gr[node].size();i++)
		{
			if(!used[gr[node][i]])
			{
				q.push(gr[node][i]);
			}
		}
		used[node]=1;
	}
}
int main()
{
	cin>>n>>m;
	int a,b;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		gr[a].push_back(b);
		gr[b].push_back(a);
	}
	bfs(1);
}
Надявам се урокът да ви е бил полезен. Ако имате въпроси пишете ми на ЛС.

Отговори

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

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

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