用C语言写一个用顶点信息输入有向图并遍历的程序,要求能实现两种遍历方式
时间: 2024-03-26 21:40:20 浏览: 22
好的,我来为您编写一个用C语言实现有向图遍历的程序。首先,我们需要定义一个结构体来表示图的顶点:
```
typedef struct Vertex {
int id; // 顶点编号
int visited; // 是否被访问过
struct Edge* edges; // 与该顶点相连的边
} Vertex;
```
接着,我们需要定义一个结构体来表示图的边:
```
typedef struct Edge {
struct Vertex* dest; // 边的终点
struct Edge* next; // 下一条边
} Edge;
```
有了顶点和边的定义,我们就可以定义图了:
```
typedef struct Graph {
int numVertices; // 顶点数
struct Vertex* vertices; // 顶点数组
} Graph;
```
接下来就是实现遍历算法了。下面是用深度优先遍历和广度优先遍历分别遍历图的代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Vertex {
int id; // 顶点编号
int visited; // 是否被访问过
struct Edge* edges; // 与该顶点相连的边
} Vertex;
typedef struct Edge {
struct Vertex* dest; // 边的终点
struct Edge* next; // 下一条边
} Edge;
typedef struct Graph {
int numVertices; // 顶点数
struct Vertex* vertices; // 顶点数组
} Graph;
// 创建一个新的边
Edge* newEdge(Vertex* dest, Edge* next) {
Edge* edge = (Edge*)malloc(sizeof(Edge));
edge->dest = dest;
edge->next = next;
return edge;
}
// 创建一个新的顶点
Vertex* newVertex(int id) {
Vertex* vertex = (Vertex*)malloc(sizeof(Vertex));
vertex->id = id;
vertex->visited = false;
vertex->edges = NULL;
return vertex;
}
// 向图中添加一条边
void addEdge(Graph* graph, int src, int dest) {
Vertex* srcVertex = &(graph->vertices[src]);
srcVertex->edges = newEdge(&(graph->vertices[dest]), srcVertex->edges);
}
// 创建一个新的图
Graph* newGraph(int numVertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->numVertices = numVertices;
graph->vertices = (Vertex*)malloc(sizeof(Vertex) * numVertices);
for (int i = 0; i < numVertices; i++) {
graph->vertices[i] = *newVertex(i);
}
return graph;
}
// 深度优先遍历
void dfs(Vertex* vertex) {
vertex->visited = true;
printf("%d ", vertex->id);
Edge* edge = vertex->edges;
while (edge != NULL) {
if (!edge->dest->visited) {
dfs(edge->dest);
}
edge = edge->next;
}
}
// 广度优先遍历
void bfs(Vertex* vertex) {
int front = 0;
int rear = 0;
Vertex* queue[vertex->visited + 1];
queue[rear++] = vertex;
vertex->visited = true;
printf("%d ", vertex->id);
while (front != rear) {
Vertex* v = queue[front++];
Edge* edge = v->edges;
while (edge != NULL) {
if (!edge->dest->visited) {
edge->dest->visited = true;
printf("%d ", edge->dest->id);
queue[rear++] = edge->dest;
}
edge = edge->next;
}
}
}
int main() {
// 创建一个图
Graph* graph = newGraph(6);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 2, 4);
addEdge(graph, 3, 5);
addEdge(graph, 4, 5);
// 深度优先遍历
printf("深度优先遍历结果:");
for (int i = 0; i < graph->numVertices; i++) {
if (!graph->vertices[i].visited) {
dfs(&(graph->vertices[i]));
}
}
printf("\n");
// 广度优先遍历
for (int i = 0; i < graph->numVertices; i++) {
graph->vertices[i].visited = false;
}
printf("广度优先遍历结果:");
for (int i = 0; i < graph->numVertices; i++) {
if (!graph->vertices[i].visited) {
bfs(&(graph->vertices[i]));
}
}
printf("\n");
return 0;
}
```
该程序创建了一个包含6个顶点的图,并采用邻接表的方式存储边。程序实现了深度优先遍历和广度优先遍历两种遍历方式。在遍历之前需要将所有顶点的visited属性初始化为false。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.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)
![](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)
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)