输入图的类型、顶点数、狐(边)数、顶点信息、狐(边)信息,建立相应的图(具体类型是无向网,采用邻接矩阵存储结构);分别按深度优先搜索和广度优先搜索遍历图;按某种形式输出图及遍历结果。
时间: 2024-05-07 21:23:08 浏览: 69
好的,我来为你介绍一下无向网图的建立、深度优先搜索和广度优先搜索。
无向网是一个有顶点和边组成的图,边具有权值。它可以用邻接矩阵来存储。
在邻接矩阵中,数组的行和列分别表示图中的顶点,矩阵中的值表示两个顶点之间的边的权值。如果两个顶点之间没有边,则权值为0。
下面是一个无向网的邻接矩阵表示:
```
A B C D
A 0 3 4 0
B 3 0 2 0
C 4 2 0 5
D 0 0 5 0
```
在这个无向网中,有4个顶点,分别为A、B、C、D。其中,A和B之间有一条权值为3的边,A和C之间有一条权值为4的边,C和B之间有一条权值为2的边,C和D之间有一条权值为5的边。
接下来,我们用C++语言来实现这个无向网的建立、深度优先搜索和广度优先搜索。
```cpp
#include <iostream>
#include <queue>
using namespace std;
const int MAX_SIZE = 100; // 最大顶点数
const int INF = 0x3f3f3f3f; // 表示正无穷
// 邻接矩阵存储结构
class MGraph {
public:
int vexNum; // 顶点数
int edgeNum; // 边数
int matrix[MAX_SIZE][MAX_SIZE]; // 邻接矩阵
// 初始化邻接矩阵
void init() {
for (int i = 0; i < MAX_SIZE; i++) {
for (int j = 0; j < MAX_SIZE; j++) {
matrix[i][j] = (i == j ? 0 : INF);
}
}
}
// 建立无向网
void create() {
cout << "请输入顶点数和边数:";
cin >> vexNum >> edgeNum;
init(); // 初始化邻接矩阵
// 输入每条边的信息
for (int i = 0; i < edgeNum; i++) {
int u, v, w;
cout << "请输入边的起点、终点和权值:";
cin >> u >> v >> w;
matrix[u][v] = matrix[v][u] = w;
}
}
// 深度优先搜索
void dfs() {
bool visited[MAX_SIZE] = { false };
cout << "深度优先搜索结果:";
for (int i = 0; i < vexNum; i++) {
if (!visited[i]) {
dfs(i, visited);
}
}
cout << endl;
}
// 从顶点v开始深度优先搜索
void dfs(int v, bool visited[]) {
visited[v] = true;
cout << v << " ";
for (int i = 0; i < vexNum; i++) {
if (matrix[v][i] != 0 && matrix[v][i] != INF && !visited[i]) {
dfs(i, visited);
}
}
}
// 广度优先搜索
void bfs() {
bool visited[MAX_SIZE] = { false };
cout << "广度优先搜索结果:";
queue<int> q;
for (int i = 0; i < vexNum; i++) {
if (!visited[i]) {
visited[i] = true;
cout << i << " ";
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < vexNum; v++) {
if (matrix[u][v] != 0 && matrix[u][v] != INF && !visited[v]) {
visited[v] = true;
cout << v << " ";
q.push(v);
}
}
}
}
}
cout << endl;
}
// 输出邻接矩阵
void print() {
cout << "邻接矩阵:" << endl;
for (int i = 0; i < vexNum; i++) {
for (int j = 0; j < vexNum; j++) {
if (matrix[i][j] == INF) {
cout << "INF" << " ";
}
else {
cout << matrix[i][j] << " ";
}
}
cout << endl;
}
}
};
int main() {
MGraph g;
g.create(); // 建立无向网
g.print(); // 输出邻接矩阵
g.dfs(); // 深度优先搜索
g.bfs(); // 广度优先搜索
return 0;
}
```
运行程序后,输入顶点数和边数,然后输入每条边的起点、终点和权值,即可建立一个无向网,并输出它的邻接矩阵。接着,程序会按照深度优先搜索和广度优先搜索的方式遍历这个图,并输出遍历结果。
例如,输入以下信息:
```
请输入顶点数和边数:4 5
请输入边的起点、终点和权值:0 1 3
请输入边的起点、终点和权值:0 2 4
请输入边的起点、终点和权值:1 2 2
请输入边的起点、终点和权值:2 3 5
请输入边的起点、终点和权值:1 3 6
```
则程序会输出以下内容:
```
邻接矩阵:
0 3 4 INF
3 0 2 6
4 2 0 5
INF 6 5 0
深度优先搜索结果:0 1 2 3
广度优先搜索结果:0 1 2 3
```
阅读全文