C++98以下版本,设计一个基于图的邻接矩阵的图的基本操作的演示程序。 【基本要求】 实现下列六种基本运算:(1)创建图;(2)深度优先遍历图;(3)广度优先遍历图;(4)转换图的存储结构 分别在图的邻接矩阵和邻接表的存储结构实现
时间: 2024-12-13 20:24:50 浏览: 28
有向图邻接矩阵c++运算操作
在C++98及更低版本中,由于缺乏现代模板和STL的支持,我们需要手动编写一些基本的数据结构以及函数来实现邻接矩阵的图。这里是一个简单的示例:
```cpp
#include <iostream>
using namespace std;
// 邻接矩阵表示图的结构
const int MAX_V = 100; // 图的最大顶点数
bool adjMatrix[MAX_V][MAX_V]; // 初始化所有边为false
// 创建图
void createGraph(int v, pair<int, int> edges[]) {
for (int i = 0; i < v; i++) {
for (int j = 0; j < v; j++) {
adjMatrix[i][j] = false;
}
}
for (int i = 0; i < v; i++) {
for (int edge : edges) {
if (i == edge.first)
adjMatrix[i][edge.second] = true;
else if (i == edge.second)
adjMatrix[edge.first][i] = true;
}
}
}
// 深度优先搜索
void dfs(int src) {
bool visited[MAX_V] = {false};
dfsUtil(src, visited);
}
void dfsUtil(int vertex, bool* visited) {
visited[vertex] = true;
cout << vertex << " ";
for (int i = 0; i < MAX_V; i++)
if (adjMatrix[vertex][i] && !visited[i])
dfsUtil(i, visited);
}
// 广度优先搜索
void bfs(int src) {
bool visited[MAX_V] = {false};
queue<int> q;
visited[src] = true;
q.push(src);
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int v = 0; v < MAX_V; v++)
if (adjMatrix[u][v] && !visited[v])
visited[v] = true,
q.push(v);
}
}
// 转换存储结构:从邻接矩阵转到邻接表
void convertToAdjList() {
int degree[MAX_V] = {0}; // 记录每个节点的出度
for (int i = 0; i < MAX_V; i++) {
for (int j = 0; j < MAX_V; j++) {
if (adjMatrix[i][j]) {
degree[j]++;
}
}
}
vector<pair<int, vector<int>>> adjList(MAX_V); // 新的邻接列表表示法
for (int i = 0; i < MAX_V; i++) {
for (int j = 0; j < MAX_V; j++) {
if (adjMatrix[i][j]) {
adjList[i].second.push_back(j);
}
}
for (int k = 0; k < degree[i]; k++) {
cout << i << " -> " << adjList[i].second[k] << "\n";
}
}
}
int main() {
int v, e;
cout << "Enter number of vertices and edges: ";
cin >> v >> e;
pair<int, int> edges[e];
cout << "Enter edges in form (source, destination):" << endl;
for (int i = 0; i < e; i++) {
cin >> edges[i].first >> edges[i].second;
}
createGraph(v, edges);
cout << "Depth First Search starting from vertex 0:\n";
dfs(0);
cout << "\n";
cout << "Breadth First Search starting from vertex 0:\n";
bfs(0);
cout << "\n";
cout << "Converting to Adjacency List representation:\n";
convertToAdjList();
return 0;
}
```
这个程序首先创建了邻接矩阵表示的图,并实现了深度优先搜索和广度优先搜索。然后展示了如何将邻接矩阵转换为邻接表。注意,由于C++98的限制,这里使用的是循环数组而不是真正意义上的邻接表,但在理解原理上是一致的。
阅读全文