头歌 图的邻接矩阵存储及求邻接点操作 参考答案
时间: 2024-02-10 22:42:49 浏览: 78
邻接矩阵是一种常见的图的存储方式,可以通过一个二维矩阵来表示图中的节点之间的关系。对于一个有 $n$ 个节点的图,邻接矩阵 $G$ 是一个 $n \times n$ 的矩阵,其中 $G_{i,j}$ 表示节点 $i$ 和节点 $j$ 之间是否有边相连,如果有则为 $1$,否则为 $0$。对于无向图,邻接矩阵是一个对称矩阵,即 $G_{i,j} = G_{j,i}$。
下面给出邻接矩阵存储和求邻接点的代码示例:
```c++
const int MAXN = 100; // 最大节点数
int G[MAXN][MAXN]; // 邻接矩阵
int n; // 节点数
// 添加一条边
void add_edge(int u, int v) {
G[u][v] = G[v][u] = 1;
}
// 删除一条边
void remove_edge(int u, int v) {
G[u][v] = G[v][u] = 0;
}
// 判断是否有边相连
bool has_edge(int u, int v) {
return G[u][v];
}
// 求节点 u 的所有邻接点
vector<int> get_adjacent_vertices(int u) {
vector<int> adj; // 邻接点数组
for (int v = 0; v < n; v++) {
if (G[u][v]) {
adj.push_back(v);
}
}
return adj;
}
```
上述代码中,`add_edge` 函数用于添加一条边,`remove_edge` 函数用于删除一条边,`has_edge` 函数用于判断是否有边相连,`get_adjacent_vertices` 函数用于求节点 $u$ 的所有邻接点。其中,`vector` 是 C++ 标准库中的一个动态数组类型,可以方便地添加和删除元素。