pta图的存储 邻接表

在图论中，特别是用于表示稀疏图（边的数量远小于节点数量的平方）的数据结构中，邻接表是一种常见的存储方式。邻接表是将图中的每个节点与它相连的所有边或顶点关联起来的一种数据结构。

邻接表的存储通常是这样的：
1. **节点表示**：每个节点有一个编号或指针，表示其在图中的位置。对于有向图，可能还需要存储出度和入度信息。
2. **邻接表数组**：对于无向图，为每个节点维护一个链表或数组，其中包含所有与该节点直接相连的节点列表。如果是有向图，则为每个节点维护两个列表，一个用于存储出度（指向其他节点），另一个用于存储入度（指向指向该节点的节点）。
3. **边的信息**：邻接表中的每个元素不仅包含目标节点，还可能存储额外的边信息，如权重、颜色等，如果图是加权的。

相关问题

pta邻接表存储图

在 PTA 上，通常使用邻接表来存储图。邻接表是一个数组列表，其中每个元素都是一个链表，该链表存储与该节点相邻的节点。

例如，下面的代码可以创建一个有 $n$ 个节点的邻接表，并添加从节点 $u$ 到节点 $v$ 的边：

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1000; // 最大节点数
vector<int> adj[MAXN]; // 邻接表

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入边的两个端点
        adj[u].push_back(v); // 添加从 u 到 v 的边
    }
    // 输出邻接表
    for (int u = 1; u <= n; u++) {
        cout << u << ": ";
        for (int v : adj[u]) {
            cout << v << " ";
        }
        cout << endl;
    }
    return 0;
}

在这个例子中，我们使用 `vector<int>` 来存储链表。由于节点编号从 $1$ 开始，因此我们使用 `for` 循环从 $1$ 到 $n$ 遍历每个节点，输出它所相邻的节点列表。注意，对于无向图，每条边应该被添加两次（从 $u$ 到 $v$，从 $v$ 到 $u$）。

邻接表存储图的广度优先遍历pta

以下是使用邻接表存储图的广度优先遍历的代码实现，使用了队列来辅助实现：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 1000;
vector<int> G[MAXN]; // 邻接表存储图
bool vis[MAXN]; // 访问标记数组

void BFS(int s) {
    queue<int> q; // 队列
    q.push(s); // 将起点加入队列
    vis[s] = true; // 标记起点已访问
    while (!q.empty()) { // 队列不为空则循环
        int u = q.front();
        q.pop(); // 取出队首元素
        cout << u << " "; // 输出访问顺序
        for (int i = 0; i < G[u].size(); i++) { // 枚举与u相邻的点
            int v = G[u][i];
            if (!vis[v]) { // 如果v未被访问
                q.push(v); // 将v加入队列
                vis[v] = true; // 标记v已访问
            }
        }
    }
}

int main() {
    int n, m, s; // n为点数，m为边数，s为起点
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) { // 读入边
        int u, v;
        cin >> u >> v;
        G[u].push_back(v); // 存储边
        G[v].push_back(u); // 无向图需要反向存储一次
    }
    BFS(s); // 广度优先遍历
    return 0;
}

其中，输入格式为：

n m s
u1 v1
u2 v2
...
um vm

其中，n为点数，m为边数，s为起点；接下来m行为边的信息。输出为广度优先遍历的访问顺序。