用vector或set建立邻接表
在一般情况下使用链表建立的邻接表就行,但若对节点下的子树的顺序有要求的话(树和图的搜索),链表显然不方便,他的顺序在输入时就固定了,所以这时就可以使用vector
或set
来构建邻接表了
这样也就方便排序了
思路与链表法相同,只是将链表换成vector
或set
0 | 1,2 |
---|---|
1 | 3,4 |
2 | NULL |
3 | NULL |
4 | 5 |
5 | NULL |
无权图
vector<int> p[N];
void add(int a, int b) {
p[a].push_back(b);
}
有权图
链表法是添加一个w[N]
数组存权重,这里可以直接用结构体vector
struct node {
int v, w; // 边的终点编号 权重
};
vector<node> p[N];
void add(int a, int b, int w) {
p[a].push_back((node){b, w});
}
正如上面洛谷的那道题,他需要有序,用vector
存完后排个序就行,但也可以使用set
代替vector
,省去排序操作,但一般没必要