#include "Project$2\_$Travelling Salesperson Problem.h$"$

#include

#include

#include

#include

#include

using namespace std;

$//$this Define the graph with connected edges

vector$>$ graph $=\{$

$\{\},//$ City $1$

$\{2\},//$ City $2$

$\{3\},//$ City $3$

$\{4,5\},//$ City $4$

$\{6,7\},//$ City $5$

$\{8\},//$ City $6$

$\{9,10\},//$ City $7$

$\{9,10,11\},//$ City $8$

$\{\},//$ City $9$

$\{\},//$ City $10$

$\{\}//$ City $11$

$\}$;

$//$ This Define city coordinates

struct Vertex $\{$

int id;

double city$1$;

double city$2$;

$\}$;

$//$ Euclidean distance between two cities

double calculateDistance$($Vertex city$1,$ Vertex city$2)\{$

return sqrt$($pow$($city$1.$firstcity$2.$first, $2)+$pow$($city$1.$second $-$ city$2.$second, $2))$;

$\}$

int main$()\{$

$//$std::vector$>$ cityCoordinates $=$

vectorveritces$=\{$

$\{1,5\mathrm{.}681818,63\mathrm{.}860370\},$

$\{2,11\mathrm{.}850649,83\mathrm{.}983573\},$

$\{3,13\mathrm{.}798701,65\mathrm{.}092402\},$

$\{4,16\mathrm{.}883117,40\mathrm{.}451745\},$

$\{5,23\mathrm{.}782468,56\mathrm{.}262834\},$

$\{6,25\mathrm{.}000000,31\mathrm{.}211499\},$

$\{7,29\mathrm{.}951299,41\mathrm{.}683778\},$

$\{8,31\mathrm{.}331169,25\mathrm{.}256674\},$

$\{9,37\mathrm{.}175325,37\mathrm{.}577002\},$

$\{10,39\mathrm{.}935065,19\mathrm{.}096509\},$

$\{11,46\mathrm{.}834416,29\mathrm{.}979466\}$

$\}$;

$//$Breadth First Search algorithm

void BFS$($int start, int goal$)\{$

queue q;

vector visited$($graph$.$size$(),$ false$)$;

q$.$push$($start$)$;

visited$[$start$]=$ true;

while$(!$q$.$empty$())\{$

int current $=$ q$.$front$()$;

q$.$pop$()$;

if $($current $==$ goal$)\{$

cout $<<$ "Goal city" $<<$ goal $<<$ "found using BFS$!"<<$ endl;

return;

$\}$

for $($int neighbor : graph$[$current$])\{$

if $(!$visited$[$neighbor$])\{$

q$.$push$($neighbor$)$;

visited$[$neighbor$]=$ true;

$\}$

$\}$

$\}$

cout $<<$ "Goal city" $<<$ goal $<<$ "not found using BFS$"<<$ endl;

$\}$

$//$Depth First Search algorithm

void DFS$($int start, int goal$)\{$

stack s;

vector visited$($graph$.$size$(),$ false$)$;

s$.$push$($start$)$;

visited$[$start$]=$ true;

while $(!$s$.$empty$())\{$

int current $=$ s$.$top$()$;

s$.$pop$()$;

if $($current $==$ goal$)\{$

cout $<<$"Goal city" $<$