图的存储

常用的是邻接矩阵和邻接表。

不常用的有边集数组，这种场景只在以边为中心进行处理时适用，比如Kruskal最小生成树算法。

注意有向图和无向图在初始化时的处理，如果是无向图，则一条边要插入两次，以下是一段示例代码：

vector<int> G[MAXN]; // 邻接表，G[i]表示顶点i的全部邻接点

void createGraph() {
    int u, v, e;
    cin >> e; // 边的数目
    for(int i = 0; i < e; i++) {
        cin >> u >> v; // 一条边的两个顶点编号
        G[u].push_back(v);
        G[v].push_back(u);
    }
}

图的遍历

分为BFS遍历和DFS遍历。

BFS遍历相当于二叉树的层次遍历，需要借助队列实现，在编码实现时，先访问结点，再设置为已访问状态，再入队，也就是每次入队的元素都是已访问过的，从队里拿出来的元素，只需要关注其邻接点即可，对拿到的邻接点，同样是先访问，再设置为已访问状态，再入队。

DFS一般使用递归实现。








  • 无标签