设计有向图的邻接表类,实现深度优先非递归遍历、广度优 先遍历
时间: 2023-06-03 16:05:51 浏览: 103
好的,这个问题是关于数据结构和算法的,我可以回答你。
设计有向图的邻接表类,可以定义如下:
```
class Graph {
private:
int numVertices; // 图中顶点数量
vector<vector<int>> adjList; // 邻接表,用 vector 存储每个顶点的邻居
public:
Graph(int n) {
numVertices = n;
adjList.resize(n);
}
// 添加一条边
void addEdge(int src, int dest) {
adjList[src].push_back(dest);
}
// 深度优先非递归遍历
void dfs(int start) {
vector<bool> visited(numVertices, false); // 标记顶点是否已经被访问
stack<int> s; // 模拟递归栈
s.push(start);
while (!s.empty()) {
int cur = s.top();
s.pop();
if (visited[cur]) {
continue;
}
visited[cur] = true;
cout << cur << " "; // 输出遍历结果
// 将未访问过的邻居按倒序压入栈中,保证顺序是从左到右
for (int i = adjList[cur].size() - 1; i >= 0; i--) {
int neighbor = adjList[cur][i];
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
// 广度优先遍历
void bfs(int start) {
vector<bool> visited(numVertices, false); // 标记顶点是否已经被访问
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
cout << cur << " "; // 输出遍历结果
// 遍历所有邻居,如果未访问过则压入队列
for (int neighbor : adjList[cur]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
}
};
```
你可以根据以上代码实现一个有向图的邻接表,并且调用 `dfs()` 或 `bfs()` 方法进行遍历。希望可以帮助到你。
阅读全文