先依次输入有向图的顶点信息,再依次输入有向图的弧信息,建立图的邻接表存储结构并将其打印输出 ,然后在建立的有向图的邻接表存储结构基础上使用非递归算法对图进行深度优先搜索遍历并输出顶点序列,最后在建立的有向图的邻接表存储结构基础上对图进行广度优先搜索遍历并输出顶点序列。用C语言实现且运行界面用汉语
时间: 2024-02-09 20:11:14 浏览: 59
C语言 输入无向图连通图的顶点数、顶点信息、边数、顶点对序列及遍历的起始点序号,输出深度优先遍历序列
5星 · 资源好评率100%
好的,下面是使用汉语输出的C语言代码,实现了您所需的功能:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义邻接表结点
typedef struct Node {
int index; // 结点编号
struct Node *next; // 指向下一个邻接点
} Node;
// 定义邻接表
typedef struct Graph {
int vertex_num; // 结点数目
Node **adj_list; // 指向每个结点的邻接链表头指针的数组
} Graph;
// 初始化邻接表
Graph* init_graph(int vertex_num) {
Graph *graph = (Graph*) malloc(sizeof(Graph));
graph->vertex_num = vertex_num;
graph->adj_list = (Node**) malloc(vertex_num * sizeof(Node*));
for (int i = 0; i < vertex_num; i++) {
graph->adj_list[i] = NULL;
}
return graph;
}
// 添加边
void add_edge(Graph *graph, int start, int end) {
// 在起始结点的邻接链表头插入终止结点
Node *new_node = (Node*) malloc(sizeof(Node));
new_node->index = end;
new_node->next = graph->adj_list[start];
graph->adj_list[start] = new_node;
}
// 打印邻接表
void print_graph(Graph *graph) {
for (int i = 0; i < graph->vertex_num; i++) {
printf("顶点 %d: ", i);
Node *cur_node = graph->adj_list[i];
while (cur_node != NULL) {
printf("%d ", cur_node->index);
cur_node = cur_node->next;
}
printf("\n");
}
}
// 非递归深度优先搜索
void dfs_iterative(Graph *graph, int start) {
// 创建栈
int *stack = (int*) malloc(graph->vertex_num * sizeof(int));
int top = -1;
int visited[graph->vertex_num];
for (int i = 0; i < graph->vertex_num; i++) {
visited[i] = 0;
}
// 将起始结点入栈并标记已访问
stack[++top] = start;
visited[start] = 1;
//
阅读全文