用c语言先构建一个有向图,再实现深度优先遍阅和广度优先遍阅。
时间: 2024-02-26 21:58:22 浏览: 20
好的,下面是使用C语言实现有向图的示例代码,并实现深度优先遍历和广度优先遍历的方法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct {
int vertex;
struct Node* next;
} Node;
typedef struct {
Node* head;
} List;
typedef struct {
List* adj_list[MAX_VERTICES];
int num_vertices;
} Graph;
Node* create_node(int v) {
Node* node = (Node*) malloc(sizeof(Node));
node->vertex = v;
node->next = NULL;
return node;
}
Graph* create_graph(int num_vertices) {
Graph* graph = (Graph*) malloc(sizeof(Graph));
graph->num_vertices = num_vertices;
for (int i = 0; i < num_vertices; i++) {
graph->adj_list[i] = (List*) malloc(sizeof(List));
graph->adj_list[i]->head = NULL;
}
return graph;
}
void add_edge(Graph* graph, int u, int v) {
Node* node = create_node(v);
node->next = graph->adj_list[u]->head;
graph->adj_list[u]->head = node;
}
void dfs(Graph* graph, int start, int* visited) {
visited[start] = 1;
printf("%d ", start);
Node* node = graph->adj_list[start]->head;
while (node != NULL) {
int connected_vertex = node->vertex;
if (!visited[connected_vertex]) {
dfs(graph, connected_vertex, visited);
}
node = node->next;
}
}
void bfs(Graph* graph, int start, int* visited) {
int queue[MAX_VERTICES];
int front = 0, rear = 0;
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int vertex = queue[front++];
printf("%d ", vertex);
Node* node = graph->adj_list[vertex]->head;
while (node != NULL) {
int connected_vertex = node->vertex;
if (!visited[connected_vertex]) {
visited[connected_vertex] = 1;
queue[rear++] = connected_vertex;
}
node = node->next;
}
}
}
int main() {
int num_vertices = 6;
Graph* graph = create_graph(num_vertices);
add_edge(graph, 0, 1);
add_edge(graph, 0, 2);
add_edge(graph, 1, 3);
add_edge(graph, 2, 4);
add_edge(graph, 3, 5);
add_edge(graph, 4, 5);
int visited[MAX_VERTICES] = {0};
printf("DFS: ");
dfs(graph, 0, visited);
printf("\nBFS: ");
bfs(graph, 0, visited);
return 0;
}
```
在上面的代码中,我们首先定义了一个Node结构体和一个List结构体来表示有向图中的节点和邻接表。然后,我们定义了一个Graph结构体来表示整个有向图,并实现了创建有向图、添加边、深度优先遍历和广度优先遍历的函数。
在主函数中,我们创建了一个有向图,并添加了一些边。然后,我们使用深度优先遍历和广度优先遍历方法来遍历这个有向图。
希望我的回答能够帮助你!
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.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)
![](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)