#include "stdio.h"
#include "stdlib.h"
#include "queue.h"
/**
* 图的邻接表存储结构
* 这里区分两个概念：顶点、边节点。
* 在邻接表的存储方式中：顶点以数组方式存储，边节点以链表方式存储。
*/
#define MAX_VERTEX_NUM 20 // 最大顶点数
#define True 1
#define False 0
typedef int bool;
bool visited[MAX_VERTEX_NUM]; // 记录每个节点是否被访问过
// 定义边节点
typedef struct EdgeNode {
int adj_vertex; // 该边指向的顶点位置
int weight; // 该边上的权值
struct EdgeNode *next; // 指向下一条边的指针
} EdgeNode;
// 定义顶点
typedef struct {
char data; // 顶点数据
EdgeNode *first_edge; // 顶点指向的第一个边节点
} VertexNode;
// 定义整个图
typedef struct {
VertexNode *vertex_nodes[MAX_VERTEX_NUM]; // 顶点数组
int edge_num, vertex_num; // 边数量，顶点数量
} AdjListGraph;
/**
* 创建图（此过程可以直接跳过）
*/
typedef struct { // 邻接表中一个顶点及其边（即邻接表一行）数据
char vertex_data;
int index_list[10]; // 一行中所有边的adj_vertex值
int edge_num; // 一行中边个数
int weights[10]; // 一行中边对应的权值
} RowData;
VertexNode *generate_vertex_from_data(RowData *row_data) {
/**
* 从一行的数据中生成一个顶点
*/
// 生成边链表
EdgeNode *head = malloc(sizeof(EdgeNode)); // 创建头结点
head->next = NULL;
EdgeNode *last_node;
last_node = head;
for (int i = 0; i < row_data->edge_num; i++) {
// 创建一个新节点，并为它赋值
EdgeNode *new_node = malloc(sizeof(EdgeNode));
new_node->adj_vertex = row_data->index_list[i];
new_node->weight = row_data->weights[i];
new_node->next = NULL;
// 将新节点添加到链表尾
last_node->next = new_node;
// 更新last_node
last_node = new_node;
}
// 生成顶点
VertexNode *vertex_node = malloc(sizeof(VertexNode));
vertex_node->data = row_data->vertex_data;
vertex_node->first_edge = head->next;
// 返回
return vertex_node;
}
AdjListGraph *create_graph(AdjListGraph *graph) {
/**
* 创建邻接表存储的图
*/
// 初始化 边数量，顶点数量
graph->edge_num = 7;
graph->vertex_num = 5;
// 初始化邻接表每一行数据
RowData *row_data1 = malloc(sizeof(RowData));
row_data1->edge_num = 2;
row_data1->vertex_data = '1';
row_data1->index_list[0] = 2;
row_data1->index_list[1] = 5;
row_data1->weights[0] = 1;
row_data1->weights[1] = 1;
RowData *row_data2 = malloc(sizeof(RowData));
row_data2->edge_num = 4;
row_data2->vertex_data = '2';
row_data2->index_list[0] = 1;
row_data2->index_list[1] = 5;
row_data2->index_list[2] = 3;
row_data2->index_list[3] = 4;
row_data2->weights[0] = 1;
row_data2->weights[1] = 1;
row_data2->weights[2] = 1;
row_data2->weights[3] = 1;
RowData *row_data3 = malloc(sizeof(RowData));
row_data3->edge_num = 2;
row_data3->vertex_data = '3';
row_data3->index_list[0] = 2;
row_data3->index_list[1] = 4;
row_data3->weights[0] = 1;
row_data3->weights[1] = 1;
RowData *row_data4 = malloc(sizeof(RowData));
row_data4->edge_num = 3;
row_data4->vertex_data = '4';
row_data4->index_list[0] = 2;
row_data4->index_list[1] = 5;
row_data4->index_list[2] = 3;
row_data4->weights[0] = 1;
row_data4->weights[2] = 1;
row_data4->weights[3] = 1;
RowData *row_data5 = malloc(sizeof(RowData));
row_data5->edge_num = 3;
row_data5->vertex_data = '5';
row_data5->index_list[0] = 4;
row_data5->index_list[1] = 1;
row_data5->index_list[2] = 2;
row_data5->weights[0] = 1;
row_data5->weights[1] = 1;
row_data5->weights[2] = 1;
// 从数据生成5个顶点
VertexNode *vertex1 = generate_vertex_from_data(row_data1);
VertexNode *vertex2 = generate_vertex_from_data(row_data2);
VertexNode *vertex3 = generate_vertex_from_data(row_data3);
VertexNode *vertex4 = generate_vertex_from_data(row_data4);
VertexNode *vertex5 = generate_vertex_from_data(row_data5);
// 将5个顶点添加到图
graph->vertex_nodes[1] = vertex1;
graph->vertex_nodes[2] = vertex2;
graph->vertex_nodes[3] = vertex3;
graph->vertex_nodes[4] = vertex4;
graph->vertex_nodes[5] = vertex5;
// 返回
return graph;
}
/**
* （邻接表）广度优先遍历图
* （BFS需要设置一个队列，队列存放访问过的顶点位置）
*/
void BFSTraverse(AdjListGraph *graph) {
/**
* 对整个图进行BFS遍历
* （整个图可能是非连通的，即包含多个连通子图）
*/
// 初始化标志数组
for (int i = 0; i <= graph->vertex_num; ++i) {
visited[i] = False;
}
// 定义队列，并初始化
Queue *queue = malloc(sizeof(Queue));
init_queue(queue);
// 以每个顶点为起点，遍历图
for (int j = 1; j <= graph->vertex_num; ++j) {
if (!visited[j]) {
VertexNode *vertex = graph->vertex_nodes[j]; // 获得当前节点
visited[j] = True; // 设置标志
printf("%c ", vertex->data); // 打印顶点
enqueue(queue, j); // 入队
// 寻找未访问过的节点
while (!queue_empty(queue)) {
int k = dequeue(queue); // 出队，k表示当前顶点位置
EdgeNode *head = graph->vertex_nodes[k]->first_edge; // 获得当前顶点的边节点链表头指针
EdgeNode *cur_edge = head; // 当前边节点
while (cur_edge) {
if (!visited[cur_edge->adj_vertex]) {
printf("%c ", graph->vertex_nodes[cur_edge->adj_vertex]->data); // 访问
visited[cur_edge->adj_vertex] = True;
enqueue(queue, cur_edge->adj_vertex);
}
cur_edge = cur_edge->next;
}
}
}
}
}
/**
* （邻接表）深度优先遍历图
*/
void DFS(AdjListGraph *graph, int i) {
/**
* 从邻接表表示的图中第i个节点开始，深度优先遍历图
* （这个函数只能完全遍历一个连通图）
*/
if (graph != NULL) {
// 标志位置1，表示访问过
visited[i] = True;
// 取出当前顶点
VertexNode *cur_vertex = graph->vertex_nodes[i];
printf("%c ", cur_vertex->data); // 输出当前节点数值
EdgeNode *head = cur_vertex->first_edge; // 获得当前顶点的边节点链表头指针
// 寻找未访问过的节点，如果找到，递归下去
EdgeNode *cur_edge = head;
while (cur_edge) {
if (!visited[cur_edge->adj_vertex]) { // 如果没有被访问过
DFS(graph, cur_edge->adj_vertex);
}
cur_edge = cur_edge->next;
}
}
}
void DFSTraverse(AdjListGraph *graph) {
/**
* 对整个图进行遍历
* （整个图可能是非连通的，即包含多个连通子图）
*/
// 初始化标志数组
for (int i = 1; i <= graph->vertex_num; ++i) {
visited[i] = False;
}
// 以每个顶点为起点，遍历图
for (int j = 1; j <= graph->vertex_num; ++j) {
if (!visited[j]) {
DFS(graph, j);
}
}
}
/**
* 主函数测试
*/
int main() {
AdjListGraph *graph = malloc(sizeof(AdjListGraph));
// 创建图
graph = create_graph(graph);
// BFS
printf("广度优先遍历结果：");
BFSTraverse(graph);
// DFS
printf("\n深度优先遍历结果：");
DFSTraverse(graph);
}
