int main() { MGraph G; cin>>G.vexnum; GreatGraph(G); DFSGraph(G); cout<<endl; return 0; }
时间: 2024-06-07 11:11:13 浏览: 3
这是一个基于邻接矩阵存储的无向图的深度优先遍历算法的主函数。具体来说,程序通过读入图的顶点个数,然后调用GreatGraph函数构建无向图的邻接矩阵表示,接着调用DFSGraph函数对图进行深度优先遍历,并输出遍历结果。最后程序结束并返回0。
需要注意的是,这段代码中的MGraph、GreatGraph和DFSGraph都是自定义的函数或结构体,需要在其他地方定义和实现。
相关问题
本题要求建立一个无向图,采用邻接矩阵做为存储结构。 例如 image.png 函数接口定义: void CreatMGraph(MGraph &G);//创建图G int locate(MGraph G,char v);//返回顶点v的下标 G 为图,采用邻接矩阵存储结构,v 是顶点的值。
根据函数接口定义和题目要求,可以参考以下代码实现创建无向图并用邻接矩阵存储:
```c++
#include <iostream>
using namespace std;
#define MAX_VERTEX_NUM 100 // 最大节点数
// 邻接矩阵存储的图结构体
typedef struct {
char vexs[MAX_VERTEX_NUM]; // 顶点集合
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵,记录边信息
int vexnum, arcnum; // 图的顶点数和边数
} MGraph;
// 返回顶点 v 的下标,如果不存在返回 -1
int locate(MGraph G, char v)
{
for (int i = 0; i < G.vexnum; i++) {
if (G.vexs[i] == v) {
return i;
}
}
return -1;
}
// 创建无向图
void CreatMGraph(MGraph& 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] = 0; // 初始值为 0,表示没有边相连
}
}
cout << "请输入边信息:" << endl;
for (int k = 0; k < G.arcnum; k++) {
char v1, v2;
cout << "请输入第" << k + 1 << "条边的两个端点:" << endl;
cin >> v1 >> v2;
int i = locate(G, v1);
int j = locate(G, v2);
if (i == -1 || j == -1) {
cout << "输入的节点信息有误!" << endl;
return;
}
G.arcs[i][j] = 1; // 标记节点 i 和节点 j 相连
G.arcs[j][i] = 1; // 由于是无向图,节点 j 和节点 i 也相连
}
}
int main()
{
MGraph G;
CreatMGraph(G);
// 输出邻接矩阵
cout << "邻接矩阵为:" << endl;
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
cout << G.arcs[i][j] << ' ';
}
cout << endl;
}
return 0;
}
```
注意,在输入边信息时,需要先通过 `locate` 函数找到两个节点在邻接矩阵中的下标,然后将它们标记为相连。由于是无向图,需要同时标记节点 j 和节点 i 相连。
请编写代码,要求如下:建立图的邻接表,邻接矩阵 Create_Graph( LGraph lg. MGraph mg ) ②邻接表表示的图的递归深度优先遍历 LDFS( LGraph g, int i ) ③邻接矩阵表示的图的递归深度优先遍历MDFS( MGraph g,int i, int vn ) ④邻接表表示的图的广度优先遍历 LBFS( LGraph g, int s, int n ) ⑤邻接矩阵表示的图的广度优先遍历 MBFS(MGraph g, int s, int n )
以下是 C++ 代码实现:
```cpp
#include<iostream>
#include<queue>
using namespace std;
// 邻接表存储结构
#define MAX_VERTEX_NUM 100
typedef struct ArcNode {
int adjvex; // 该弧指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
//InfoType info; // 网的边权值
} ArcNode;
typedef struct VNode {
char data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum; // 图的当前顶点数和弧数
} LGraph;
// 邻接矩阵存储结构
#define INFINITY INT_MAX
typedef struct {
char vexs[MAX_VERTEX_NUM]; // 顶点向量
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵,可看作边表
int vexnum, arcnum; // 图的当前顶点数和弧数
} MGraph;
// 邻接表表示的图的递归深度优先遍历
void DFS(LGraph g, int i, int *visited) {
visited[i] = 1;
cout << g.vertices[i].data << " ";
ArcNode *p = g.vertices[i].firstarc;
while (p != NULL) {
if (visited[p->adjvex] == 0) {
DFS(g, p->adjvex, visited);
}
p = p->nextarc;
}
}
void LDFS(LGraph g, int i) {
int visited[MAX_VERTEX_NUM] = { 0 };
DFS(g, i, visited);
}
// 邻接矩阵表示的图的递归深度优先遍历
void MDFS(MGraph g, int i, int *visited) {
visited[i] = 1;
cout << g.vexs[i] << " ";
for (int j = 0; j < g.vexnum; j++) {
if (g.arcs[i][j] != 0 && visited[j] == 0) {
MDFS(g, j, visited);
}
}
}
void MDFS(MGraph g, int i) {
int visited[MAX_VERTEX_NUM] = { 0 };
MDFS(g, i, visited);
}
// 邻接表表示的图的广度优先遍历
void LBFS(LGraph g, int s) {
queue<int> q;
int visited[MAX_VERTEX_NUM] = { 0 };
visited[s] = 1;
cout << g.vertices[s].data << " ";
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
ArcNode *p = g.vertices[v].firstarc;
while (p != NULL) {
if (visited[p->adjvex] == 0) {
visited[p->adjvex] = 1;
cout << g.vertices[p->adjvex].data << " ";
q.push(p->adjvex);
}
p = p->nextarc;
}
}
}
// 邻接矩阵表示的图的广度优先遍历
void MBFS(MGraph g, int s) {
queue<int> q;
int visited[MAX_VERTEX_NUM] = { 0 };
visited[s] = 1;
cout << g.vexs[s] << " ";
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int j = 0; j < g.vexnum; j++) {
if (g.arcs[v][j] != 0 && visited[j] == 0) {
visited[j] = 1;
cout << g.vexs[j] << " ";
q.push(j);
}
}
}
}
// 建立图的邻接表
void Create_Graph(LGraph &g, MGraph &mg) {
// 邻接表
g.vexnum = mg.vexnum;
g.arcnum = mg.arcnum;
for (int i = 0; i < mg.vexnum; i++) {
g.vertices[i].data = mg.vexs[i];
g.vertices[i].firstarc = NULL;
}
for (int i = 0; i < mg.vexnum; i++) {
for (int j = 0; j < mg.vexnum; j++) {
if (mg.arcs[i][j] != 0) {
ArcNode *p = new ArcNode;
p->adjvex = j;
p->nextarc = g.vertices[i].firstarc;
g.vertices[i].firstarc = p;
}
}
}
// 邻接矩阵
for (int i = 0; i < mg.vexnum; i++) {
for (int j = 0; j < mg.vexnum; j++) {
if (mg.arcs[i][j] == INFINITY) {
mg.arcs[i][j] = 0;
}
}
}
}
int main() {
LGraph lg;
MGraph mg;
// 初始化邻接矩阵
mg.vexnum = 5;
mg.arcnum = 7;
for (int i = 0; i < mg.vexnum; i++) {
for (int j = 0; j < mg.vexnum; j++) {
mg.arcs[i][j] = INFINITY;
}
}
mg.vexs[0] = 'A';
mg.vexs[1] = 'B';
mg.vexs[2] = 'C';
mg.vexs[3] = 'D';
mg.vexs[4] = 'E';
mg.arcs[0][1] = 1;
mg.arcs[0][2] = 1;
mg.arcs[1][2] = 1;
mg.arcs[1][3] = 1;
mg.arcs[2][0] = 1;
mg.arcs[2][3] = 1;
mg.arcs[3][4] = 1;
// 建立邻接表
Create_Graph(lg, mg);
// 邻接表表示的图的递归深度优先遍历
LDFS(lg, 0);
cout << endl;
// 邻接矩阵表示的图的递归深度优先遍历
MDFS(mg, 0);
cout << endl;
// 邻接表表示的图的广度优先遍历
LBFS(lg, 0);
cout << endl;
// 邻接矩阵表示的图的广度优先遍历
MBFS(mg, 0);
cout << endl;
return 0;
}
```
注意:以上代码只是一种实现方法,不一定是最优的。在实际应用中,还需要考虑图的具体特征和需求,选择合适的存储结构和算法。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)