任选一个存储结构存储一个无向图,要求最少8个顶点,12个边,完成如下功能: 1.创建图。接收从键盘输入的边信息,存储到图中。 2.增加边的信息。 3.删除边的信息。 4.对图进行深度优先遍历。用c语言
时间: 2024-05-12 16:15:02 浏览: 39
以下是一个使用邻接表存储无向图,实现以上功能的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 10 // 最多顶点数
typedef struct ArcNode { // 边表结点
int adjvex; // 该边所指向的顶点的位置
struct ArcNode *next; // 指向下一条边的指针
} ArcNode;
typedef struct VNode { // 顶点表结点
char data; // 顶点数据
ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { // 图结构
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 创建图
void CreateGraph(ALGraph *G) {
printf("请输入顶点数和边数(以空格隔开):");
scanf("%d %d", &(G->vexnum), &(G->arcnum));
getchar(); // 把换行符从缓冲区中取出
printf("请输入每个顶点的值:");
for (int i = 0; i < G->vexnum; i++) {
scanf("%c", &(G->vertices[i].data));
G->vertices[i].firstarc = NULL;
getchar(); // 把换行符从缓冲区中取出
}
printf("请输入每条边的信息(起点 终点):\n");
for (int i = 0; i < G->arcnum; i++) {
int v1, v2;
scanf("%d %d", &v1, &v2);
getchar(); // 把换行符从缓冲区中取出
// 创建新的边表结点
ArcNode *newArcNode1 = (ArcNode *)malloc(sizeof(ArcNode));
newArcNode1->adjvex = v2;
newArcNode1->next = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = newArcNode1;
ArcNode *newArcNode2 = (ArcNode *)malloc(sizeof(ArcNode));
newArcNode2->adjvex = v1;
newArcNode2->next = G->vertices[v2].firstarc;
G->vertices[v2].firstarc = newArcNode2;
}
}
// 输出图
void PrintGraph(ALGraph G) {
printf("该无向图的邻接表为:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("%c -> ", G.vertices[i].data);
ArcNode *p = G.vertices[i].firstarc;
while (p != NULL) {
printf("%c -> ", G.vertices[p->adjvex].data);
p = p->next;
}
printf("NULL\n");
}
}
// 增加边的信息
void AddArc(ALGraph *G, int v1, int v2) {
// 创建新的边表结点
ArcNode *newArcNode1 = (ArcNode *)malloc(sizeof(ArcNode));
newArcNode1->adjvex = v2;
newArcNode1->next = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = newArcNode1;
ArcNode *newArcNode2 = (ArcNode *)malloc(sizeof(ArcNode));
newArcNode2->adjvex = v1;
newArcNode2->next = G->vertices[v2].firstarc;
G->vertices[v2].firstarc = newArcNode2;
G->arcnum++;
}
// 删除边的信息
void DeleteArc(ALGraph *G, int v1, int v2) {
// 找到v1的边表中指向v2的边,删除之
ArcNode *p = G->vertices[v1].firstarc;
ArcNode *pre = NULL;
while (p != NULL) {
if (p->adjvex == v2) {
if (pre == NULL) {
G->vertices[v1].firstarc = p->next;
} else {
pre->next = p->next;
}
free(p);
break;
}
pre = p;
p = p->next;
}
// 找到v2的边表中指向v1的边,删除之
p = G->vertices[v2].firstarc;
pre = NULL;
while (p != NULL) {
if (p->adjvex == v1) {
if (pre == NULL) {
G->vertices[v2].firstarc = p->next;
} else {
pre->next = p->next;
}
free(p);
break;
}
pre = p;
p = p->next;
}
G->arcnum--;
}
// 深度优先遍历
void DFS(ALGraph G, int v, int *visited) {
visited[v] = 1;
printf("%c ", G.vertices[v].data);
ArcNode *p = G.vertices[v].firstarc;
while (p != NULL) {
if (visited[p->adjvex] == 0) {
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
// 遍历图
void TraverseGraph(ALGraph G) {
printf("深度优先遍历结果为:");
int visited[MAX_VERTEX_NUM] = {0}; // 记录每个结点是否被访问过
for (int i = 0; i < G.vexnum; i++) {
if (visited[i] == 0) {
DFS(G, i, visited);
}
}
printf("\n");
}
int main() {
ALGraph G;
CreateGraph(&G);
PrintGraph(G);
printf("请输入要增加的边的信息(起点 终点):");
int v1, v2;
scanf("%d %d", &v1, &v2);
AddArc(&G, v1, v2);
PrintGraph(G);
printf("请输入要删除的边的信息(起点 终点):");
scanf("%d %d", &v1, &v2);
DeleteArc(&G, v1, v2);
PrintGraph(G);
TraverseGraph(G);
return 0;
}
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)