引自免费微信小程序：皆我百晓生
为了帮助您解决这些问题，我会提供C语言代码示例以及对每个部分的解释。首先，我们定义一个表示图节点的结构体Node，一个表示边的结构体Edge，以及一个表示邻接表的结构体AdjacencyList。
#include
#include
#include
typedef struct Node {
char name[20];
int visited; // 用于DFS和BFS标记
} Node;
typedef struct Edge {
char source[20];
char destination[20];
} Edge;
typedef struct AdjacencyList {
char vertex[20];
struct Edge* edges;
int num_edges;
} AdjacencyList;
// 函数声明
void add_vertex(Node** nodes, int* num_nodes, char* vertex_name);
void add_edge(Node** nodes, AdjacencyList** adj_list, int num_nodes, char* source, char* destination);
void delete_vertex(Node** nodes, AdjacencyList** adj_list, int* num_nodes, char* vertex_name);
void delete_edge(Node** nodes, AdjacencyList** adj_list, int num_nodes, char* source, char* destination);
void print_adj_list(AdjacencyList* adj_list, int num_vertices);
void dfs(Node* nodes, AdjacencyList* adj_list, int num_vertices, char* start_vertex);
void bfs(Node* nodes, AdjacencyList* adj_list, int num_vertices, char* start_vertex);
int main() {
// 初始化数据
Node* nodes = NULL;
AdjacencyList* adj_list = NULL;
int num_nodes = 0;
// 从文件读取数据并构建图
read_graph_from_file(&nodes, &num_nodes, &adj_list, "g.txt");
// 输出邻接表
printf("Original adjacency list:\n");
print_adj_list(adj_list, num_nodes);
// 图的操作：添加和删除顶点和边
// 示例：添加顶点 "I"，边 "I->J"
add_vertex(&nodes, &num_nodes, "I");
add_edge(&nodes, &adj_list, num_nodes, "I", "J");
// 将修改后的图保存到文件
save_graph_to_file(nodes, num_nodes, adj_list, "g.txt");
// 深度优先遍历
printf("\nDepth First Search (DFS) from vertex 'A':\n");
dfs(nodes, adj_list, num_nodes, "A");
// 广度优先遍历
printf("\nBreath First Search (BFS) from vertex 'A':\n");
bfs(nodes, adj_list, num_nodes, "A");
// 清理内存
free_graph(&nodes, &adj_list, &num_nodes);
return 0;
}
// 其他函数实现...
由于篇幅限制，这里只展示了主要的框架和函数声明。下面是这些函数的实现：
- 添加顶点
void add_vertex(Node** nodes, int* num_nodes, char* vertex_name) {
Node* new_node = (Node*)malloc(sizeof(Node));
strcpy(new_node->name, vertex_name);
new_node->visited = 0;
*nodes = (Node*)realloc(*nodes, (*num_nodes + 1) * sizeof(Node));
(*nodes)[(*num_nodes)] = *new_node;
(*num_nodes)++;
}
- 添加边
void add_edge(Node** nodes, AdjacencyList** adj_list, int num_nodes, char* source, char* destination) {
for (int i = 0; i < num_nodes; i++) {
if (!strcmp((*nodes)[i].name, source)) {
break;
}
}
if (i == num_nodes) {
printf("Error: Source vertex '%s' not found.\n", source);
return;
}
Edge* new_edge = (Edge*)malloc(sizeof(Edge));
strcpy(new_edge->source, source);
strcpy(new_edge->destination, destination);
(*adj_list)[i].edges = (Edge*)realloc((*adj_list)[i].edges, ((*adj_list)[i].num_edges + 1) * sizeof(Edge));
(*adj_list)[i].edges[(*adj_list)[i].num_edges] = *new_edge;
(*adj_list)[i].num_edges++;
}
- 删除顶点
void delete_vertex(Node** nodes, AdjacencyList** adj_list, int* num_nodes, char* vertex_name) {
for (int i = 0; i < *num_nodes; i++) {
if (!strcmp((*nodes)[i].name, vertex_name)) {
for (int j = i; j < *num_nodes - 1; j++) {
(*nodes)[j] = (*nodes)[j + 1];
}
*num_nodes--;
for (int k = 0; k < *num_nodes; k++) {
(*adj_list)[k].edges = remove_vertex_from_adj_list((*adj_list)[k].edges, (*adj_list)[k].num_edges, vertex_name);
(*adj_list)[k].num_edges = count_edges_in_adj_list((*adj_list)[k].edges, (*adj_list)[k].num_edges);
}
break;
}
}
}
- 删除边
void delete_edge(Node** nodes, AdjacencyList** adj_list, int num_nodes, char* source, char* destination) {
for (int i = 0; i < num_nodes; i++) {
if (!strcmp((*nodes)[i].name, source)) {
for (int j = 0; j < (*adj_list)[i].num_edges; j++) {
if (!strcmp((*adj_list)[i].edges[j].destination, destination)) {
for (int k = j; k < (*adj_list)[i].num_edges - 1; k++) {
(*adj_list)[i].edges[k] = (*adj_list)[i].edges[k + 1];
}
(*adj_list)[i].num_edges--;
break;
}
}
break;
}
}
}
- 打印邻接表
void print_adj_list(AdjacencyList* adj_list, int num_vertices) {
for (int i = 0; i < num_vertices; i++) {
printf("%s -> ", adj_list[i].vertex);
for (int j = 0; j < adj_list[i].num_edges; j++) {
printf("(%s, %s), ", adj_list[i].edges[j].source, adj_list[i].edges[j].destination);
}
printf("\n");
}
}
- 深度优先遍历
void dfs(Node* nodes, AdjacencyList* adj_list, int num_vertices, char* start_vertex) {
dfs_helper(nodes, adj_list, num_vertices, start_vertex, start_vertex, 0);
}
void dfs_helper(Node* nodes, AdjacencyList* adj_list, int num_vertices, char* current, char* parent, int depth) {
printf("%s (%d)\n", current, depth);
(*nodes)[find_index(nodes, num_vertices, current)].visited = 1;
for (int i = 0; i < adj_list[find_index(nodes, num_vertices, current)].num_edges; i++) {
if (!strcmp(adj_list[find_index(nodes, num_vertices, current)].edges[i].destination, parent)) continue;
if (!(*nodes)[find_index(nodes, num_vertices, adj_list[find_index(nodes, num_vertices, current)].edges[i].destination)].visited) {
dfs_helper(nodes, adj_list, num_vertices, adj_list[find_index(nodes, num_vertices, current)].edges[i].destination, current, depth + 1);
}
}
}
- 广度优先遍历
void bfs(Node* nodes, AdjacencyList* adj_list, int num_vertices, char* start_vertex) {
queue_char q;
init_queue(&q);
enqueue(&q, start_vertex);
while (!queue_empty(&q)) {
char* current = dequeue(&q);
printf("%s\n", current);
(*nodes)[find_index(nodes, num_vertices, current)].visited = 1;
for (int i = 0; i < adj_list[find_index(nodes, num_vertices, current)].num_edges; i++) {
if (!(*nodes)[find_index(nodes, num_vertices, adj_list[find_index(nodes, num_vertices, current)].edges[i].destination)].visited) {
enqueue(&q, adj_list[find_index(nodes, num_vertices, current)].edges[i].destination);
}
}
}
}
- 辅助函数（队列操作）
typedef struct QueueChar {
char* elements[100];
int front, rear;
} QueueChar;
void init_queue(QueueChar* q) {
q->front = q->rear = -1;
}
int is_queue_empty(QueueChar* q) {
return q->front == q->rear;
}
void enqueue(QueueChar* q, char* data) {
if (q->rear == 99) {
