你是一名编程师,你现在要写一份代码,要求如下 1.图的定义及存储表示(邻接矩阵和邻接表)。 2.无向图或有向图的创建。 3.采用邻接矩阵表示图的深度优先搜索遍历。 4.采用邻接表表示图的深度优先搜索遍历。 5.采用邻接矩阵表示图的广度优先搜索遍历。 6.采用邻接表表示图的广度优先搜索遍历。 7.按照C或C++程序编码规范进行编程。
时间: 2024-02-26 19:58:40 浏览: 100
图的存储结构(邻接表或邻接矩阵),的深度优先搜索遍历路径。
5星 · 资源好评率100%
好的,根据你的要求,我可以给你提供一个基本的代码框架,你可以在此基础上进行修改和完善。
```C++
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
// 定义图的结构体
struct Graph {
int vertex_num; // 图的顶点数
bool is_directed; // 是否为有向图
int **matrix; // 邻接矩阵
vector<vector<int>> list; // 邻接表
};
// 创建图
Graph createGraph(int vertex_num, bool is_directed) {
Graph graph;
graph.vertex_num = vertex_num;
graph.is_directed = is_directed;
// 创建邻接矩阵
graph.matrix = new int*[vertex_num];
for (int i = 0; i < vertex_num; i++) {
graph.matrix[i] = new int[vertex_num];
for (int j = 0; j < vertex_num; j++) {
graph.matrix[i][j] = 0;
}
}
// 创建邻接表
graph.list = vector<vector<int>>(vertex_num);
return graph;
}
// 添加边
void addEdge(Graph &graph, int from, int to) {
// 添加邻接矩阵的边
graph.matrix[from][to] = 1;
if (!graph.is_directed) {
graph.matrix[to][from] = 1;
}
// 添加邻接表的边
graph.list[from].push_back(to);
if (!graph.is_directed) {
graph.list[to].push_back(from);
}
}
// 邻接矩阵的深度优先遍历
void dfs_matrix(Graph graph, int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (int i = 0; i < graph.vertex_num; i++) {
if (graph.matrix[v][i] == 1 && !visited[i]) {
dfs_matrix(graph, i, visited);
}
}
}
// 邻接表的深度优先遍历
void dfs_list(Graph graph, int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (int i = 0; i < graph.list[v].size(); i++) {
int next = graph.list[v][i];
if (!visited[next]) {
dfs_list(graph, next, visited);
}
}
}
// 邻接矩阵的广度优先遍历
void bfs_matrix(Graph graph, int v, bool visited[]) {
queue<int> q;
q.push(v);
visited[v] = true;
while (!q.empty()) {
int curr = q.front();
q.pop();
cout << curr << " ";
for (int i = 0; i < graph.vertex_num; i++) {
if (graph.matrix[curr][i] == 1 && !visited[i]) {
q.push(i);
visited[i] = true;
}
}
}
}
// 邻接表的广度优先遍历
void bfs_list(Graph graph, int v, bool visited[]) {
queue<int> q;
q.push(v);
visited[v] = true;
while (!q.empty()) {
int curr = q.front();
q.pop();
cout << curr << " ";
for (int i = 0; i < graph.list[curr].size(); i++) {
int next = graph.list[curr][i];
if (!visited[next]) {
q.push(next);
visited[next] = true;
}
}
}
}
int main() {
int vertex_num = 5;
bool is_directed = false;
Graph graph = createGraph(vertex_num, is_directed);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
bool visited[vertex_num] = {false};
// 邻接矩阵的深度优先遍历
cout << "Matrix DFS: ";
for (int i = 0; i < vertex_num; i++) {
if (!visited[i]) {
dfs_matrix(graph, i, visited);
}
}
cout << endl;
// 邻接表的深度优先遍历
memset(visited, false, sizeof(visited));
cout << "List DFS: ";
for (int i = 0; i < vertex_num; i++) {
if (!visited[i]) {
dfs_list(graph, i, visited);
}
}
cout << endl;
// 邻接矩阵的广度优先遍历
memset(visited, false, sizeof(visited));
cout << "Matrix BFS: ";
for (int i = 0; i < vertex_num; i++) {
if (!visited[i]) {
bfs_matrix(graph, i, visited);
}
}
cout << endl;
// 邻接表的广度优先遍历
memset(visited, false, sizeof(visited));
cout << "List BFS: ";
for (int i = 0; i < vertex_num; i++) {
if (!visited[i]) {
bfs_list(graph, i, visited);
}
}
cout << endl;
return 0;
}
```
这份代码实现了图的创建、邻接矩阵和邻接表的存储表示、深度优先搜索遍历和广度优先搜索遍历,并且按照C或C++程序编码规范进行编程。你可以根据自己的需求进行修改和完善。
阅读全文