【C 数据结构】 图（代码篇）

目录图的构建基本功能实现图的遍历方式graph_bfs 广度遍历graph_dfs 深度遍历图的表示方法邻接表邻接矩阵图的构建首先实现图的构建的要知道的就是节点构建和节点连接到下一个节点的地址并且链接到下一个地址是要有一个具有可的链接NULL和多个地址的的结构所以图的结构是有一个存在一个整形和一个地址我们在学习树的结构已经有抽象的理解过通过单链表实现树的结构理念其实在图的结构也不难看出我们也可以通过单链表来实现。图的实现理念图的结构有一个存入内容的结构和一个单链表来存入多个或者没有NULL的地址链表的内容可以存入的是指向对应图当前位置的下一个位置的地址和如果是加权图还可以加进去。代码展示typedef struct AdjListNode { int dest; /* 目标顶点的编号0 ~ V-1 */ struct AdjListNode* next; /* 指向下一个邻接点的指针尾节点为 NULL */ } AdjListNode; typedef struct AdjList { AdjListNode* head; /* 该顶点邻接链表的头指针无边时为 NULL */ } AdjList; typedef struct Graph { int V; /* 顶点总数Vertex count */ int E; /* 当前边总数Edge count */ AdjList* array; /* 邻接表数组长度 Varray[i] 表示顶点 i 的邻接链表 */ char** vertex_names; /* 顶点名称数组长度 Vvertex_names[i] 为顶点 i 的名称字符串或 NULL */ } Graph;基本功能实现图节点初始化链表创建创建图节点的销毁static AdjListNode* new_node(int dest) { AdjListNode* node (AdjListNode*)malloc(sizeof(AdjListNode)); node-dest dest; node-next NULL; return node; } Graph* graph_create(int V) { if (V 0) return NULL; Graph* g (Graph*)malloc(sizeof(Graph));//创建空间 g-V V; g-E 0; g-array (AdjList*)malloc(V * sizeof(AdjList));//创建了多个头指针连续空间通过[]可以控制访问位置 g-vertex_names (char**)malloc(V * sizeof(char*));//同理 //初始化 for (int i 0; i V; i) { g-array[i].head NULL; g-vertex_names[i] NULL; } return g; } void graph_destroy(Graph* g) { if (!g) return; for (int i 0; i g-V; i) { AdjListNode* cur g-array[i].head; while (cur) { AdjListNode* tmp cur; cur cur-next; free(tmp); } free(g-vertex_names[i]); } free(g-array); free(g-vertex_names); free(g); }取名字和查找名字bool graph_set_vertex_name(Graph* g, int v, const char* name) { /* 检查图指针和顶点编号合法性 */ if (!g || v 0 || v g-V) return false; /* 如果该顶点已有名称先释放旧的名称字符串 */ free(g-vertex_names[v]); /* 如果 name 不是 NULL使用 strdup 复制一份新字符串 否则设为 NULL清除名称 */ g-vertex_names[v] name ? strdup(name) : NULL; /* 操作成功 */ return true; } const char* graph_get_vertex_name(Graph* g, int v) { /* 检查参数有效性 */ if (!g || v 0 || v g-V) return NULL; /* 直接返回名称指针 */ return g-vertex_names[v]; }边的构造、边的删除和查找边bool graph_add_edge(Graph* g, int src, int dest) { /* 参数合法性检查 */ if (!g || src 0 || src g-V || dest 0 || dest g-V) return false; /* 在 src 的邻接表头部插入新节点指向 dest */ AdjListNode* node new_node(dest); /* 创建新节点 */ node-next g-array[src].head; /* 新节点指向原头节点 */ g-array[src].head node; /* 更新头指针为新节点 */ /* 在 dest 的邻接表头部插入新节点指向 src实现无向性 */ AdjListNode* node2 new_node(src); /* 创建新节点 */ node2-next g-array[dest].head; /* 新节点指向原头节点 */ g-array[dest].head node2; /* 更新头指针为新节点 */ /* 边计数加 1 */ g-E; /* 操作成功 */ return true; } bool graph_remove_edge(Graph* g, int src, int dest) { /* 参数合法性检查 */ if (!g || src 0 || src g-V || dest 0 || dest g-V) return false; /* ---- 从 src 的链表中删除 dest 节点 ---- */ /* cur 是二级指针指向当前节点的 next 指针的地址 */ AdjListNode** cur g-array[src].head; /* 遍历链表 */ while (*cur) { /* 找到目标顶点编号相同的节点 */ if ((*cur)-dest dest) { /* 暂存待删除节点 */ AdjListNode* tmp *cur; /* 将前驱节点的 next 指向待删除节点的 next跳过该节点 */ *cur (*cur)-next; /* 释放节点内存 */ free(tmp); /* 边计数减 1 */ g-E--; /* 跳出循环 */ break; } /* cur 移到下一个节点的 next 指针地址 */ cur (*cur)-next; } /* ---- 从 dest 的链表中删除 src 节点无向图需要对等删除 ---- */ AdjListNode** cur2 g-array[dest].head; /* 遍历 dest 的邻接链表 */ while (*cur2) { /* 找到指向 src 的节点 */ if ((*cur2)-dest src) { /* 暂存待删除节点 */ AdjListNode* tmp *cur2; /* 跳过该节点 */ *cur2 (*cur2)-next; /* 释放节点内存 */ free(tmp); /* 跳出循环 */ break; } /* cur2 移到下一个节点的 next 指针地址 */ cur2 (*cur2)-next; } /* 操作成功 */ return true; } bool graph_has_edge(Graph* g, int src, int dest) { /* 参数合法性检查 */ if (!g || src 0 || src g-V || dest 0 || dest g-V) return false; /* cur 指向 src 的邻接链表头 */ AdjListNode* cur g-array[src].head; /* 遍历链表 */ while (cur) { /* 如果某个节点的 dest 与目标编号相等说明边存在 */ if (cur-dest dest) return true; /* 继续下一个节点 */ cur cur-next; } /* 遍历完整个链表都没找到说明边不存在 */ return false; }因为是无向图所以需要同时构建两个节点相互链接所以在删除边的也需要同时删除对应的链表的两个节点需要用到循环进行查找位置指定位置进行删除操作。图的遍历方式graph_bfs 广度遍历void graph_bfs(Graph* g, int start) { /* 参数合法性检查 */ if (!g || start 0 || start g-V) return; /* visited 数组记录每个顶点是否已被访问初始全部为 false */ bool* visited (bool*)calloc(g-V, sizeof(bool)); /* queue 数组用数组模拟队列存放待访问的顶点编号 */ int* queue (int*)malloc(g-V * sizeof(int)); /* front —— 队头下标出队位置rear —— 队尾下标入队位置 */ int front 0, rear 0; /* 标记起始顶点为已访问 */ visited[start] true; /* 起始顶点入队 */ queue[rear] start; /* 只要队列不为空就继续遍历 */ while (front rear) { /* 出队一个顶点 v */ int v queue[front]; /* 获取顶点名称有名称则显示名称否则显示编号 */ const char* name g-vertex_names[v]; if (name) printf(%s , name); else printf(%d , v); /* 遍历 v 的所有邻接点 */ AdjListNode* cur g-array[v].head; while (cur) { /* 如果邻接点尚未被访问 */ if (!visited[cur-dest]) { /* 标记为已访问 */ visited[cur-dest] true; /* 将该邻接点入队等待后续访问 */ queue[rear] cur-dest; } /* 继续下一个邻接点 */ cur cur-next; } } /* 换行 */ printf(\n); /* 释放动态分配的内存 */ free(visited); free(queue); }1判断是否符合条件2申请两个空间一个visited作为标记已将访问的空间一个queue用于保存当前有分叉的路口。3循环从头优先访问打印出头和分叉路口的个元素标记已经访问的位置和入队分叉路口如果遇到死胡同或者已经访问的位置就退出每次循环都从队提出位置直到所有元素被访问为止停止循环。graph_bfs —— 广度优先遍历Breadth First Search参数g —— 图指针start —— 起始顶点编号说明使用队列FIFO实现先访问起始顶点再逐层访问其所有邻居直到所有可达顶点都被访问graph_dfs 深度遍历static void dfs_util(Graph* g, int v, bool* visited) { /* 标记当前顶点为已访问 */ visited[v] true; /* 打印当前顶点 */ const char* name g-vertex_names[v]; if (name) printf(%s , name); else printf(%d , v); /* 遍历 v 的所有邻接点 */ AdjListNode* cur g-array[v].head; while (cur) { /* 如果邻接点未被访问递归访问它 */ if (!visited[cur-dest]) { dfs_util(g, cur-dest, visited); } /* 继续下一个邻接点 */ cur cur-next; } } void graph_dfs(Graph* g, int start) { /* 参数合法性检查 */ if (!g || start 0 || start g-V) return; /* 创建访问标记数组初始全为 false */ bool* visited (bool*)calloc(g-V, sizeof(bool)); /* 从 start 开始递归遍历 */ dfs_util(g, start, visited); /* 换行 */ printf(\n); /* 释放动态内存 */ free(visited); }利用递归比广度优先遍历少了一个申请空间visited 依旧功能是用于标记依旧读取过的地址。图的表示方法邻接表代码展示void graph_print(Graph* g) { /* 空指针检查 */ if (!g) return; /* 打印图的基本信息无向、顶点数 V、边数 E */ printf(Graph (undirected, V%d, E%d):\n, g-V, g-E); /* 遍历每个顶点打印其邻接链表 */ for (int i 0; i g-V; i) { /* 获取当前顶点名称优先显示名称否则显示编号 */ const char* name g-vertex_names[i]; if (name) printf(%s, name); else printf(%d, i); /* 打印箭头分隔符 */ printf( - ); /* 遍历邻接链表 */ AdjListNode* cur g-array[i].head; while (cur) { /* 获取邻居顶点的名称优先显示名称 */ const char* dname g-vertex_names[cur-dest]; if (dname) printf(%s, dname); else printf(%d, cur-dest); /* 邻居之间用空格分隔 */ printf( ); /* 移动到下一个邻接点 */ cur cur-next; } /* 链表结尾标记 */ printf(NULL\n); } }main.cgraph_set_vertex_name(g, 0, A); /* 顶点 0 命名为 A */ graph_set_vertex_name(g, 1, B); /* 顶点 1 命名为 B */ graph_set_vertex_name(g, 2, C); /* 顶点 2 命名为 C */ graph_set_vertex_name(g, 3, D); /* 顶点 3 命名为 D */ graph_set_vertex_name(g, 4, E); /* 顶点 4 命名为 E */ /* ---- 添加边 ---- */ /* 在顶点之间添加无向边 */ graph_add_edge(g, 0, 1); /* A - B */ graph_add_edge(g, 0, 3); /* A - D */ graph_add_edge(g, 1, 2); /* B - C */ graph_add_edge(g, 1, 3); /* B - D */ graph_add_edge(g, 2, 4); /* C - E */ graph_add_edge(g, 3, 4); /* D - E */ /* ---- 打印图结构 ---- */ /* 输出邻接表显示每个顶点的所有邻居 */ graph_print(g);输出格式示例邻接矩阵void graph_matrix_print(GraphMatrix* g) { /* 空指针检查 */ if (!g) return; /* 打印基本信息 */ printf(GraphMatrix (undirected, V%d, E%d):\n, g-V, g-E); /* ---- 打印列标头 ---- */ printf( ); /* 左上角留空 */ for (int j 0; j g-V; j) { /* 每列宽度 4 个字符显示顶点名称或编号 */ const char* name g-vertex_names[j]; if (name) printf(%4s, name); else printf(%4d, j); } printf(\n); /* ---- 逐行打印矩阵 ---- */ for (int i 0; i g-V; i) { /* 打印行标头当前顶点名称 */ const char* name g-vertex_names[i]; if (name) printf(%4s, name); else printf(%4d, i); /* 打印该行每个元素1 表示有边0 表示无边 */ for (int j 0; j g-V; j) { printf(%4d, g-matrix[i][j] ? 1 : 0); } /* 行末换行 */ printf(\n); } }输出结果感谢观看悠仁さん