BFS implementation is provided. You need to implement DFS$.$

#ifndef $\_$GRAPH$\_$ALGORITHMS$\_$H$\_$

#define $\_$GRAPH$\_$ALGORITHMS$\_$H$\_$

#include

#include

$//$#include $//$ Uncomment this if you have boost installed

$//$ This is an example list of the basic algorithms we will work with in class.

$//$

$//$ In general this is what the following template parameters are:

$//$

$//-$ Graph: type of graph, literally your adjacency list graph.

$//$

$//-$ ParentMap: associative container between vertex$\_$descriptors and parent

$//$ vertex$\_$descriptors. This is a representation of the free

$//$ trees$/$forests created by these search methods.

$//$

$//-$ DistanceMap: associative container between vertex$\_$descriptors and

$//$ EdgeProperties. This represents the summation of the path

$//$ weights to the vertex itself.

$//$

$//$ Assume EdgeProperties can be added and compared with less than$/$less than or

$//$ equal.

$//$

$///$@brief Implement breadth$-$first search.

template

void breadth$\_$first$\_$search$($const Graph& g$,$ ParentMap& p$)\{$

typedef typename Graph::vertex$\_$descriptor vertex$\_$descriptor;

typedef typename Graph::edge$\_$descriptor edge$\_$descriptor;

typedef typename Graph::const$\_$vertex$\_$iterator vertex$\_$iterator;

typedef typename Graph::const$\_$edge$\_$iterator edge$\_$iterator;

typedef typename Graph::const$\_$adj$\_$edge$\_$iterator adj$\_$edge$\_$iterator;

$//$setup

std::queue q;

$//$std::unordered$\_$set$>$ edges$\_$unexplored;

std::set edges$\_$unexplored;

std::unordered$\_$set vertices$\_$unexplored;

$//$initialize

p$.$clear$()$;

for$($vertex$\_$iterator vi $=$ g$.$vertices$\_$cbegin$()$; vi $!=$ g$.$vertices$\_$cend$()$; $++$vi$)\{$

vertex$\_$descriptor vd $=(*$vi$)->$descriptor$()$;

vertices$\_$unexplored.emplace$($vd$)$;

p$[$vd$]=-1$;

$\}$

for$($edge$\_$iterator ei $=$ g$.$edges$\_$cbegin$()$; ei $!=$ g$.$edges$\_$cend$()$; $++$ei$)$

edges$\_$unexplored.emplace$((*$ei$)->$descriptor$())$;

$//$for each CC

for$($vertex$\_$iterator vi $=$ g$.$vertices$\_$cbegin$()$; vi $!=$ g$.$vertices$\_$cend$()$; $++$vi$)\{$

vertex$\_$descriptor vd $=(*$vi$)->$descriptor$()$;

if$($vertices$\_$unexplored.count$($vd$))\{$

q$.$push$($vd$)$;

vertices$\_$unexplored.erase$($vd$)$;

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

vertex$\_$descriptor vd $=$ q$.$front$()$;

q$.$pop$()$;

auto& v $=*$g$.$find$\_$vertex$($vd$)$;

for$($adj$\_$edge$\_$iterator aei $=$ v$->$begin$()$; aei $!=$ v$->$end$()$; $++$aei$)\{$

auto el $=$ edges$\_$unexplored.find$((*$aei$)->$descriptor$())$;

if$($el $!=$ edges$\_$unexplored.end$())\{$

vertex$\_$descriptor t $=(*$aei$)->$target$()$;

if$($vertices$\_$unexplored.count$($t$))\{$

$//$discovery edge

edges$\_$unexplored.erase$($el$)$;

p$[$t$]=$ v$->$descriptor$()$;

q$.$push$($t$)$;

vertices$\_$unexplored.erase$($t$)$;

$\}$

$//$else cross edge

$\}$

$\}$

$\}$

$\}$

$\}$

$\}$

$///$@todo Implement depth$-$first search.

template

void depth$\_$first$\_$search$($const Graph& g$,$ ParentMap& p$)\{$

$\}$

#endif