Popište algoritmus DFS, diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.

Algortimus DFS je algoritmus sloužící k prohledávání grafů.

1. Algortimus začne na libovolném vrcholu grafu, tento vrchol prohledá a připraví si všechny jeho sousední vrcholy na prohledání ve datové struktuře typu FIFO (First-In, First-Out), tedy prvně prohledá naposledy přidané vrcholy
2. Po připravení vrcholu na prohledání označí tento vrchol jako otevřený

→ pokud na tento otevřený vrchol znovu narazí nepřidává ho do fronty

1. Přejde na libovolný z nově přidaných vrcholů a zde provadí krok 1. a 2.

DFS(int start, vector<int> vertices, map<int,vector<int>> edges)
{
	// queue of vertices we have yet to traverse
	stack<int> queue;

	//edges we already discovered
	set<int> seen;

//we will push starting vortex to the queue
	queue.push(start);
	seen.insert(start);

	while(!q.empty)
	{
		int current_edge = q.front();
		q.pop();

		seen.insert(current_edge)
		
		for(auto& neighbor : map[current_edge])
		{
			if(!seen.count(neigbort))
			{
				queue.push(neighbor);
				seen.insert(neighbor);
			}
		}
	}
}

Ukázka DFS