如何遍历节点向量

Question

我正在实现 Dijkstra 的最短路径算法。我做了一个节点class如下：

node::node(int to,int weight)
{
    this->to = to;
    this->weight = weight;
}

我制作了一个图表 class 作为 :

class Graph
{
    int V,E;
    vector<node> *adj;
    public :
        Graph(int V,int E);
        void addEdge(int v,int w,int weight);
        void dijkstra(int src,int V);
};

Graph::Graph(int V,int E)
{
    this->V = V;
    this->E = E;
}

void Graph::addEdge(int v,int w,int weight)
{
    node x(w,weight);
    adj[v].push_back(x);
    node y(v,weight);
    adj[w].push_back(y);
}

现在在 Dijkstra 的算法函数中，我想遍历邻接表（这里是 vector）：

void Graph::dijkstra(int src,int V)
{
    struct heap_node node[V];
    for(int i=0;i<V;i++)
    {
        node[i].vertex_value = INT_MAX;
        node[i].vertex_no = i;
    }
    bool visited[V];
    memset(visited,false,sizeof(visited));
    node[src].vertex_value = 0;
    make_heap(node,node+V,compare);
    //As we have set vertex_value(distance from source) of the source node to 0,We are left with V-1 vertices. So, we will run a for loop. 
    for(int i=0;i<V-1;i++)  
    {
        pop_heap(node,node-i-1,compare);
        //This will extract the minimum from the heap and set it to the last position. 
        int cur = V-i-1;
        int u = node[cur].vertex_no;
        visited[u] = true;
        vector<node>::iterator it;
        for(it = adj[u].begin() ; it != adj[u].end() ; it++)
        {
            node v = *it;
        }
    }
}

但它给我以下错误：

dijkstra1.cpp: 在成员函数‘void Graph::dijkstra(int, int)’中： dijkstra1.cpp:79:10: 错误：‘节点’不能出现在常量表达式中 vector::iterator它；

dijkstra1.cpp:79:14: 错误：模板参数 1 无效 vector::iterator它；

dijkstra1.cpp:79:14: 错误：模板参数 2 无效

dijkstra1.cpp:79:26: 错误：'it' 之前的预期初始值设定项 vector::iterator它；

dijkstra1.cpp:80:7: 错误：“它”未在此范围内声明 for(it = adj[u].begin() ; it != adj[u].end() ; it++)

我该如何摆脱它。

Answer 1

看起来您有两种类型：heap_node 和一个节点 class。我不确定哪种类型是 adj，但无论哪种方式，您都不能使矢量类型成为一个实例。它必须是一种类型。所以要么做到

typedef struct heap_node HEAP_NODE_STRUCT
vector<HEAP_NODE_STRUCT>

或c 吊死 heap_node struct node 至

heap_node struct the_heap_node;

所以你没有隐藏原来的节点class。

如何遍历节点向量

How to iterate through a vector of nodes

c++

graph

vector

dijkstra

shortest-path