运用C语言,建立一个包含6个结点的无向图的邻接矩阵,实现插入、删除边的功能,并进行深度优先遍历和广度优先遍历。
时间: 2024-02-18 09:05:56 浏览: 79
好的,下面是一份C语言代码,实现了无向图的邻接矩阵表示、插入、删除边以及深度优先遍历和广度优先遍历的功能。这里假设图中共有6个结点,编号为0到5。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE
int graph[MAX_NODE][MAX_NODE];
int visited[MAX_NODE];
int queue[MAX_NODE];
int front = 0, rear = 0;
// 初始化图
void init_graph() {
int i, j;
for (i = ; i < MAX_NODE; i++) {
for (j = 0; j < MAX_NODE; j++) {
graph[i][j] = 0;
}
}
}
// 插入一条边
void insert_edge(int u, int v) {
graph[u][v] = 1;
graph[v][u] = 1;
}
// 删除一条边
void delete_edge(int u, int v) {
graph[u][v] = 0;
graph[v][u] = 0;
}
// 深度优先遍历
void dfs(int node) {
int i;
visited[node] = 1;
printf("%d ", node);
for (i = 0; i < MAX_NODE; i++) {
if (graph[node][i] && !visited[i]) {
dfs(i);
}
}
}
// 广度优先遍历
void bfs(int node) {
int i;
visited[node] = 1;
printf("%d ", node);
queue[rear++] = node;
while (front < rear) {
int cur = queue[front++];
for (i = 0; i < MAX_NODE; i++) {
if (graph[cur][i] && !visited[i]) {
visited[i] = 1;
printf("%d ", i);
queue[rear++] = i;
}
}
}
}
int main() {
init_graph();
insert_edge(0, 1);
insert_edge(0, 2);
insert_edge(1, 3);
insert_edge(1, 4);
insert_edge(2, 4);
insert_edge(3, 5);
insert_edge(4, 5);
printf("DFS: ");
dfs(0);
printf("\n");
// 重置visited数组,以便进行BFS
int i;
for (i = 0; i < MAX_NODE; i++) {
visited[i] = 0;
}
printf("BFS: ");
bfs(0);
printf("\n");
delete_edge(2, 4);
printf("After delete edge (2, 4):\n");
printf("DFS: ");
for (i = 0; i < MAX_NODE; i++) {
visited[i] = 0;
}
dfs(0);
printf("\n");
printf("BFS: ");
for (i = 0; i < MAX_NODE; i++) {
visited[i] = 0;
}
bfs(0);
printf("\n");
return 0;
}
```
上述代码中的init_graph函数初始化了邻接矩阵,insert_edge和delete_edge函数分别实现了插入和删除一条边的功能,dfs和bfs函数分别实现了深度优先遍历和广度优先遍历的功能。
在代码中,我们先插入了6条边,然后进行了一次深度优先遍历和广度优先遍历,输出了遍历结果。接着,我们删除了一条边,再次进行一次深度优先遍历和广度优先遍历,输出了更新后的遍历结果。
阅读全文