C语言深度广度优先搜索
时间: 2023-11-23 11:54:49 浏览: 50
深度优先搜索和广度优先搜索是图论中的两个基本算法,它们在C语言中的实现方式如下:
深度优先搜索(DFS):深度优先搜索是一种递归的算法,它从图的某个顶点开始遍历,尽可能深地搜索图的分支,直到不能再继续为止,然后回溯到前一个节点,继续搜索其他分支。在C语言中,可以使用邻接矩阵或邻接表来表示图,然后使用递归函数来实现深度优先搜索。
```
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 顶点数组
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num, edge_num; // 顶点数和边数
} Graph;
void DFS(Graph *G, int v, int visited[]) {
visited[v] = 1; // 标记当前节点已访问
printf("%d ", G->vertex[v]); // 输出当前节点
for (int i = 0; i < G->vertex_num; i++) {
if (G->edge[v][i] && !visited[i]) { // 如果当前节点与下一个节点有边且下一个节点未被访问
DFS(G, i, visited); // 递归访问下一个节点
}
}
}
int main() {
Graph G = {
{1, 2, 3, 4, 5}, // 顶点数组
{
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 1, 0},
{0, 1, 1, 0, 1},
{0, 1, 0, 1, 0}
}, // 邻接矩阵
5, 7 // 顶点数和边数
};
int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有节点未被访问
DFS(&G, 0, visited); // 从第一个节点开始深度优先搜索
return 0;
}
```
广度优先搜索(BFS):广度优先搜索是一种迭代的算法,它从图的某个顶点开始遍历,先访问该顶点的所有邻居节点,然后依次访问邻居节点的邻居节点,直到遍历完整个图。在C语言中,可以使用邻接矩阵或邻接表来表示图,然后使用队列来实现广度优先搜索。
```
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 顶点数组
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num, edge_num; // 顶点数和边数
} Graph;
void BFS(Graph *G, int v, int visited[]) {
int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 定义队列
visited[v] = 1; // 标记当前节点已访问
printf("%d ", G->vertex[v]); // 输出当前节点
queue[rear++] = v; // 将当前节点入队
while (front != rear) { // 队列不为空时循环
int w = queue[front++]; // 取出队首节点
for (int i = 0; i < G->vertex_num; i++) {
if (G->edge[w][i] && !visited[i]) { // 如果当前节点与下一个节点有边且下一个节点未被访问
visited[i] = 1; // 标记下一个节点已访问
printf("%d ", G->vertex[i]); // 输出下一个节点
queue[rear++] = i; // 将下一个节点入队
}
}
}
}
int main() {
Graph G = {
{1, 2, 3, 4, 5}, // 顶点数组
{
{0, 1, 1, 0, 0},
{1, 0, 0, 1, 1},
{1, 0, 0, 1, 0},
{0, 1, 1, 0, 1},
{0, 1, 0, 1, 0}
}, // 邻接矩阵
5, 7 // 顶点数和边数
};
int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有节点未被访问
BFS(&G, 0, visited); // 从第一个节点开始广度优先搜索
return 0;
}
```