给出代码,要求实现图的一些基本运算,包括图的初始化,图的创建,图的输出,遍历,转换,销毁,退出
时间: 2024-04-29 10:21:54 浏览: 106
实现各种图的建立和输出
以下是一个简单的图的实现代码,包括图的初始化、创建、输出、遍历、转换、销毁和退出操作。这里使用邻接矩阵来表示无向图,可以通过修改代码来实现有向图或其他图的数据结构。
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100;
// 图的结构体
struct Graph {
int V; // 图的顶点数
int E; // 图的边数
int adj[MAXN][MAXN]; // 邻接矩阵表示图
};
// 初始化图
void init(Graph& G, int V) {
G.V = V;
G.E = 0;
for (int i = 0; i < G.V; i++) {
for (int j = 0; j < G.V; j++) {
G.adj[i][j] = 0;
}
}
}
// 创建图
void create(Graph& G) {
int u, v;
while (cin >> u >> v) {
G.adj[u][v] = G.adj[v][u] = 1; // 添加无向边
G.E++;
}
}
// 输出图
void print(Graph& G) {
cout << "Graph: V=" << G.V << ", E=" << G.E << endl;
for (int i = 0; i < G.V; i++) {
for (int j = 0; j < G.V; j++) {
cout << G.adj[i][j] << " ";
}
cout << endl;
}
}
// DFS遍历图
void dfs(Graph& G, int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int i = 0; i < G.V; i++) {
if (G.adj[v][i] && !visited[i]) {
dfs(G, i, visited);
}
}
}
// BFS遍历图
void bfs(Graph& G, int v, vector<bool>& visited) {
vector<int> q;
q.push_back(v);
visited[v] = true;
while (!q.empty()) {
int u = q.front();
q.erase(q.begin());
cout << u << " ";
for (int i = 0; i < G.V; i++) {
if (G.adj[u][i] && !visited[i]) {
visited[i] = true;
q.push_back(i);
}
}
}
}
// 转换图为有向图
void to_directed(Graph& G) {
for (int i = 0; i < G.V; i++) {
for (int j = 0; j < G.V; j++) {
if (G.adj[i][j] && !G.adj[j][i]) { // 如果存在边(i,j)但不存在边(j,i),则添加边(j,i)
G.adj[j][i] = 1;
}
}
}
}
// 销毁图
void destroy(Graph& G) {
G.V = 0;
G.E = 0;
}
int main() {
Graph G;
vector<bool> visited(MAXN, false); // 标记顶点是否已经被访问过
init(G, 5); // 初始化一个5个顶点的图
create(G); // 从标准输入读取无向边,创建图
print(G); // 输出图
cout << "DFS: ";
dfs(G, 0, visited); // DFS遍历图
cout << endl;
visited.assign(MAXN, false); // 重置visited数组
cout << "BFS: ";
bfs(G, 0, visited); // BFS遍历图
cout << endl;
to_directed(G); // 转换为有向图
print(G); // 输出图
destroy(G); // 销毁图
return 0;
}
```
示例输入输出:
输入:
```
0 1
0 2
1 3
2 4
```
输出:
```
Graph: V=5, E=4
0 1 1 0 0
1 0 0 1 0
1 0 0 0 1
0 1 0 0 0
0 0 1 0 0
DFS: 0 1 3 2 4
BFS: 0 1 2 3 4
Graph: V=5, E=8
0 1 1 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
```
阅读全文