我得到了这个邻接矩阵,我必须从文本文件中读取它,并且应该返回读取它的广度优先和深度优先的结果。
我知道广度优先使用 FIFO 队列,而深度优先使用 LIFO 堆栈。当我有图表时,我可以手动进行这些搜索。我只是不确定如何在计算机上处理这个问题,并在 C++ 上使用矩阵。
我将不胜感激有关如何解决此问题的指导。 我有一些问题:
- 我是否将文本文件中的矩阵作为常规矩阵保存到我的程序中?
- 阅读文本文件以显示搜索结果后该怎么办?
最佳答案
ANS 1:是的,最好将文本文件中的输入读入常规矩阵。
void MyGraph::csv_import()
{
int temp, i=0;
string parsed;
fstream file("input.csv");
while (getline(file, parsed, ',')) {
temp = stoi(parsed);
arr[i/10][i%10] = temp; //10 x 10 Matrix
i++;
}
}
ANS 2:选择一个起始节点,调用BFS显示搜索结果。例如(在我的例子中)
void MyGraph::BFS(int v)
{
memset(visited, false, sizeof(visited);
QQ.push(v); //push the starting vertex into queue
visited[v] = true; //mark the starting vertex visited
while (!QQ.empty()) //until queue is not empty
{
v = QQ.front(); //assign v the vertex on front of queue
cout << v << " "; //print the vertex to be popped
QQ.pop(); //pop the vertex on front
for (int c = 0; c< V; c++) //V is the number of nodes
{
//M[i][j] == 1, when i,j are connected
if (M[v][c] == 1 && visited[c] == false)
{ //if vertex has edge and is unvisited
QQ.push(c); //push to the queue
visited[c] = true; //mark it visited
Path[c] = p; //assign the path length
}
}
}
}
关于c++ - 在邻接矩阵上应用广度和深度优先搜索?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40683271/