用c语言编写一个图程序,要求如下: (1)输入任意一张图(以邻接矩阵的方式存储); (2)对存储好的图从任意点出发进行深度、广度遍历; (3)上述对同一张图的遍历可多次进行(可从不同点出发进行)
时间: 2024-01-02 20:05:14 浏览: 84
建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历.doc
5星 · 资源好评率100%
好的,我会为您解答。
首先,您需要输入一张图,并以邻接矩阵的方式存储。可以使用二维数组来表示邻接矩阵。假设您的图有n个顶点,则可以定义一个n*n的二维数组,其中第i行第j列的元素表示从顶点i到顶点j是否有边相连。
接下来,您可以使用深度优先遍历或广度优先遍历来遍历存储好的图。下面是深度优先遍历和广度优先遍历的伪代码:
深度优先遍历:
1. 从某个顶点开始遍历,将该顶点标记为已访问;
2. 对于该顶点的每个未访问过的邻居,按照任意顺序递归地调用深度优先遍历函数;
广度优先遍历:
1. 从某个顶点开始遍历,将该顶点标记为已访问并加入队列;
2. 循环执行以下步骤,直到队列为空:
2.1 取出队列头部的顶点;
2.2 对于该顶点的每个未访问过的邻居,将其标记为已访问并加入队列。
最后,您可以多次进行对同一张图的遍历,可以从不同的点出发进行。
下面是一个使用C语言实现的例子代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTICES 100
// 邻接矩阵表示的图
typedef struct Graph {
int matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int num_vertices; // 顶点数
} Graph;
// 初始化图
void init_graph(Graph *graph, int num_vertices) {
graph->num_vertices = num_vertices;
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
graph->matrix[i][j] = 0;
}
}
}
// 添加边
void add_edge(Graph *graph, int i, int j) {
graph->matrix[i][j] = 1;
graph->matrix[j][i] = 1;
}
// 深度优先遍历
void depth_first_search(Graph *graph, int v, bool visited[]) {
visited[v] = true;
printf("%d ", v);
for (int i = 0; i < graph->num_vertices; i++) {
if (graph->matrix[v][i] && !visited[i]) {
depth_first_search(graph, i, visited);
}
}
}
// 广度优先遍历
void breadth_first_search(Graph *graph, int v, bool visited[]) {
int queue[MAX_VERTICES];
int front = 0;
int rear = 0;
visited[v] = true;
printf("%d ", v);
queue[rear++] = v;
while (front < rear) {
int u = queue[front++];
for (int i = 0; i < graph->num_vertices; i++) {
if (graph->matrix[u][i] && !visited[i]) {
visited[i] = true;
printf("%d ", i);
queue[rear++] = i;
}
}
}
}
int main() {
Graph graph;
init_graph(&graph, 6);
add_edge(&graph, 0, 1);
add_edge(&graph, 0, 2);
add_edge(&graph, 1, 3);
add_edge(&graph, 1, 4);
add_edge(&graph, 2, 4);
add_edge(&graph, 3, 5);
add_edge(&graph, 4, 5);
bool visited[MAX_VERTICES] = {false};
printf("深度优先遍历:\n");
for (int i = 0; i < graph.num_vertices; i++) {
if (!visited[i]) {
depth_first_search(&graph, i, visited);
}
}
printf("\n广度优先遍历:\n");
for (int i = 0; i < graph.num_vertices; i++) {
visited[i] = false;
}
for (int i = 0; i < graph.num_vertices; i++) {
if (!visited[i]) {
breadth_first_search(&graph, i, visited);
}
}
return 0;
}
```
这个例子中,我们定义了一个Graph结构体来表示邻接矩阵表示的图,使用init_graph函数初始化图,并使用add_edge函数添加边。使用depth_first_search函数和breadth_first_search函数来进行深度优先遍历和广度优先遍历。在main函数中,我们使用这些函数来遍历图,并输出遍历结果。
希望能帮到您!
阅读全文