mirror of
https://gitee.com/Lamdonn/varch.git
synced 2025-12-06 08:46:42 +08:00
765 lines
17 KiB
Markdown
765 lines
17 KiB
Markdown
## 介绍
|
||
|
||
图（Graph）是一种由节点（或称顶点）和边组成的数据结构，通常用于表示对象之间的关系。以下是图的基本概念及其特点：
|
||
|
||
### 1. 基本组成
|
||
- **节点（Vertex）**：图中的基本单位，表示对象。
|
||
- **边（Edge）**：连接两个节点的线，表示节点之间的关系。
|
||
|
||
### 2. 类型
|
||
- **有向图（Directed Graph）**：边有方向，表示从一个节点到另一个节点的单向关系。
|
||
- **无向图（Undirected Graph）**：边没有方向，表示节点之间的双向关系。
|
||
- **加权图（Weighted Graph）**：边带有权重，表示连接两个节点的代价或距离。
|
||
|
||
### 3. 表示方法
|
||
- **邻接矩阵（Adjacency Matrix）**：用一个二维数组表示节点之间的连接关系，数组中的值表示边的存在（1）或不存在（0），如果是加权图，则用边的权重表示。
|
||
|
||
- **邻接表（Adjacency List）**：用一个数组或链表表示每个节点的邻接节点，适用于稀疏图。
|
||
|
||
### 4. 应用
|
||
- **社交网络**：节点表示用户，边表示用户之间的关系。
|
||
- **网络路由**：节点表示路由器，边表示连接。
|
||
- **路径查找**：如地图应用中查找最短路径。
|
||
|
||
该模块实现了一个图的数据结构，包括基本的图操作，如添加和删除顶点与边，以及深度优先搜索（DFS）和广度优先搜索（BFS）等算法。该图支持有向图和无向图，适合于各种图论应用。
|
||
|
||
## 接口
|
||
|
||
### 创建和删除graph对象
|
||
|
||
```c
|
||
graph_t graph_create(int max, int directed);
|
||
```
|
||
|
||
创建并初始化一个图。
|
||
|
||
**参数**:
|
||
- `max`: 图中最大顶点数。
|
||
- `directed`: 标志位，指示图是否为有向图（非零）或无向图（零）。
|
||
|
||
**返回**: 返回指向新创建图的指针，如果创建失败则返回NULL。
|
||
|
||
```c
|
||
void graph_delete(graph_t graph);
|
||
```
|
||
|
||
销毁图并释放相关资源。
|
||
|
||
**参数**:
|
||
- `graph`: 指向要销毁的图的指针。
|
||
|
||
**返回**: 无
|
||
|
||
例子
|
||
```c
|
||
graph_t graph = graph_create(10, 1);
|
||
graph_delete(graph);
|
||
```
|
||
|
||
### 添加顶点
|
||
|
||
```c
|
||
int graph_add_vertex(graph_t graph, void *data, int size);
|
||
```
|
||
|
||
向图中添加一个顶点。
|
||
|
||
**参数**:
|
||
- `graph`: 指向要添加顶点的图的指针。
|
||
- `data`: 与顶点相关联的数据的指针。
|
||
- `size`: 要复制的数据的大小。
|
||
|
||
**返回**: 返回添加的顶点的索引，如果添加失败则返回-1。
|
||
|
||
例子
|
||
```c
|
||
void graph_traverse_int(int index, void *data, int size)
|
||
{
|
||
printf("graph[%d] %d\r\n", index, *(int *)data);
|
||
}
|
||
|
||
static void test_add_vertex(void)
|
||
{
|
||
graph_t graph = NULL;
|
||
|
||
graph = graph_create(10, 1);
|
||
if (!graph)
|
||
{
|
||
printf("graph_create fail!\r\n");
|
||
}
|
||
|
||
graph_add_vertex(graph, la(int, 12), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 13), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 15), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 23), sizeof(int));
|
||
|
||
graph_ls(graph, graph_traverse_int);
|
||
|
||
graph_delete(graph);
|
||
}
|
||
```
|
||
|
||
其中 `la()` 为获取字面量地址的宏定义，具体可以参考 [test_graph.c](../test/test_graph.c) 文件
|
||
`graph_ls()` 线性搜索方法，下文介绍。
|
||
|
||
结果
|
||
```
|
||
graph[0] 12
|
||
graph[1] 13
|
||
graph[2] 15
|
||
graph[3] 23
|
||
|
||
```
|
||
|
||
### 添加边
|
||
|
||
```c
|
||
int graph_add_edge(graph_t graph, int start, int end, int weight);
|
||
```
|
||
|
||
向图中添加一条边。
|
||
|
||
**参数**:
|
||
- `graph`: 指向要添加边的图的指针。
|
||
- `start`: 起始顶点的索引。
|
||
- `end`: 结束顶点的索引。
|
||
- `weight`: 边的权重。
|
||
|
||
**返回**: 如果边成功添加返回1，失败返回0。
|
||
|
||
例子
|
||
```c
|
||
static void test_add_edge(void)
|
||
{
|
||
graph_t graph = NULL;
|
||
|
||
graph = graph_create(10, 1);
|
||
if (!graph)
|
||
{
|
||
printf("graph_create fail!\r\n");
|
||
}
|
||
|
||
graph_add_vertex(graph, la(int, 12), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 13), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 15), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 23), sizeof(int));
|
||
|
||
printf("---------------\r\n");
|
||
|
||
graph_dfs(graph, 0, graph_traverse_int);
|
||
|
||
printf("---------------\r\n");
|
||
|
||
graph_add_edge(graph, 0, 1, 0);
|
||
graph_add_edge(graph, 0, 2, 0);
|
||
graph_add_edge(graph, 0, 3, 0);
|
||
graph_add_edge(graph, 1, 0, 0);
|
||
graph_add_edge(graph, 1, 2, 0);
|
||
graph_add_edge(graph, 1, 3, 0);
|
||
graph_add_edge(graph, 2, 3, 0);
|
||
|
||
graph_dfs(graph, 0, graph_traverse_int);
|
||
|
||
printf("---------------\r\n");
|
||
|
||
graph_delete(graph);
|
||
}
|
||
```
|
||
|
||
`graph_dfs()` 为深度优先搜索方法，下文介绍
|
||
|
||
对比添加边前后搜索的情况，没有边连接的图搜不到下一个顶点
|
||
|
||
结果
|
||
```
|
||
---------------
|
||
graph[0] 12
|
||
---------------
|
||
graph[0] 12
|
||
graph[3] 23
|
||
graph[2] 15
|
||
graph[1] 13
|
||
---------------
|
||
```
|
||
|
||
### 移除顶点和边
|
||
|
||
```c
|
||
int graph_remove_vertex(graph_t graph, int index);
|
||
```
|
||
|
||
从图中移除指定的顶点及其关联的边。
|
||
|
||
**参数**:
|
||
- `graph`: 指向要移除顶点的图的指针。
|
||
- `index`: 要移除的顶点的索引。
|
||
|
||
**返回**: 如果顶点成功移除返回1，失败返回0。
|
||
|
||
```c
|
||
int graph_remove_edge(graph_t graph, int start, int end);
|
||
```
|
||
|
||
从图中移除指定的边。
|
||
|
||
**参数**:
|
||
- `graph`: 指向要移除边的图的指针。
|
||
- `start`: 边的起始顶点索引。
|
||
- `end`: 边的结束顶点索引。
|
||
|
||
**返回**: 如果边成功移除返回1，失败返回0。
|
||
|
||
例子
|
||
```c
|
||
static void test_remove(void)
|
||
{
|
||
graph_t graph = NULL;
|
||
|
||
graph = graph_create(100, 1);
|
||
if (!graph)
|
||
{
|
||
printf("graph_create fail!\r\n");
|
||
}
|
||
|
||
graph_add_vertex(graph, la(int, 100), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 200), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 300), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 500), sizeof(int));
|
||
|
||
graph_add_edge(graph, 0, 1, 0);
|
||
graph_add_edge(graph, 0, 2, 0);
|
||
graph_add_edge(graph, 0, 3, 0);
|
||
graph_add_edge(graph, 1, 0, 0);
|
||
graph_add_edge(graph, 1, 2, 0);
|
||
graph_add_edge(graph, 1, 3, 0);
|
||
graph_add_edge(graph, 2, 3, 0);
|
||
|
||
graph_remove_vertex(graph, 1);
|
||
graph_remove_edge(graph, 0, 2);
|
||
|
||
graph_dfs(graph, 0, graph_traverse_int);
|
||
|
||
graph_delete(graph);
|
||
}
|
||
```
|
||
|
||
结果
|
||
```
|
||
graph[0] 100
|
||
graph[3] 500
|
||
```
|
||
|
||
### 遍历
|
||
|
||
```c
|
||
void graph_ls(graph_t graph, graph_traverse_t func);
|
||
```
|
||
|
||
从图开始位置逐个线性遍历。
|
||
|
||
**参数**:
|
||
- `graph`: 指向要遍历的图的指针。
|
||
- `func`: 对每个访问到的顶点执行的回调函数。
|
||
|
||
**返回**: 无
|
||
|
||
```c
|
||
void graph_ls(graph_t graph, graph_traverse_t func);
|
||
```
|
||
|
||
从指定起始顶点开始执行深度优先遍历。
|
||
|
||
**参数**:
|
||
- `graph`: 指向要遍历的图的指针。
|
||
- `start`: 起始顶点的索引。
|
||
- `func`: 对每个访问到的顶点执行的回调函数。
|
||
|
||
**返回**: 无
|
||
|
||
```c
|
||
void graph_dfs(graph_t graph, int start, graph_traverse_t func);
|
||
```
|
||
|
||
从指定起始顶点开始执行广度优先遍历。
|
||
|
||
**参数**:
|
||
- `graph`: 指向要遍历的图的指针。
|
||
- `start`: 起始顶点的索引。
|
||
- `func`: 对每个访问到的顶点执行的回调函数。
|
||
|
||
**返回**: 无
|
||
|
||
例子
|
||
```c
|
||
static void test_search(void)
|
||
{
|
||
graph_t graph = NULL;
|
||
|
||
graph = graph_create(100, 1);
|
||
if (!graph)
|
||
{
|
||
printf("graph_create fail!\r\n");
|
||
}
|
||
|
||
graph_add_vertex(graph, la(int, 100), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 200), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 300), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 500), sizeof(int));
|
||
|
||
graph_add_edge(graph, 0, 1, 0);
|
||
graph_add_edge(graph, 0, 2, 0);
|
||
graph_add_edge(graph, 0, 3, 0);
|
||
graph_add_edge(graph, 1, 0, 0);
|
||
graph_add_edge(graph, 1, 2, 0);
|
||
graph_add_edge(graph, 1, 3, 0);
|
||
graph_add_edge(graph, 2, 3, 0);
|
||
|
||
graph_remove_vertex(graph, 1);
|
||
graph_remove_edge(graph, 0, 2);
|
||
|
||
printf("graph_ls ----------------------\r\n");
|
||
graph_ls(graph, graph_traverse_int);
|
||
printf("graph_dfs ----------------------\r\n");
|
||
graph_dfs(graph, 0, graph_traverse_int);
|
||
printf("graph_bfs ----------------------\r\n");
|
||
graph_bfs(graph, 0, graph_traverse_int);
|
||
|
||
graph_delete(graph);
|
||
}
|
||
```
|
||
|
||
结果
|
||
```
|
||
graph_ls ----------------------
|
||
graph[0] 100
|
||
graph[2] 300
|
||
graph[3] 500
|
||
graph_dfs ----------------------
|
||
graph[0] 100
|
||
graph[3] 500
|
||
graph_bfs ----------------------
|
||
graph[0] 100
|
||
graph[3] 500
|
||
```
|
||
|
||
### 设置和获取数据
|
||
|
||
```c
|
||
int graph_vertex_set_data(graph_t graph, int index, void *data, int size);
|
||
```
|
||
|
||
为图中的指定顶点设置数据。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
- `index`: 顶点的索引。
|
||
- `data`: 要设置的数据的指针。
|
||
- `size`: 数据的大小。
|
||
|
||
**返回**: 如果成功设置数据返回1，失败返回0。
|
||
|
||
```c
|
||
int graph_vertex_get_data(graph_t graph, int index, void *data, int size);
|
||
```
|
||
|
||
从图中的指定顶点获取数据。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
- `index`: 顶点的索引。
|
||
- `data`: 指向将要复制数据的位置的指针。
|
||
- `size`: 数据缓冲区的大小。
|
||
|
||
**返回**: 如果成功获取数据返回1，失败返回0。
|
||
|
||
```c
|
||
void *graph_vertex_data(graph_t graph, int index, int *size);
|
||
```
|
||
|
||
获取图中指定顶点的数据。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
- `index`: 顶点的索引。
|
||
- `size`: 指向存储顶点数据大小的指针（如果不为NULL）。
|
||
|
||
**返回**: 返回顶点数据的指针，如果失败则返回NULL。
|
||
|
||
例子
|
||
```c
|
||
static void test_data(void)
|
||
{
|
||
graph_t graph = NULL;
|
||
|
||
graph = graph_create(100, 1);
|
||
if (!graph)
|
||
{
|
||
printf("graph_create fail!\r\n");
|
||
}
|
||
|
||
graph_add_vertex(graph, la(int, 100), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 200), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 300), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 500), sizeof(int));
|
||
|
||
graph_vertex_set_data(graph, 2, la(int, 1024), sizeof(int));
|
||
|
||
int size = 0;
|
||
printf("graph_vertex_data[3].data = %d\r\n", *(int *)graph_vertex_data(graph, 3, &size));
|
||
printf("graph_vertex_data[3].size = %d\r\n", size);
|
||
|
||
graph_ls(graph, graph_traverse_int);
|
||
|
||
graph_delete(graph);
|
||
}
|
||
```
|
||
|
||
结果
|
||
```
|
||
graph_vertex_data[3].data = 500
|
||
graph_vertex_data[3].size = 4
|
||
graph[0] 100
|
||
graph[1] 200
|
||
graph[2] 1024
|
||
graph[3] 500
|
||
```
|
||
|
||
### 出度和入度
|
||
|
||
```c
|
||
int graph_out_degree(graph_t graph, int index);
|
||
```
|
||
|
||
获取指定顶点的出度。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
- `index`: 顶点的索引。
|
||
|
||
**返回**: 顶点的出度，如果失败返回-1。
|
||
|
||
```c
|
||
int graph_in_degree(graph_t graph, int index);
|
||
```
|
||
|
||
获取指定顶点的入度。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
- `index`: 顶点的索引。
|
||
|
||
**返回**: 顶点的入度，如果失败返回-1。
|
||
|
||
例子
|
||
```c
|
||
static void test_degree(void)
|
||
{
|
||
graph_t graph = NULL;
|
||
|
||
graph = graph_create(10, 1);
|
||
if (!graph)
|
||
{
|
||
printf("graph_create fail!\r\n");
|
||
}
|
||
|
||
graph_add_vertex(graph, la(int, 100), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 200), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 300), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 500), sizeof(int));
|
||
|
||
graph_add_edge(graph, 0, 1, 0);
|
||
graph_add_edge(graph, 0, 2, 0);
|
||
graph_add_edge(graph, 0, 3, 0);
|
||
graph_add_edge(graph, 1, 0, 0);
|
||
graph_add_edge(graph, 1, 2, 0);
|
||
graph_add_edge(graph, 1, 3, 0);
|
||
graph_add_edge(graph, 2, 3, 0);
|
||
|
||
printf("graph_out_degree %d\r\n", graph_out_degree(graph, 3));
|
||
printf("graph_out_degree %d\r\n", graph_out_degree(graph, 2));
|
||
|
||
printf("graph_in_degree %d\r\n", graph_in_degree(graph, 0));
|
||
printf("graph_in_degree %d\r\n", graph_in_degree(graph, 2));
|
||
|
||
graph_delete(graph);
|
||
}
|
||
```
|
||
|
||
结果
|
||
```
|
||
graph_out_degree 0
|
||
graph_out_degree 1
|
||
graph_in_degree 1
|
||
graph_in_degree 2
|
||
```
|
||
|
||
### 相邻
|
||
|
||
```c
|
||
int graph_is_adjacent(graph_t graph, int start, int end);
|
||
```
|
||
|
||
检查两个顶点是否相邻。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
- `start`: 起始顶点的索引。
|
||
- `end`: 结束顶点的索引。
|
||
|
||
**返回**: 。如果顶点相邻返回1，否则返回0或失败
|
||
|
||
|
||
### 权重
|
||
|
||
```c
|
||
int graph_get_edge_weight(graph_t graph, int start, int end);
|
||
```
|
||
|
||
获取两个顶点之间边的权重（如果存在）。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
- `start`: 起始顶点的索引。
|
||
- `end`: 结束顶点的索引。
|
||
|
||
**返回**: 边的权重，如果失败或边不存在返回INT_MAX。
|
||
|
||
```c
|
||
int graph_set_edge_weight(graph_t graph, int start, int end, int weight);
|
||
```
|
||
|
||
设置两个顶点之间边的权重（如果存在）。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
- `start`: 起始顶点的索引。
|
||
- `end`: 结束顶点的索引。
|
||
- `weight`: 边的权重。
|
||
|
||
**返回**: 如果存在该边返回1，否则返回0或失败。
|
||
|
||
例子
|
||
```c
|
||
static void test_weight(void)
|
||
{
|
||
graph_t graph = NULL;
|
||
|
||
graph = graph_create(100, 1);
|
||
if (!graph)
|
||
{
|
||
printf("graph_create fail!\r\n");
|
||
}
|
||
|
||
graph_add_vertex(graph, la(int, 100), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 200), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 300), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 500), sizeof(int));
|
||
|
||
graph_add_edge(graph, 0, 1, 0);
|
||
graph_add_edge(graph, 0, 2, 0);
|
||
graph_add_edge(graph, 0, 3, 10);
|
||
graph_add_edge(graph, 1, 0, 0);
|
||
graph_add_edge(graph, 1, 2, 0);
|
||
graph_add_edge(graph, 1, 3, 0);
|
||
graph_add_edge(graph, 2, 3, 0);
|
||
|
||
printf("graph_get_edge_weight = %d\r\n", graph_get_edge_weight(graph, 0, 3));
|
||
graph_set_edge_weight(graph, 0, 3, 1024);
|
||
printf("graph_get_edge_weight = %d\r\n", graph_get_edge_weight(graph, 0, 3));
|
||
|
||
graph_delete(graph);
|
||
}
|
||
```
|
||
|
||
结果
|
||
```
|
||
graph_get_edge_weight = 10
|
||
graph_get_edge_weight = 1024
|
||
|
||
```
|
||
|
||
|
||
### 检查顶点
|
||
|
||
```c
|
||
int graph_contains_vertex(graph_t graph, int index);
|
||
```
|
||
|
||
检查顶点是否存在于图中。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
- `index`: 顶点的索引。
|
||
|
||
**返回**: 如果顶点存在返回1，否则返回0或失败。
|
||
|
||
|
||
### 拓扑排序
|
||
|
||
```c
|
||
int graph_contains_vertex(graph_t graph, int index);
|
||
```
|
||
|
||
对图进行拓扑排序。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
|
||
**返回**: 无
|
||
|
||
|
||
### 最短路径
|
||
|
||
```c
|
||
void graph_shortest_path(graph_t graph, int start);
|
||
```
|
||
|
||
查找从起始顶点到其它顶点的最短路径。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
- `start`: 起始顶点的索引。
|
||
|
||
**返回**: 无
|
||
|
||
例子
|
||
```c
|
||
static void test_shortest_path(void)
|
||
{
|
||
graph_t graph = NULL;
|
||
|
||
graph = graph_create(100, 1);
|
||
if (!graph)
|
||
{
|
||
printf("graph_create fail!\r\n");
|
||
}
|
||
|
||
graph_add_vertex(graph, la(int, 100), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 200), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 300), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 500), sizeof(int));
|
||
|
||
graph_add_edge(graph, 0, 1, 3);
|
||
graph_add_edge(graph, 0, 2, 2);
|
||
graph_add_edge(graph, 0, 3, 5);
|
||
graph_add_edge(graph, 1, 0, 6);
|
||
graph_add_edge(graph, 1, 2, 3);
|
||
graph_add_edge(graph, 1, 3, 2);
|
||
graph_add_edge(graph, 2, 3, 1);
|
||
|
||
graph_shortest_path(graph, 0);
|
||
|
||
graph_delete(graph);
|
||
}
|
||
```
|
||
|
||
结果
|
||
```
|
||
Shortest path from 0 to 0: 0 (0)
|
||
Shortest path from 0 to 1: 3 (0 -> 1)
|
||
Shortest path from 0 to 2: 2 (0 -> 2)
|
||
Shortest path from 0 to 3: 3 (0 -> 2 -> 3)
|
||
```
|
||
|
||
### 连通图
|
||
|
||
```c
|
||
int graph_is_connected(graph_t graph);
|
||
```
|
||
|
||
检查图是否连通。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
|
||
**返回**: 如果图连通返回1，否则返回0。
|
||
|
||
|
||
### 完全图
|
||
|
||
```c
|
||
int graph_is_complete(graph_t graph);
|
||
```
|
||
|
||
检查图是否为完全图。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
|
||
**返回**: 如果图为完全图返回1，否则返回0。
|
||
|
||
### 二部图
|
||
|
||
```c
|
||
int graph_is_bipartite(graph_t graph);
|
||
```
|
||
|
||
检查图是否为二部图。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
|
||
**返回**: 如果图为二部图返回1，否则返回0。
|
||
|
||
### 欧拉图
|
||
|
||
```c
|
||
int graph_is_eulerian(graph_t graph);
|
||
```
|
||
|
||
检查图是否为欧拉图（能恰好遍历每条边一次）。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
|
||
**返回**: 如果图为欧拉图返回1，否则返回0。
|
||
|
||
### 最小顶点覆盖
|
||
|
||
```c
|
||
void graph_min_vertex_cover(graph_t graph);
|
||
```
|
||
|
||
计算图的最小顶点覆盖。
|
||
|
||
**参数**:
|
||
- `graph`: 指向图的指针。
|
||
|
||
**返回**: 无
|
||
|
||
例子
|
||
```c
|
||
static void test_min_cover(void)
|
||
{
|
||
graph_t graph = NULL;
|
||
|
||
graph = graph_create(100, 1);
|
||
if (!graph)
|
||
{
|
||
printf("graph_create fail!\r\n");
|
||
}
|
||
|
||
graph_add_vertex(graph, la(int, 100), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 200), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 300), sizeof(int));
|
||
graph_add_vertex(graph, la(int, 500), sizeof(int));
|
||
|
||
graph_add_edge(graph, 0, 1, 3);
|
||
graph_add_edge(graph, 0, 2, 2);
|
||
graph_add_edge(graph, 0, 3, 5);
|
||
graph_add_edge(graph, 1, 0, 6);
|
||
graph_add_edge(graph, 1, 2, 3);
|
||
graph_add_edge(graph, 1, 3, 2);
|
||
graph_add_edge(graph, 2, 3, 1);
|
||
|
||
graph_min_vertex_cover(graph);
|
||
|
||
graph_delete(graph);
|
||
}
|
||
```
|
||
|
||
结果
|
||
```
|
||
0 3 1 2
|
||
```
|