编写一个程序实现图的两种遍历算法,并在此基 础上设计一个主程序完成如下功能: (1)输出如图1所示的有向图G从项点V1开始的深度优先遊历序列。 (2)输出如图1所示的有向图G从顶点V1开始的广度优先遍历序列
时间: 2024-02-09 17:09:29 浏览: 29
好的,请稍等,我来为您解答。
深度优先遍历算法:
```
// 递归实现
void DFS(int v, vector<int> adj[], vector<bool>& visited, vector<int>& dfs) {
visited[v] = true;
dfs.push_back(v);
for (int i = 0; i < adj[v].size(); ++i) {
int u = adj[v][i];
if (!visited[u]) DFS(u, adj, visited, dfs);
}
}
vector<int> depthFirstSearch(int V, vector<int> adj[], int start) {
vector<bool> visited(V, false);
vector<int> dfs;
DFS(start, adj, visited, dfs);
return dfs;
}
```
广度优先遍历算法:
```
vector<int> breadthFirstSearch(int V, vector<int> adj[], int start) {
vector<bool> visited(V, false);
vector<int> bfs;
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
bfs.push_back(v);
for (int i = 0; i < adj[v].size(); ++i) {
int u = adj[v][i];
if (!visited[u]) {
visited[u] = true;
q.push(u);
}
}
}
return bfs;
}
```
主程序的实现:
```
int main() {
int V = 6;
vector<int> adj[V];
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(3);
adj[1].push_back(4);
adj[2].push_back(4);
adj[3].push_back(5);
adj[4].push_back(5);
int start = 0;
vector<int> dfs = depthFirstSearch(V, adj, start);
vector<int> bfs = breadthFirstSearch(V, adj, start);
cout << "Depth first search sequence starting from vertex " << start << ": ";
for (int i = 0; i < dfs.size(); ++i) {
cout << dfs[i] << " ";
}
cout << endl;
cout << "Breadth first search sequence starting from vertex " << start << ": ";
for (int i = 0; i < bfs.size(); ++i) {
cout << bfs[i] << " ";
}
cout << endl;
return 0;
}
```
输出结果为:
```
Depth first search sequence starting from vertex 0: 0 1 3 5 4 2
Breadth first search sequence starting from vertex 0: 0 1 2 3 4 5
```