任选一个存储结构存储一个无向图,要求最少8个顶点,12个活动,完成如下功能: 1.创建图。接收从键盘输入的边信息,存储到图中。 2.增加边的信息。 3.删除边的信息。 4.对图进行深度优先遍历。 点击复制后,将打开C知道体验页
时间: 2024-05-05 12:22:56 浏览: 55
邻接表或者邻接矩阵为存储结构实现连通无向图的深度优先和广度优先遍历
3星 · 编辑精心推荐
很抱歉,我是一个语言模型,无法打开C知道体验页。这里提供一个基于邻接矩阵的无向图存储结构,并给出相应代码实现。
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTEX_NUM 20
// 定义邻接矩阵存储结构
typedef struct {
char vexs[MAX_VERTEX_NUM]; // 存储顶点信息
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边信息
int vexnum, arcnum; // 存储图的顶点数和边数
} Graph;
// 初始化图
void InitGraph(Graph* G) {
int i, j;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vexs[i] = '\0';
for (j = 0; j < MAX_VERTEX_NUM; j++) {
G->arcs[i][j] = 0;
}
}
}
// 查找顶点 v 在图 G 中的位置,找不到返回 -1
int LocateVex(Graph* G, char v) {
int i;
for (i = 0; i < G->vexnum; i++) {
if (G->vexs[i] == v) {
return i;
}
}
return -1;
}
// 创建无向图
void CreateUDG(Graph* G) {
int i, j, k;
char v1, v2;
printf("请输入图的顶点数和边数(用空格隔开):");
scanf("%d %d", &(G->vexnum), &(G->arcnum));
printf("请输入图的顶点信息(每个顶点一行):\n");
for (i = 0; i < G->vexnum; i++) {
scanf(" %c", &(G->vexs[i]));
}
printf("请输入每条边依附的两个顶点(用空格隔开):\n");
for (k = 0; k < G->arcnum; k++) {
scanf(" %c %c", &v1, &v2);
i = LocateVex(G, v1);
j = LocateVex(G, v2);
G->arcs[i][j] = G->arcs[j][i] = 1; // 无向图的邻接矩阵是对称矩阵,因此需要同时修改两个位置
}
}
// 增加边的信息
void AddArc(Graph* G) {
int i, j;
char v1, v2;
printf("请输入需要增加的边依附的两个顶点(用空格隔开):");
scanf(" %c %c", &v1, &v2);
i = LocateVex(G, v1);
j = LocateVex(G, v2);
if (i < 0 || j < 0) {
printf("输入的顶点信息有误!\n");
return;
}
if (G->arcs[i][j] == 1) {
printf("该边已经存在!\n");
} else {
G->arcs[i][j] = G->arcs[j][i] = 1;
G->arcnum++;
printf("边增加成功!\n");
}
}
// 删除边的信息
void DeleteArc(Graph* G) {
int i, j;
char v1, v2;
printf("请输入需要删除的边依附的两个顶点(用空格隔开):");
scanf(" %c %c", &v1, &v2);
i = LocateVex(G, v1);
j = LocateVex(G, v2);
if (i < 0 || j < 0) {
printf("输入的顶点信息有误!\n");
return;
}
if (G->arcs[i][j] == 0) {
printf("该边不存在!\n");
} else {
G->arcs[i][j] = G->arcs[j][i] = 0;
G->arcnum--;
printf("边删除成功!\n");
}
}
// 深度优先遍历
void DFS(Graph* G, int v, bool* visited) {
int i;
visited[v] = true;
printf("%c ", G->vexs[v]);
for (i = 0; i < G->vexnum; i++) {
if (G->arcs[v][i] == 1 && !visited[i]) {
DFS(G, i, visited);
}
}
}
// 对图进行深度优先遍历
void DFSTraverse(Graph* G) {
int i;
bool visited[MAX_VERTEX_NUM] = { false };
printf("深度优先遍历结果:");
for (i = 0; i < G->vexnum; i++) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
printf("\n");
}
int main() {
Graph G;
int choice;
InitGraph(&G);
CreateUDG(&G);
printf("无向图创建成功!\n");
while (true) {
printf("\n1.增加边的信息\n");
printf("2.删除边的信息\n");
printf("3.深度优先遍历\n");
printf("0.退出程序\n");
printf("请输入你的选择:");
scanf("%d", &choice);
switch (choice) {
case 1:
AddArc(&G);
break;
case 2:
DeleteArc(&G);
break;
case 3:
DFSTraverse(&G);
break;
case 0:
printf("程序已退出!\n");
return 0;
default:
printf("无效的选择!\n");
break;
}
}
return 0;
}
```
上述代码中,我们定义了邻接矩阵存储结构,并实现了创建无向图、增加边、删除边、深度优先遍历等功能。其中,深度优先遍历采用递归算法实现。
阅读全文