DFS, BFS, TSP
DFS, BFS, TSP
DFS, BFS, TSP
#include<iostream>
int main(){
int i,j,k,n,a[10][10],indeg[10],flag[10],count=0;
for(i=0;i<n;i++){
indeg[i]=0;
flag[i]=0;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
indeg[i]=indeg[i]+a[j][i];
while(count<n){
for(k=0;k<n;k++){
if((indeg[k]==0) && (flag[k]==0)){
cout<<k+1<<" ";
flag[k]=1;
}
for(i=0;i<n;i++){
if(a[i][k]==1)
indeg[k]--;
}
}
count++;
}
return 0;
}
DFS: -
#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];
main()
{
int m;
cout <<"enterno of vertices";
cin >> n;
cout <<"ente no of edges";
cin >> m;
cout <<"\nEDGES \n";
for(k=1;k<=m;k++)
{
cin >>i>>j;
cost[i][j]=1;
}
BFS: -
#include <iostream>
#include <list>
class Graph
{
int numVertices;
list *adjLists;
bool* visited;
public:
Graph(int vertices);
void addEdge(int src, int dest);
void BFS(int startVertex);
};
Graph::Graph(int vertices)
{
numVertices = vertices;
adjLists = new list[vertices];
}
list queue;
visited[startVertex] = true;
queue.push_back(startVertex);
list::iterator i;
while(!queue.empty())
{
int currVertex = queue.front();
cout << "Visited " << currVertex << " ";
queue.pop_front();
for(i = adjLists[currVertex].begin(); i !=
adjLists[currVertex].end(); ++i)
{
int adjVertex = *i;
if(!visited[adjVertex])
{
visited[adjVertex] = true;
queue.push_back(adjVertex);
}
}
}
}
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);
g.BFS(2);
return 0;
}