定义一有n个结点的的以邻接矩阵为存储方式的网(有向或无向均可),并对其进行如下操作: 1.深度优先遍历,并输出遍历序列; 2.广度优先遍历,并输出遍历序列; 3.求源点到图中每个点的最短路径,并输出; 4.输出图 C++代码怎么写?
时间: 2024-03-27 11:41:41 浏览: 39
好的,以下是实现以上操作的 C++ 代码:
```c++
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
const int MAXN = 100; //最大结点数
int n; //结点数
int a[MAXN][MAXN]; //邻接矩阵
bool visited[MAXN]; //标记结点是否访问过
//深度优先遍历
void dfs(int u) {
visited[u] = true;
cout << u << " ";
for (int v = 0; v < n; v++) {
if (a[u][v] != 0 && !visited[v]) {
dfs(v);
}
}
}
//广度优先遍历
void bfs(int s) {
queue<int> q;
q.push(s);
visited[s] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int v = 0; v < n; v++) {
if (a[u][v] != 0 && !visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
//求最短路径
void shortestPath(int s) {
const int INF = 0x3f3f3f3f; //表示正无穷
int dist[MAXN]; //dist[i]表示源点s到结点i的最短距离
bool inQueue[MAXN]; //标记结点是否在队列中
queue<int> q;
for (int i = 0; i < n; i++) {
dist[i] = INF;
inQueue[i] = false;
}
dist[s] = 0;
inQueue[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
inQueue[u] = false;
for (int v = 0; v < n; v++) {
if (a[u][v] != 0 && dist[v] > dist[u] + a[u][v]) {
dist[v] = dist[u] + a[u][v];
if (!inQueue[v]) {
q.push(v);
inQueue[v] = true;
}
}
}
}
//输出最短路径
cout << "源点到各点的最短路径如下:" << endl;
for (int i = 0; i < n; i++) {
if (dist[i] == INF) {
cout << "源点" << s << "到结点" << i << "不存在路径" << endl;
} else {
cout << "源点" << s << "到结点" << i << "的最短路径长度为:" << dist[i] << endl;
}
}
}
int main() {
//读入数据
cout << "请输入结点数n:";
cin >> n;
cout << "请输入邻接矩阵a:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
}
//深度优先遍历
cout << "深度优先遍历序列为:";
for (int i = 0; i < n; i++) {
visited[i] = false;
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i);
}
}
cout << endl;
//广度优先遍历
cout << "广度优先遍历序列为:";
for (int i = 0; i < n; i++) {
visited[i] = false;
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
bfs(i);
}
}
cout << endl;
//求最短路径
int s;
cout << "请输入源点s:";
cin >> s;
shortestPath(s);
return 0;
}
```
注意:以上代码只是一种实现方式,实际上还有很多其他实现方式,比如使用邻接表存储图等。
阅读全文