C++ vector建立无向图并遍历

如果题目中，以[[1,2],[1,3],[1,4],[2,3],....]这种方式给出边。可用使用vector建图。

首先定义一个二维的vector

vector<vector<int>>g(n+1);//n为顶点数

然后遍历每一条边，假设遍历时两边的顶点分别为a,b。如果是无向边，则可添加顶点。

g[a].push_back(b);

g[b].push_back(a);

图的遍历：假设遍历a点的邻接点

for(auto ne:g[a]){

处理ne

}?

dfs遍历无向图（后序遍历）

dfs(i)：?

for (auto ne:g[i])：

? ? ?dfs(ne)

? 处理i

? ? ?这样写会重复遍历，为了防止遍历的时候走回去，需要多一个参数来记录上一个走的是什么。

dfs( i , pre ) :

? for( auto ne:g[i] ):

? ? ? ?if ne==pre|| ne ==i ：continue

? ? ? ?dfs(ne)

? 处理i? ? ? ?

?如果建立的边带有权值，那么就使用 vector<vector<pair<int,int>>>g， 来建图。

假设有边? {a,b,w}

g[a].push_back({b,w});

g[b].push_back({a,w});