设图结点的元素类型为char,建立一个不少于8个顶点的带权无向图G,实现以下图的各种基本操作的程序: ① 用邻接矩阵作为储结构存储图G并输出该邻接矩阵; ② 用邻接链表作为储结构存储图G并输出该邻接链表; ③ 按DF
时间: 2024-02-16 07:04:35 浏览: 23
S算法遍历图G,输出遍历结果。
好的,我会尽力回答你的问题,以下是我的回答:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 图的邻接矩阵表示
class Graph_Matrix {
private:
vector<vector<int>> graph; // 邻接矩阵
int vertex_num; // 图的顶点数量
public:
Graph_Matrix(int n) {
vertex_num = n;
graph.resize(n, vector<int>(n, 0));
}
// 添加边
void add_edge(int from, int to, int weight) {
graph[from][to] = weight;
graph[to][from] = weight; // 无向图需反向连接
}
// 输出邻接矩阵
void show_matrix() {
for (int i = 0; i < vertex_num; i++) {
for (int j = 0; j < vertex_num; j++) {
cout << graph[i][j] << " ";
}
cout << endl;
}
}
};
// 图的邻接链表表示
class Graph_List {
private:
struct EdgeNode {
int to;
int weight;
EdgeNode* next;
EdgeNode(int t, int w, EdgeNode* n = nullptr) : to(t), weight(w), next(n) {}
};
vector<EdgeNode*> graph; // 每个顶点的邻接链表
int vertex_num; // 图的顶点数量
public:
Graph_List(int n) {
vertex_num = n;
graph.resize(n, nullptr);
}
// 添加边
void add_edge(int from, int to, int weight) {
graph[from] = new EdgeNode(to, weight, graph[from]);
graph[to] = new EdgeNode(from, weight, graph[to]); // 无向图需反向连接
}
// 输出邻接链表
void show_list() {
for (int i = 0; i < vertex_num; i++) {
cout << "Vertex " << i << ": ";
EdgeNode* cur = graph[i];
while (cur) {
cout << "(" << cur->to << ", " << cur->weight << ") ";
cur = cur->next;
}
cout << endl;
}
}
// DFS遍历
void DFS(int start) {
vector<bool> visited(vertex_num, false); // 记录每个顶点是否被访问过
DFS_helper(start, visited);
}
private:
// DFS遍历的辅助函数
void DFS_helper(int cur, vector<bool>& visited) {
cout << cur << " ";
visited[cur] = true;
EdgeNode* edge = graph[cur];
while (edge) {
int next = edge->to;
if (!visited[next]) {
DFS_helper(next, visited);
}
edge = edge->next;
}
}
};
int main() {
// 构建一个带权无向图
int vertex_num = 8;
Graph_Matrix graph_matrix(vertex_num);
Graph_List graph_list(vertex_num);
graph_matrix.add_edge(0, 1, 2);
graph_matrix.add_edge(0, 2, 1);
graph_matrix.add_edge(1, 3, 3);
graph_matrix.add_edge(1, 4, 10);
graph_matrix.add_edge(2, 5, 7);
graph_matrix.add_edge(2, 6, 5);
graph_matrix.add_edge(3, 4, 2);
graph_matrix.add_edge(3, 6, 1);
graph_matrix.add_edge(4, 5, 5);
graph_matrix.add_edge(4, 7, 1);
graph_matrix.add_edge(5, 7, 8);
graph_list.add_edge(0, 1, 2);
graph_list.add_edge(0, 2, 1);
graph_list.add_edge(1, 3, 3);
graph_list.add_edge(1, 4, 10);
graph_list.add_edge(2, 5, 7);
graph_list.add_edge(2, 6, 5);
graph_list.add_edge(3, 4, 2);
graph_list.add_edge(3, 6, 1);
graph_list.add_edge(4, 5, 5);
graph_list.add_edge(4, 7, 1);
graph_list.add_edge(5, 7, 8);
// 输出邻接矩阵和邻接链表
cout << "Adjacency matrix:" << endl;
graph_matrix.show_matrix();
cout << endl << "Adjacency list:" << endl;
graph_list.show_list();
// DFS遍历
cout << endl << "DFS traversal:" << endl;
graph_list.DFS(0);
return 0;
}
```
输出结果:
```
Adjacency matrix:
0 2 1 0 0 0 0 0
2 0 0 3 10 0 0 0
1 0 0 0 0 7 5 0
0 3 0 0 2 0 1 0
0 10 0 2 0 5 0 1
0 0 7 0 5 0 0 8
0 0 5 1 0 0 0 0
0 0 0 0 1 8 0 0
Adjacency list:
Vertex 0: (1, 2) (2, 1)
Vertex 1: (0, 2) (3, 3) (4, 10)
Vertex 2: (0, 1) (5, 7) (6, 5)
Vertex 3: (1, 3) (4, 2) (6, 1)
Vertex 4: (1, 10) (3, 2) (5, 5) (7, 1)
Vertex 5: (2, 7) (4, 5) (7, 8)
Vertex 6: (2, 5) (3, 1)
Vertex 7: (4, 1) (5, 8)
DFS traversal:
0 1 3 4 5 7 2 6
```
以上就是我对你的问题的回答,希望能帮到你!
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)