Grafove algoritmy

DFS prehladavanie grafu

Pozor: Ak nie je su vsetky uzly dosiahnutelne zo startovneho uzlu, tak nebudu vsetky prehladane!

		#include
		#include 

		using namespace std;

		// Pouzivame STL triedu Graph
		class Graph
		{
			int V;    // pocet uzlov
			list *adj;    // pointer na list susedov	
		public:
			Graph(int V)
			{
				this->V = V;
				adj = new list[V];
			}

			void addEdge(int v, int w)
			{
				adj[v].push_back(w); 
			}

			void DFSUtil(int v, bool visited[])
			{		
				visited[v] = true;
				cout << v << " ";
						
				list::iterator i;
				for (i = adj[v].begin(); i != adj[v].end(); ++i)
				if (!visited[*i])
					DFSUtil(*i, visited);
			}
				
			void DFS(int v)
			{		
				bool *visited = new bool[V];
				for (int i = 0; i < V; i++)
					visited[i] = false;
					
				DFSUtil(v, visited);
			}

		};

		int main()
		{
			
			Graph g(4);
			g.addEdge(0, 1);
			g.addEdge(0, 2);
			g.addEdge(1, 2);
			g.addEdge(2, 0);
			g.addEdge(2, 3);
			g.addEdge(3, 3);

			cout << "Depth First prehladavanie (zacinajuce uzlom 2) \n";
			g.DFS(2);

			return 0;
		}
		

BFS prehladavanie grafu

Pozor: Ak nie je su vsetky uzly dosiahnutelne zo startovneho uzlu, tak nebudu vsetky prehladane!

		#include
		#include 

		using namespace std;

		class Graph
		{
			int V;
			list *adj;
		public:
			Graph(int V)
			{
				this->V = V;
				adj = new list[V];
			}

			void addEdge(int v, int w)
			{
				adj[v].push_back(w); 
			}

			void BFS(int s)
			{
				
				bool *visited = new bool[V];
				for (int i = 0; i < V; i++)
					visited[i] = false;

				
				list queue;

				
				visited[s] = true;
				queue.push_back(s);

				
				list::iterator i;

				while (!queue.empty())
				{
					
					s = queue.front();
					cout << s << " ";
					queue.pop_front();
								
					for (i = adj[s].begin(); i != adj[s].end(); ++i)
					{
						if (!visited[*i])
						{
							visited[*i] = true;
							queue.push_back(*i);
						}
					}
				}
			}
		};


		int main()
		{

			Graph g(4);
			g.addEdge(0, 1);
			g.addEdge(0, 2);
			g.addEdge(1, 2);
			g.addEdge(2, 0);
			g.addEdge(2, 3);
			g.addEdge(3, 3);

			cout << "Breadth First prehladavanie zacinajuce uzlom 2  \n";
			g.BFS(2);

			return 0;
		}