当前位置：首页 > article >正文

22智能图

article 2024/12/2 22:01:06

例题

根据下列顶点之间的关系，画出相应的图结构
A -> B, C, D
B -> A, C,
C -> A, D, E,
D -> B, E,
E -> C,

数据结构：使用邻接表表示图，每个顶点有一个链表来存储与它相邻的顶点。
功能：
创建图。
添加边。
打印邻接表。
执行广度优先搜索（BFS）。

#include <stdio.h>  // 包含标准输入输出库
#include <stdlib.h> // 包含标准库函数，如 malloc 和 free

// 定义链表节点结构体
typedef struct ListNode {
    int value;             // 节点的值
    struct ListNode* next; // 指向下一个节点的指针
} ListNode;

// 定义图的邻接表结构体
typedef struct {
    int vertex;       // 顶点编号
    ListNode* adjList; // 邻接链表的头指针
} AdjacencyList;

// 图结构体
typedef struct {
    int numVertices;      // 顶点数量
    AdjacencyList* adjLists; // 邻接表数组
} Graph;

// 创建链表节点的函数
ListNode* createListNode(int value) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); // 分配内存
    newNode->value = value;                                   // 初始化节点值
    newNode->next = NULL;                                     // 初始化指针
    return newNode;                                           // 返回新节点
}

// 创建图的函数
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph)); // 分配内存
    graph->numVertices = vertices;                // 初始化顶点数量

    graph->adjLists = (AdjacencyList*)malloc(vertices * sizeof(AdjacencyList)); // 分配邻接表数组内存

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i].vertex = i;          // 初始化顶点编号
        graph->adjLists[i].adjList = NULL;      // 初始化邻接链表为空
    }

    return graph;                               // 返回图结构
}

// 添加边的函数
void addEdge(Graph* graph, int src, int dest, int bidir) {
    // 添加从 src 到 dest 的边
    ListNode* newNode = createListNode(dest);   // 创建新节点
    newNode->next = graph->adjLists[src].adjList; // 将新节点插入到邻接链表头部
    graph->adjLists[src].adjList = newNode;

    if (bidir) {                                // 如果是双向图
        // 添加从 dest 到 src 的边
        newNode = createListNode(src);          // 创建新节点
        newNode->next = graph->adjLists[dest].adjList; // 将新节点插入到邻接链表头部
        graph->adjLists[dest].adjList = newNode;
    }
}

// 打印邻接表的函数
void printAdjList(Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        printf("%d -> ", graph->adjLists[i].vertex); // 打印顶点编号
        ListNode* temp = graph->adjLists[i].adjList; // 获取邻接链表头指针
        while (temp) {
            printf("%d, ", temp->value);             // 打印邻接节点值
            temp = temp->next;                       // 移动到下一个节点
        }
        printf("\n");                                // 换行
    }
}

// 广度优先搜索的函数
void bfs(Graph* graph, int src) {
    int* visited = (int*)calloc(graph->numVertices, sizeof(int)); // 分配访问标记数组内存
    int queue[graph->numVertices];                                // 定义队列
    int front = 0, rear = 0;                                      // 初始化队列的前后指针

    visited[src] = 1;                                             // 标记源节点已访问
    queue[rear++] = src;                                          // 将源节点入队

    while (front != rear) {                                       // 当队列不为空时
        int node = queue[front++];                                // 出队一个节点
        printf("%d, ", node);                                     // 打印节点值

        ListNode* temp = graph->adjLists[node].adjList;           // 获取当前节点的邻接链表头指针
        while (temp) {
            if (!visited[temp->value]) {                          // 如果邻接节点未被访问
                visited[temp->value] = 1;                         // 标记邻接节点已访问
                queue[rear++] = temp->value;                      // 将邻接节点入队
            }
            temp = temp->next;                                    // 移动到下一个邻接节点
        }
    }

    free(visited);                                                // 释放访问标记数组内存
}

int main() {
    int vertices = 6;                                             // 定义顶点数量
    Graph* graph = createGraph(vertices);                         // 创建图

    // 添加边
    addEdge(graph, 0, 1, 1);                                      // 添加边 (0, 1)
    addEdge(graph, 1, 2, 1);                                      // 添加边 (1, 2)
    addEdge(graph, 0, 4, 1);                                      // 添加边 (0, 4)
    addEdge(graph, 2, 4, 1);                                      // 添加边 (2, 4)
    addEdge(graph, 2, 3, 1);                                      // 添加边 (2, 3)
    addEdge(graph, 3, 5, 1);                                      // 添加边 (3, 5)
    addEdge(graph, 3, 4, 1);                                      // 添加边 (3, 4)

    printf("The Graph is:\n");                                    // 打印图的信息
    printAdjList(graph);                                          // 打印邻接表
    printf("\n");

    printf("The Breadth First Search from Node 0:\n");            // 打印广度优先搜索结果
    bfs(graph, 0);

    // 释放图的内存
    for (int i = 0; i < vertices; i++) {
        ListNode* temp = graph->adjLists[i].adjList;              // 获取邻接链表头指针
        while (temp) {
            ListNode* toFree = temp;                              // 保存当前节点
            temp = temp->next;                                    // 移动到下一个节点
            free(toFree);                                         // 释放当前节点内存
        }
    }
    free(graph->adjLists);                                        // 释放邻接表数组内存
    free(graph);                                                  // 释放图结构内存

    return 0;                                                     // 程序结束
}