图的实现: 邻接表和领接矩阵
邻接表的优势: 占用空间少, 避免了邻接矩阵里面的空的位置
邻接矩阵的优势: 查找 2 个节点之间的连通性更高效
// 邻接表: 存储连接邻居和链接邻居的权重
vector<vector<int>> graph;
vector<vector<int>> weight;
// 邻接矩阵
// 1.有向加权图, 记录x指向y边的权重, 0表示不相邻
// 2.无向图等于双向图
vector<vector<int>> matrix;
图的遍历
1.所有数据结构被发明出来无非就是为了遍历和访问, 所以遍历是所有数据结构的基础
2.图可以理解为多叉树的复杂版, 适用于树的dfs/bfs遍历基础方法全部适用于图; 图和多叉树遍历的区别在于: 图可能是包含环的, 如果图从一个节点遍历, 可能又会回到这个节点, 这样在遍历的时候就会无穷无尽; 树不存在这个情况; 如果图包含环, 那么遍历需要一个visited数组辅助, 这个visited数组表示当前节点已经被访问过
3.回顾多叉树是怎么遍历的
class TreeNode {
public:
int val;
vector<Node*> children;
TreeNode() {}
TreeNode(int _val) {
val = _val;
}
TreeNode(int _val, vector<TreeNode*> _children) {
val = _val;
children = _children;
}
};
// 多叉树遍历框架
void traverse(TreeNode* root) {
if (root == nullptr)
return;
for (TreeNode* child: root->children) {
traverse(child);
}
}
转载请注明来源, from goldandrabbit.github.io
