图实现的邻接矩阵中的数组向量错误

Question

我正在查看这段代码

using namespace std; 


// A utility function to add an edge in an 
// undirected graph. 
void addEdge(vector<int> adj[], int u, int v) 
{ 
    adj[u].push_back(v); 
    adj[v].push_back(u); 
} 

// A utility function to print the adjacency list 
// representation of graph 
void printGraph(vector<int> adj[], int V) 
{ 
    for (int v = 0; v < V; ++v) 
    { 
        cout << "\n Adjacency list of vertex "
             << v << "\n head "; 
        for (auto x : adj[v]) 
           cout << "-> " << x; 
        printf("\n"); 
    } 
} 

// Driver code 
int main() 
{ 
    int V = 5; 
    vector<int> adj[V]; 
    addEdge(adj, 0, 1); 
    addEdge(adj, 0, 4); 
    addEdge(adj, 1, 2); 
    addEdge(adj, 1, 3); 
    addEdge(adj, 1, 4); 
    addEdge(adj, 2, 3); 
    addEdge(adj, 3, 4); 
    printGraph(adj, V); 
    return 0; 
}

这段代码应该打印出邻接矩阵中节点之间的连接，它确实做到了。不过，我有几个doubts/questions.

在加边函数中，数组的向量是按值传递的。我觉得这是不正确的，应该通过引用传递。除非我在这里错过了一个把戏。

void addEdge(vector adj[], int u, int v)
所以我尝试将上面的转换为参考函数如下

void addEdge(vector (&adj)[], int u, int v)

但是这当然失败并出现错误：

candidate function not viable: no known conversion from 'vector [V]' to 'vector (&)[]' for 1st argument void addEdge(vector (&adj)[], int u, int v)

我知道有不同的方式来表示邻接矩阵，即数组、向量的向量，但如果有人能帮助我弄清楚这种语法，我将不胜感激。

谢谢

Answer 1

对于初学者来说，这个代码片段

int V = 5; 
vector<int> adj[V];

不是 C++ 标准的标准功能。 C++ 不支持变长数组。

你可以改写

const int V = 5; 
vector<int> adj[V];

按值传递数组时，指定数组的表达式将隐式转换为指向数组第一个元素的指针。所以实际上数组的每个元素都是使用指针间接传递的。该函数不会创建数组本身的副本。它创建指向数组第一个元素的传递指针的副本。

另一方面，声明为数组的函数参数会被编译器隐式调整为指向数组元素类型的指针。

例如这些函数声明

void f( int a[10] );
void f( int a[] );
void f( int *a );

声明同一个函数并且可以全部包含在一个程序中，尽管它们是多余的。

至于这个声明

void addEdge(vector (&adj)[], int u, int v);

那你没有指定数组的大小。所以第一个参数的类型不完整。

Answer 2

您对数组和指针之间的关系感到困惑。第一点，这个

void addEdge(vector<int> adj[], int u, int v)

完全等同于此

void addEdge(vector<int>* adj, int u, int v)

C语言中加入了[]语法，专门用来迷惑新手的（我想不出还有什么别的原因）。当您在函数参数中使用 [] 时，您实际上是在声明一个指针。

所以这是第二点，在 C 或 C++ 中不可能按值传递数组。所以你的担心是错误的。您实际上是将指针传递给数组的第一个元素，这是非常有效的。

我的建议是将函数参数中 [] 的所有实例更改为 *，这样您就不会感到困惑。

图实现的邻接矩阵中的数组向量错误

vector of arrays error in adjacency matrix for graph implementation

c++

arrays

declaration

function

vector