运用C语言,建立一个包含6个结点的无向图的邻接矩阵,实现插入、删除边的功能,并进行深度优先遍历和广度优先遍历。
时间: 2024-02-18 09:06:28 浏览: 80
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
5星 · 资源好评率100%
好的,我可以帮你实现这个功能。首先,我们定义一个包含6个结点的无向图的邻接矩阵,如下所示:
```c
#define MAX_VERTEX_NUM 6 // 最大顶点数
#define INF 65535 // 表示无穷大
int graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM] = {
{0, 6, 1, 5, INF, INF},
{6, 0, 5, INF, 3, INF},
{1, 5, 0, 5, 6, 4},
{5, INF, 5, 0, INF, 2},
{INF, 3, 6, INF, 0, 6},
{INF, INF, 4, 2, 6, 0}
};
```
其中,`MAX_VERTEX_NUM` 表示最大顶点数,这里我们定义为6。`INF` 表示无穷大,即两个顶点之间不存在边。我们将邻接矩阵存储在一个二维数组 `graph` 中,`graph[i][j]` 表示顶点i和顶点j之间的边的权重,如果它们之间没有边,则 `graph[i][j]` 等于 `INF`。
接下来,我们需要实现插入边和删除边的功能。为了方便起见,这里我们将顶点编号从0开始。插入边的函数代码如下:
```c
void insert_edge(int u, int v, int w) {
graph[u][v] = w;
graph[v][u] = w;
}
```
其中,`u` 和 `v` 分别表示要插入的边的两个顶点,`w` 表示边的权重。这里的实现是无向图,所以我们需要将两个顶点之间的权重都设置为 `w`。
删除边的函数代码如下:
```c
void delete_edge(int u, int v) {
graph[u][v] = INF;
graph[v][u] = INF;
}
```
其中,`u` 和 `v` 分别表示要删除的边的两个顶点。这里的实现与插入边的函数类似,将两个顶点之间的权重都设置为 `INF`。
接下来,我们需要实现深度优先遍历和广度优先遍历的算法。深度优先遍历的函数代码如下:
```c
int visited[MAX_VERTEX_NUM]; // 标记数组,用于记录每个顶点是否被访问过
void dfs(int v) {
visited[v] = 1; // 标记顶点v已经被访问过
printf("%d ", v); // 输出顶点v的编号
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
if (graph[v][i] != INF && visited[i] == 0) {
dfs(i); // 递归访问顶点i
}
}
}
```
其中,`visited` 是一个标记数组,用于记录每个顶点是否被访问过。在遍历过程中,我们先标记当前顶点已经被访问过,然后输出它的编号。接着,我们遍历与当前顶点相邻的顶点,并递归访问它们。如果相邻的顶点已经被访问过,那么我们不再访问它。
广度优先遍历的函数代码如下:
```c
void bfs(int v) {
int queue[MAX_VERTEX_NUM]; // 队列,用于存储待访问的顶点
int front = 0, rear = 0; // 队列的头尾指针
visited[v] = 1; // 标记顶点v已经被访问过
printf("%d ", v); // 输出顶点v的编号
queue[rear++] = v; // 将顶点v加入队列
while (front != rear) { // 如果队列不为空
int u = queue[front++]; // 取出队列的头部元素
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
if (graph[u][i] != INF && visited[i] == 0) {
visited[i] = 1; // 标记顶点i已经被访问过
printf("%d ", i); // 输出顶点i的编号
queue[rear++] = i; // 将顶点i加入队列
}
}
}
}
```
其中,`queue` 是一个队列,用于存储待访问的顶点。我们首先将起始顶点加入队列中,并标记它已经被访问过。接着,我们不断从队列中取出头部元素,并遍历与它相邻的顶点。如果相邻的顶点还没有被访问过,那么我们将它加入队列中,并标记它已经被访问过。这样,我们就可以按照广度优先的顺序遍历整个图了。
完整的代码如下:
阅读全文