通过代码实现分别实现有向网和无向网的邻接矩阵存储的创建函数,以及图的深度优先搜索函数。通过以下给出的有向网和无向往进行验证。(顶点的数据为顶点的名称字符数组char name[2]:“G1“,G2“,“G3”…)
时间: 2024-02-12 18:09:14 浏览: 25
好的,我可以帮你实现这个功能。
以下是有向网和无向网的邻接矩阵存储的创建函数实现代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100; // 顶点数的最大值
const int INF = 0x3f3f3f3f; // 表示正无穷的值
// 有向网的邻接矩阵存储结构
typedef struct {
char name[MAXN][2]; // 存储每个顶点的名称
int edge[MAXN][MAXN]; // 存储边的权值
int vexnum, arcnum; // 图的顶点数和边数
} DG;
// 有向网的邻接矩阵创建函数
void CreateDG(DG &G) {
cout<<"请输入图的顶点数和边数:";
cin>>G.vexnum>>G.arcnum;
for(int i=0; i<G.vexnum; i++) {
cout<<"请输入第"<<i+1<<"个顶点的名称:";
cin>>G.name[i];
}
memset(G.edge, INF, sizeof(G.edge)); // 初始化边的权值为正无穷
for(int i=0; i<G.arcnum; i++) {
int u, v, w;
cout<<"请输入第"<<i+1<<"条边的起点、终点和权值:";
cin>>u>>v>>w;
G.edge[u-1][v-1] = w; // 存储边的权值
}
}
// 无向网的邻接矩阵存储结构
typedef struct {
char name[MAXN][2]; // 存储每个顶点的名称
int edge[MAXN][MAXN]; // 存储边的权值
int vexnum, arcnum; // 图的顶点数和边数
} UDG;
// 无向网的邻接矩阵创建函数
void CreateUDG(UDG &G) {
cout<<"请输入图的顶点数和边数:";
cin>>G.vexnum>>G.arcnum;
for(int i=0; i<G.vexnum; i++) {
cout<<"请输入第"<<i+1<<"个顶点的名称:";
cin>>G.name[i];
}
memset(G.edge, INF, sizeof(G.edge)); // 初始化边的权值为正无穷
for(int i=0; i<G.arcnum; i++) {
int u, v, w;
cout<<"请输入第"<<i+1<<"条边的起点、终点和权值:";
cin>>u>>v>>w;
G.edge[u-1][v-1] = G.edge[v-1][u-1] = w; // 存储边的权值
}
}
```
以下是图的深度优先搜索函数的实现代码:
```c++
bool visited[MAXN]; // 标记每个顶点是否被访问过
// 有向网的深度优先搜索函数
void DFS_DG(DG &G, int v) {
cout<<G.name[v]<<" "; // 访问当前顶点
visited[v] = true; // 标记当前顶点为已访问
for(int i=0; i<G.vexnum; i++) {
if(G.edge[v][i]!=INF && !visited[i]) { // 如果顶点i与当前顶点v有连边且未被访问
DFS_DG(G, i); // 递归访问顶点i
}
}
}
// 无向网的深度优先搜索函数
void DFS_UDG(UDG &G, int v) {
cout<<G.name[v]<<" "; // 访问当前顶点
visited[v] = true; // 标记当前顶点为已访问
for(int i=0; i<G.vexnum; i++) {
if(G.edge[v][i]!=INF && !visited[i]) { // 如果顶点i与当前顶点v有连边且未被访问
DFS_UDG(G, i); // 递归访问顶点i
}
}
}
```
下面是对有向网和无向网进行验证的代码:
```c++
int main() {
DG G1;
cout<<"创建有向网G1:"<<endl;
CreateDG(G1);
cout<<"有向网G1的邻接矩阵:"<<endl;
for(int i=0; i<G1.vexnum; i++) {
for(int j=0; j<G1.vexnum; j++) {
if(G1.edge[i][j] == INF) {
cout<<"INF"<<" ";
} else {
cout<<G1.edge[i][j]<<" ";
}
}
cout<<endl;
}
memset(visited, false, sizeof(visited));
cout<<"有向网G1的深度优先搜索序列为:"<<endl;
for(int i=0; i<G1.vexnum; i++) {
if(!visited[i]) { // 如果顶点i未被访问
DFS_DG(G1, i); // 从顶点i开始深度优先搜索
}
}
cout<<endl;
UDG G2;
cout<<"创建无向网G2:"<<endl;
CreateUDG(G2);
cout<<"无向网G2的邻接矩阵:"<<endl;
for(int i=0; i<G2.vexnum; i++) {
for(int j=0; j<G2.vexnum; j++) {
if(G2.edge[i][j] == INF) {
cout<<"INF"<<" ";
} else {
cout<<G2.edge[i][j]<<" ";
}
}
cout<<endl;
}
memset(visited, false, sizeof(visited));
cout<<"无向网G2的深度优先搜索序列为:"<<endl;
for(int i=0; i<G2.vexnum; i++) {
if(!visited[i]) { // 如果顶点i未被访问
DFS_UDG(G2, i); // 从顶点i开始深度优先搜索
}
}
cout<<endl;
return 0;
}
```
希望这份代码可以帮助到你,有问题可以继续询问我哦。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)