1. 建立无向图在邻接矩阵 2. 图的深度优先遍历 3. 图的广深度优先遍历
时间: 2024-06-14 12:03:30 浏览: 25
1. 建立无向图在邻接矩阵:
邻接矩阵是一种常见的图的存储方式,可以用一个二维数组来表示图中各个节点之间的关系。对于无向图,邻接矩阵是一个对称矩阵,因为节点i到节点j的关系和节点j到节点i的关系是相同的。下面是一个C++的示例代码,用邻接矩阵表示上述无向图:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;
int G[MAXN][MAXN]; // 邻接矩阵
int n, m; // n表示节点数,m表示边数
int main() {
cin >> n >> m;
memset(G, 0, sizeof(G)); // 初始化邻接矩阵
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u][v] = G[v][u] = 1; // 无向图的邻接矩阵是对称矩阵
}
return 0;
}
```
2. 图的深度优先遍历:
深度优先遍历是一种常见的图遍历算法,其基本思想是从某个节点开始,沿着一条路径一直走到底,直到不能再走为止,然后回溯到上一个节点,再沿着另一条路径走到底,直到所有的节点都被访问过为止。下面是一个C++的示例代码,用深度优先遍历遍历上述无向图:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;
int G[MAXN][MAXN]; // 邻接矩阵
int n, m; // n表示节点数,m表示边数
bool vis[MAXN]; // 标记数组,记录每个节点是否被访问过
void dfs(int u) {
vis[u] = true; // 标记节点u已经被访问过
cout << u << " "; // 输出节点u
for (int v = 0; v < n; v++) {
if (G[u][v] && !vis[v]) { // 如果节点u和节点v之间有边,并且节点v没有被访问过
dfs(v); // 递归访问节点v
}
}
}
int main() {
cin >> n >> m;
memset(G, 0, sizeof(G)); // 初始化邻接矩阵
memset(vis, false, sizeof(vis)); // 初始化标记数组
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u][v] = G[v][u] = 1; // 无向图的邻接矩阵是对称矩阵
}
dfs(1); // 从节点1开始深度优先遍历
return 0;
}
```
3. 图的广度优先遍历:
广度优先遍历是一种常见的图遍历算法,其基本思想是从某个节点开始,先访问它的所有邻居节点,然后再依次访问它们的邻居节点,直到所有的节点都被访问过为止。下面是一个C++的示例代码,用广度优先遍历遍历上述无向图:
```c++
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 100;
int G[MAXN][MAXN]; // 邻接矩阵
int n, m; // n表示节点数,m表示边数
bool vis[MAXN]; // 标记数组,记录每个节点是否被访问过
void bfs(int u) {
queue<int> q; // 定义一个队列
q.push(u); // 将节点u加入队列
vis[u] = true; // 标记节点u已经被访问过
while (!q.empty()) { // 当队列不为空时
int x = q.front(); // 取出队首元素x
q.pop(); // 弹出队首元素
cout << x << " "; // 输出节点x
for (int v = 0; v < n; v++) {
if (G[x][v] && !vis[v]) { // 如果节点x和节点v之间有边,并且节点v没有被访问过
q.push(v); // 将节点v加入队列
vis[v] = true; // 标记节点v已经被访问过
}
}
}
}
int main() {
cin >> n >> m;
memset(G,0, sizeof(G)); // 初始化邻接矩阵
memset(vis, false, sizeof(vis)); // 初始化标记数组
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u][v] = G[v][u] = 1; // 无向图的邻接矩阵是对称矩阵
}
bfs(1); // 从节点1开始广度优先遍历
return 0;
}
```