c++ - 在有向图中通过 bfs 搜索显示最短路径

Question

我一直在为大学做一个项目，遇到了一个相当大的问题。我应该创建一个函数，通过有向图从 A 点到 B 点获取最短路径，并按顺序显示路径。

例如。如果该节点包含州名称并且我们想要找到加利福尼亚和犹他州之间的最短路径，则输出将显示加利福尼亚 -> 内华达 -> 犹他州

目前，我的遍历显示的是使用 bfs 搜索的所有节点，而不是我们从 A 点到 B 点所采用的节点列表。

下面是我对作业的实现。我唯一真正的问题是如何跟踪我实际遍历的节点而不是所有搜索到的节点。

bool DirectedGraph::GetShortestPath(
const string& startNode, const string& endNode, 
bool nodeDataInsteadOfName, vector<string>& traversalList) const
{

//Nodes are the same
if (startNode.compare(endNode) == 0)
    return false;

//Stores the location of our nodes in the node list
vector<int> path;

//Queue to hold the index of the node traversed 
queue<int> q;

//Create our boolean table to handle visited nodes
bool *visited = new bool[m_nodes.size()];
//initialize bool table
memset(visited, false, sizeof(bool) * m_nodes.size());

//Label the start node as visited
visited[GetNodeIndex(startNode)] = true;
//Push the node onto our queue
q.push(GetNodeIndex(startNode));



while (!q.empty())
{
    //Store the nodes index
    int index = q.front();
    path.push_back(q.front());
    q.pop();

    int i = 0;
    for (i = 0; i < m_nodes[index]->Out.size(); i++)
    {
        //If this node matches what we are looking for break/return values
        if (m_nodes[index]->Out[i]->targetI == GetNodeIndex(endNode))
        {
            path.push_back(m_nodes[index]->Out[i]->targetI);
            if (nodeDataInsteadOfName)
            {
                path.push_back(m_nodes[index]->Out[i]->targetI);
                for (int x = 0; x < path.size(); x++)
                {
                    traversalList.push_back(m_nodes[path[x]]->Data);
                }
            }
            else
            {
                for (int x = 0; x < path.size(); x++)
                {
                    traversalList.push_back( m_nodes[path[x]]->Name);
                }
            }

            return true;
        }


        //Continue through the data
        if (!visited[m_nodes[index]->Out[i]->targetI])
        {
            visited[m_nodes[index]->Out[i]->targetI] = true;
            q.push(m_nodes[index]->Out[i]->targetI);
        }
    }

}
// You must implement this function
return false;
}

//图私有(private)成员的定义

struct Edge
{
    int srcI; // Index of source node
    int targetI; // Index of target node
    Edge(int sourceNodeIndex, int targetNodeIndex)
    {
        srcI = sourceNodeIndex;
        targetI = targetNodeIndex;
    }
};

struct Node
{
    string Name;
    string Data;
    Node(const string& nodeName, const string& nodeData)
    {
        Name = nodeName;
        Data = nodeData;
    }

    // List of incoming edges to this node
    vector<Edge*> In;

    // List of edges going out from this node
    vector<Edge*> Out;
};

// We need a list of nodes and edges
vector<Node*> m_nodes;
vector<Edge*> m_edges;

// Used for efficiency purposes so that quick node lookups can be 
// done based on node names. Maps a node name string to the index 
// of the node within the nodes list (m_nodes).
unordered_map<string, int> m_nodeMap;

Answer 1

第一个问题是 for 循环中的 if。您的 path 变量只能包含两项:起始节点和结束节点。我建议您不要使用 for 循环跟踪路径。相反，为每个节点分配一个距离。

struct Node
{
    string Name;
    string Data;
    int Distance;
    Node(const string& nodeName, const string& nodeData)
    {
        Name = nodeName;
        Data = nodeData;
        Distance = INT_MAX;
    }

    // List of incoming edges to this node
    vector<Edge*> In;

    // List of edges going out from this node
    vector<Edge*> Out;
};

并在循环之前将起始节点的距离设置为零。

m_nodes[GetNodeIndex(startNode)]->Distance = 0;

在每次迭代中，从队列中选择一个节点(您称它为索引)，遍历其邻接列表(传出弧)并测试是否访问了相邻节点。如果访问了该节点，则跳过它。如果该节点没有被访问过，通过设置它的距离来访问它

m_nodes[index]->Distance + 1

更新每个节点的距离后，检查它是否是最终节点，如果是则跳出循环。

此时您已正确更新距离。从结束节点向后工作，每次从邻接列表中选择节点(距离 = 当前节点的距离 - 1)。您可以使用 m_edges vector 来执行此操作，每次您实际知道 targetI 时，您都可以使用距离值检查其对应的 scrI如上所述。