Modify the adjacency matrix implementation to use an extra stack where you push a new node id onto the stack when adding a node to minimize the initialization effort. Do that by scanning the stack to see if a node id has already been plugged into the adj. matrix

#include

#include

#include

#include "Graph.hpp$"$

using namespace std;

template

class AdjMatrixGraph: public Graph $\{$

private:

class NodeEntry $\{$

public:

N node;

int index;

$\}$;

const static int maxSize $=10$;

bool adjMatrix$[$maxSize$][$maxSize$]$;

NodeEntry $*$nodes$[$maxSize$]$;

int numNodes $=0$;

int findNodeInMatrix$($N x$)\{$

for $($int j$=0$; j $<$ numNodes; $++$j$)$

$\{$

if $($x $==$ nodes$[$j$]->$node$)$

$\{$

return j;

$\}$

$\}$

return $-1$;

$\}$

public:

$//$ Default constuctor, create empty

AdjMatrixGraph$()$

$\{$

for$($int i $=0$; i $<$ maxSize; i$++)$

for $($int j$=0$; j $<$ maxSize; j$++)$

$\{$

adjMatrix$[$i$][$j$]=$ false;

$\}$

$\}$

$//$ Add the nodes in the list to graph

AdjMatrixGraph$($vector newNodes, vector$>$ newEdges$)$

$\{$

adjMatrix $=$ new NodeEntry$[$maxSize$][$maxSize$]$;

for $($typename vector::const$\_$iterator it $=$ newNodes.begin$()$;

it $<$ newNodes.end$()$;

$++$it$)$

$\{$

NodeEntry ne $=$ new NodeEntry$()$;

ne$.$node $=*$it;

ne$.$index $=$ numNodes;

nodes$[$numNodes$]=$ ne;

$\}$

for $($typename vector$>$::const$\_$iterator it $=$ newEdges.begin$()$;

it $<$ newEdges.end$()$;

$++$it$)$

$\{$

pair edge $=*$it;

int sourceIndex $=$ findNodeInMatrix$($edge$.$first$)$;

int destIndex $=$ findNodeInMatrix$($edge$.$second$)$;

if $($sourceIndex $!=-1)$

$\{$

if $($destIndex $!=-1)$

$\{$

adjMatrix$[$sourceIndex$][$destIndex$]=$ true;

$\}$

$\}$

$\}$

$\}$

$//$ Clean up behind ourselves

~AdjMatrixGraph$()\{\}$;

virtual bool adjacent$($N x$,$ N y$)$

$\{$

bool result $=$ false;

int xIndex $=$ findNodeInMatrix$($x$)$;

int yIndex $=$ findNodeInMatrix$($y$)$;

if $(($xIndex $!=-1)$ && $($yIndex $!=-1))$

$\{$

bool xy $=$ adjMatrix$[$xIndex$][$yIndex$]$;

bool yx $=$ adjMatrix$[$yIndex$][$xIndex$]$;

result $=$ xy && yx;

$\}$

return$($result$)$;

$\}$

virtual vector neighbors$($N x$)$

$\{$

vector $*$v $=$ new vector$()$;

int xIndex $=$ findNodeInMatrix$($x$)$;

if $($xIndex $!=-1)$

$\{$

for $($int i$=0$; i $<$ numNodes; $++$i$)\{$

if $($adjMatrix$[$xIndex$][$i$]==$ true$)\{$

v$->$push$\_$back$($nodes$[$i$]->$node$)$;

$\}$

$\}$

$\}$

return $*$v;

$\}$

virtual void addNode$($N node$)$

$\{$

NodeEntry $*$ne $=$ new NodeEntry$()$;

ne$->$node $=$ node;

ne$->$index $=$ numNodes;

nodes$[$numNodes$]=$ ne;

numNodes$++$;

$\}$

virtual void addEdge$($N x$,$ N y$)\{$

int xIndex $=$ findNodeInMatrix$($x$)$;

int yIndex $=$ findNodeInMatrix$($y$)$;

if $(($xIndex $!=-1)$ && $($yIndex $!=-1))$

$\{$

adjMatrix$[$xIndex$][$yIndex$]=$ true;

$\}$

$\}$

virtual void deleteEdge$($N x$,$ N y$)$

$\{$

int xIndex $=$ findNodeInMatrix$($x$)$;

int yIndex $=$ findNodeInMatrix$($y$)$;

adjMatrix$[$xIndex$][$yIndex$]=$ false;

$\}$

$//$ Traversals

void dfs$($N startNode, std::function visit$)\{$

map visited;

for $($int i $=0$; i $<$ numNodes; $++$i$)\{$

visited$[$nodes$[$i$]->$node$]=$ false;

$\}$

stack s;

s$.$push$($startNode$)$;

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

N currentNode $=$ s$.$top$()$;

s$.$pop$()$;

bool beenVisited $=$ visited$[$currentNode$]$;

if $(!$beenVisited$)\{$

visit$($currentNode$)$;

visited$[$currentNode$]=$ true;

$\}$

vector neighVec $=$ neighbors$($currentNode$)$;

for $($auto neighbor: neighVec $)\{$

if $(!$visited$[$neighbor$])\{$ s$.$push$($neighbor$)$; $\}$

$\}$

$\}$

$\}$

void bfs$($N startNode, std::function visit$)\{$

map visited;

for $($int i $=0$; i $<$ numNodes; $++$i$)\{$

visited$[$nodes$[$i$]->$node$]=$ false;

$\}$

queue q;

q$.$push$($startNode$)$;

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

N currentNode $=$ q$.$front$()$;

q$.$pop$()$;

bool beenVisited $=$ visited$[$currentNode$]$;

if $(!$beenVisited$)\{$

visit$($currentNode$)$;

visited$[$currentNode$]=$ true;

$\}$

vector neighVec $=$ neighbors$($currentNode$)$;

for $($auto neighbor: neighVec$)\{$

if $(!$visited$[$neighbor$])\{$ q$.$p