#include <iostream> #include <queue> using namespace std; // 定义图的最大顶点数 #define MAX_VERTEX_NUM 100 // 图的邻接矩阵表示 typedef struct { int vertex[MAX_VERTEX_NUM]; // 顶点数组 int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vertexNum; // 顶点数量 int edgeNum; // 边数量 } GraphMatrix; // 初始化图 void initGraph(GraphMatrix& graph) { graph.vertexNum = 0; graph.edgeNum = 0; for (int i = 0; i < MAX_VERTEX_NUM; i++) { graph.vertex[i] = 0; for (int j = 0; j < MAX_VERTEX_NUM; j++) { graph.edges[i][j] = 0; } } } // 添加顶点 void addVertex(GraphMatrix& graph, int v) { if (graph.vertexNum < MAX_VERTEX_NUM) { graph.vertex[graph.vertexNum] = v; graph.vertexNum++; } } // 添加边 void addEdge(GraphMatrix& graph, int v1, int v2) { int i, j; for (i = 0; i < graph.vertexNum; i++) { if (graph.vertex[i] == v1) break; } for (j = 0; j < graph.vertexNum; j++) { if (graph.vertex[j] == v2) break; } if (i < graph.vertexNum && j < graph.vertexNum) { graph.edges[i][j] = 1; graph.edges[j][i] = 1; graph.edgeNum++; } } // 销毁图 void destroyGraph(GraphMatrix& graph) { graph.vertexNum = 0; graph.edgeNum = 0; } // 深度优先遍历 void depthFirstSearch(GraphMatrix& graph, int v, bool visited[]) { visited[v] = true; cout << graph.vertex[v] << " "; for (int i = 0; i < graph.vertexNum; i++) { if (graph.edges[v][i] == 1 && !visited[i]) { depthFirstSearch(graph, i, visited); } } } // 深度优先遍历图 void DFS(GraphMatrix& graph) { bool visited[MAX_VERTEX_NUM]; for (int i = 0; i < graph.vertexNum; i++) { visited[i] = false; } for (int i = 0; i < graph.vertexNum; i++) { if (!visited[i]) { depthFirstSearch(graph, i, visited); } } cout << endl; } // 广度优先遍历图 void BFS(GraphMatrix& graph) { bool vis这段代码的不足
时间: 2024-02-15 20:24:58 浏览: 35
这段代码的不足可能有以下几点:
1. 缺少输入检查:在添加顶点和添加边的函数中,没有检查输入的参数是否合法,比如顶点数量是否已经达到最大值,或者添加的边是否已经存在。
2. 图的存储方式不够灵活:这里使用邻接矩阵来表示图,虽然在一些场景下比较方便,但是对于稀疏图来说,会浪费大量的空间。因此,可以考虑使用邻接表等其他存储方式。
3. 没有考虑多个连通分量的情况:在深度优先遍历和广度优先遍历的函数中,只考虑了单个连通分量的情况。如果图由多个连通分量组成,就只能遍历其中一个连通分量。
4. 代码可读性不够好:代码中缺少注释,函数命名不够规范,导致代码可读性不够好,不利于后期维护和修改。
相关问题
用C++代码实现:理解并实现无向图邻接矩阵的创建,理解并实现无向图邻接矩阵方式存储的广度优先遍历的算法,转换成程序并上机实现; //用两个数组分别存储顶点表和邻接矩阵 #define MaxInt 32767 //表示极大值,即∞ #define MVNum 100 //最大顶点数 typedef char VerTexType; //假设顶点的数据类型为字符型 typedef int ArcType; //假设边的权值类型为整型 typedef struct{ VerTexType vexs[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前点数和边数 }AMGraph;
以下是C++代码实现:
```cpp
#include <iostream>
#include <queue>
using namespace std;
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
typedef struct{
VerTexType vexs[MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum, arcnum;
}AMGraph;
void CreateUDN(AMGraph &G) {
cout << "请输入顶点数和边数:" << endl;
cin >> G.vexnum >> G.arcnum;
cout << "请输入顶点信息:" << endl;
for(int i = 0; i < G.vexnum; i++) {
cin >> G.vexs[i];
}
for(int i = 0; i < G.vexnum; i++) {
for(int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = MaxInt;
}
}
cout << "请输入边的信息:" << endl;
for(int k = 0; k < G.arcnum; k++) {
int i, j, w;
cin >> i >> j >> w;
G.arcs[i][j] = w;
G.arcs[j][i] = w;
}
}
void BFS(AMGraph G, int v, bool visited[]) {
queue<int> q;
cout << G.vexs[v] << " ";
visited[v] = true;
q.push(v);
while(!q.empty()) {
int w = q.front();
q.pop();
for(int i = 0; i < G.vexnum; i++) {
if(G.arcs[w][i] != MaxInt && !visited[i]) {
cout << G.vexs[i] << " ";
visited[i] = true;
q.push(i);
}
}
}
}
void BFSTraverse(AMGraph G) {
bool visited[MVNum] = {false};
for(int i = 0; i < G.vexnum; i++) {
if(!visited[i]) {
BFS(G, i, visited);
}
}
}
int main() {
AMGraph G;
CreateUDN(G);
cout << "广度优先遍历结果:" << endl;
BFSTraverse(G);
return 0;
}
```
在这段代码中,我们使用了一个邻接矩阵来存储无向图,包括顶点表和邻接矩阵两个数组。函数 `CreateUDN` 可以创建一个无向图,并且使用了一个二维数组 `arcs` 来存储边的权值。
函数 `BFS` 实现了广度优先遍历算法,使用了一个队列来存储需要遍历的顶点。函数 `BFSTraverse` 则是对整个图进行了广度优先遍历。
在 `main` 函数中,我们先创建了一个无向图,然后调用 `BFSTraverse` 函数进行广度优先遍历,并输出结果。
帮我用c++语言完善下列函数,void BFSTraverse(MGraph G,int v) { //广度优先遍历 }
好的,以下是完善后的代码:
```c++
#include <iostream>
#include <queue>
#define MAX_VERTEX_NUM 100
using namespace std;
typedef struct {
// 存放顶点信息的结构体
} VertexType;
typedef struct {
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum, arcnum;
VertexType vexs[MAX_VERTEX_NUM];
} MGraph;
bool visited[MAX_VERTEX_NUM];
void BFSTraverse(MGraph G, int v) {
queue<int> Q;
cout << v << " ";
visited[v] = true;
Q.push(v);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i = 0; i < G.vexnum; i++) {
if (G.edges[u][i] == 1 && !visited[i]) {
cout << i << " ";
visited[i] = true;
Q.push(i);
}
}
}
}
int main() {
MGraph G;
// 初始化G
BFSTraverse(G, 0);
return 0;
}
```
这段代码实现了广度优先遍历,从顶点v开始遍历。其中,MGraph结构体存储了图的信息,visited数组用于标记顶点是否被访问过。在BFSTraverse函数中,我们用队列来存储待访问的顶点,每次访问一个顶点后,将其未访问的邻居顶点加入队列中,直到队列为空。