为什么我的广度优先先打印了 8
CMap:
void CMap::BreadthFirstTraverse(int nodeIndex)
{
cout<<m_pNodeArray[nodeIndex].m_cData << " ";
m_pNodeArray[nodeIndex].m_bIsVisited = true;
vector<int> curVec;
curVec.push_back(nodeIndex);
BreadthFirstTraverseImpl(curVec);
}
void CMap::BreadthFirstTraverseImpl(vector<int> preVec)
{
int value = 0;
vector<int> curVec;
for (int j = 0; j < (int)preVec.size(); j++)
{
for (int i = 0; i < m_iCapacity; i++)
{
GetValueFromMatrix(preVec[j], i, value);
if (value != 0)
{
if (m_pNodeArray[i].m_bIsVisited)
{
continue;
}
else
{
cout << m_pNodeArray[i].m_cData <<" ";
m_pNodeArray[i].m_bIsVisited = true;
curVec.push_back(i);
}
}
}
if (curVec.size() == 0)
{
return;
}
else
{
BreadthFirstTraverseImpl(curVec);
}
}
}
bool CMap::GetValueFromMatrix(int row, int col, int &val)
{
if (row < 0 || row >= m_iCapacity)
{
return false;
}
if (col < 0 || col >= m_iCapacity)
{
return false;
}
val = m_pMatrix[row*m_iCapacity+col];
return true;
}
Main:
#include <iostream>
#include <stdlib.h>
#include "CMap.h"
using namespace std;
/*
1
2 3
4 5 6 7
8
1 2 3 4 5 6 7 8
1 1 1
2 1 1 1
3 1 1 1
4 1 1
5 1 1
6 1 1
7 1 1
8 1 1
*/
int main()
{
CMap *map = new CMap(8);
MapNode node1;
node1.m_cData = '1';
MapNode node2;
node2.m_cData = '2';
MapNode node3;
node3.m_cData = '3';
MapNode node4;
node4.m_cData = '4';
MapNode node5;
node5.m_cData = '5';
MapNode node6;
node6.m_cData = '6';
MapNode node7;
node7.m_cData = '7';
MapNode node8;
node8.m_cData = '8';
map->AddNode(&node1);
map->AddNode(&node2);
map->AddNode(&node3);
map->AddNode(&node4);
map->AddNode(&node5);
map->AddNode(&node6);
map->AddNode(&node7);
map->AddNode(&node8);
map->SetValueToMatrixForUndirectedGraph(0, 1);
map->SetValueToMatrixForUndirectedGraph(0, 2);
map->SetValueToMatrixForUndirectedGraph(1, 3);
map->SetValueToMatrixForUndirectedGraph(1, 4);
map->SetValueToMatrixForUndirectedGraph(2, 5);
map->SetValueToMatrixForUndirectedGraph(2, 6);
map->SetValueToMatrixForUndirectedGraph(3, 7);
map->SetValueToMatrixForUndirectedGraph(4, 7);
map->SetValueToMatrixForUndirectedGraph(5, 6);
map->PrintMatrix();
cout << endl;
map->BreadthFirstTraverse(0);
delete map;
map = NULL;
system("pause");
return 0;
}
