目录
1. 相邻节点迭代器的概念
在图数据结构中，相邻节点迭代器（Neighbor Iterator） 是一种用于遍历图中某个顶点的所有相邻节点的工具。其核心目标是高效地枚举某个节点的邻居，常用于图的遍历（如 DFS、BFS）、路径搜索以及各种图算法的实现。
不同的图表示方式（如邻接表、邻接矩阵）影响迭代器的实现方式：
- 邻接表迭代器：遍历链表或动态数组中的邻接节点。
- 邻接矩阵迭代器：遍历矩阵的行来找到相邻节点。
- STL 风格的图迭代器：提供标准化接口，提高通用性。
2. 邻接表迭代器
邻接表 适用于稀疏图，通常使用 链表 或 动态数组 存储相邻节点。因此，邻接表的迭代器通常是 指针 或 迭代器对象，遍历某个节点的邻接链表。
示例实现（C++ STL 风格）
class Graph {
public:
vector<vector<int>> adjList; // 邻接表
explicit Graph(int V) : adjList(V) {}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u); // 无向图
}
vector<int>::iterator neighborsBegin(int v) { return adjList[v].begin(); }
vector<int>::iterator neighborsEnd(int v) { return adjList[v].end(); }
};
使用示例
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
for (auto it = g.neighborsBegin(0); it != g.neighborsEnd(0); ++it) {
cout << "邻居: " << *it << endl;
}
时间复杂度：
- 迭代复杂度：O(degree(v))O(\text{degree}(v))
- 适用于稀疏图。
3. 邻接矩阵迭代器
邻接矩阵 适用于稠密图，通常使用 二维数组 形式存储，迭代器遍历 矩阵的行 来找到所有相邻节点。
示例实现（Python）
class Graph:
def __init__(self, V):
self.V = V
self.adjMatrix = [[0] * V for _ in range(V)] # 初始化邻接矩阵
def add_edge(self, u, v):
self.adjMatrix[u][v] = 1
self.adjMatrix[v][u] = 1 # 无向图
def neighbors(self, v):
return (i for i in range(self.V) if self.adjMatrix[v][i] == 1)
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
for neighbor in g.neighbors(0):
print(f"邻居: {neighbor}")
时间复杂度：
- 迭代复杂度：O(V)O(V)（需要遍历整行）
- 适用于稠密图。
4. STL 风格的图迭代器
在 C++ Boost Graph Library（BGL） 中，提供了一套 STL 风格的图迭代器，使得不同图结构的遍历方式统一。
Boost Graph 迭代器
#include <boost/graph/adjacency_list.hpp>
#include <iostream>
using namespace boost;
typedef adjacency_list<vecS, vecS, undirectedS> Graph;
typedef graph_traits<Graph>::adjacency_iterator adjacency_iterator;
int main() {
Graph g(5);
add_edge(0, 1, g);
add_edge(0, 2, g);
adjacency_iterator it, end;
tie(it, end) = adjacent_vertices(0, g);
for (; it != end; ++it) {
std::cout << "邻居: " << *it << std::endl;
}
}
优点：
- STL 兼容：可与标准容器、算法兼容。
- 适配多种图结构：支持邻接表、邻接矩阵等多种存储方式。
5. 相邻节点迭代器的应用
5.1 图遍历（BFS）
使用相邻节点迭代器实现 广度优先搜索（BFS）：
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
v = queue.popleft()
if v not in visited:
print(f"访问: {v}")
visited.add(v)
queue.extend(graph.neighbors(v))
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
bfs(g, 0)
复杂度：
- 时间复杂度：O(V+E)O(V + E)
- 适用于稀疏图。
5.2 Dijkstra 最短路径
在 邻接表 上使用迭代器实现 Dijkstra 算法：
void dijkstra(Graph &g, int src) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
vector<int> dist(g.V, INT_MAX);
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto it = g.neighborsBegin(u); it != g.neighborsEnd(u); ++it) {
int v = *it;
int weight = 1; // 示例，无权图
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
}
复杂度：
- 邻接表：O((V+E)logV)O((V + E) \log V)
- 邻接矩阵：O(V2)O(V^2)
发表回复