题目五:广度优先搜索算法

广度优先搜索是一种用于图的查找算法，用于解决最短路径问题。它能够从一个起始节点开始，逐层遍历图中的节点，直到找到目标节点或者遍历完整个图。广度优先搜索可以帮助回答两类问题：1. 从节点A出发，有前往节点B的路吗？2. 从节点A出发，前往节点B的哪条路径最短？

广度优先搜索的基本思想是将每一层的节点都加入一个队列中，并按照队列的先进先出原则进行遍历。具体步骤如下：
1. 从起始节点开始，将起始节点标记为已访问，并加入队列。
2. 当队列不为空时，从队列中取出一个节点，并检查该节点是否为目标节点。如果是目标节点，则搜索结束；否则，继续进行下一步。
3. 遍历当前节点的所有邻居节点，将未访问过的邻居节点标记为已访问，并加入队列。
4. 重复步骤2和步骤3，直到队列为空或者找到目标节点。

这样，广度优先搜索会按照层级逐步扩展搜索范围，直到找到目标节点或者遍历完整个图。广度优先搜索可以确保找到的路径是最短路径。

相关问题

题目1：建立一个具有n个结点的无向图的邻接矩阵和邻接表。 （1）、设计一个将邻接矩阵转换为邻接表的算法 （2）、设计一个将邻接表转换为邻接矩阵的算法 （3）、设计以邻接表为存储结构的图的广度优先搜索算法。 （4）、设计以邻接矩阵为存储结构的图的深度优先搜索算法。

1. 建立邻接矩阵和邻接表

我们可以用一个二维数组来表示邻接矩阵，其中 $adj[i][j]=1$ 表示结点 $i$ 和结点 $j$ 之间有一条边，$adj[i][j]=0$ 表示没有边。用一个链表数组来表示邻接表，其中邻接表的第 $i$ 个链表存储与结点 $i$ 相邻的结点。

下面是用 C++ 实现的代码：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 100;

// 邻接矩阵转邻接表
void AdjMatrixToList(int adj[][MAX], int n, int head[], int ver[], int nxt[], int tot) {
  tot = 0;
  memset(head, -1, sizeof(head));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (adj[i][j] == 1) {
        ver[++tot] = j;
        nxt[tot] = head[i];
        head[i] = tot;
      }
    }
  }
}

// 邻接表转邻接矩阵
void AdjListToMatrix(int head[], int ver[], int nxt[], int adj[][MAX], int n) {
  memset(adj, 0, sizeof(adj));
  for (int i = 1; i <= n; i++) {
    for (int j = head[i]; j != -1; j = nxt[j]) {
      adj[i][ver[j]] = 1;
    }
  }
}

// 图的广度优先搜索
void BFS(int head[], int ver[], int nxt[], int n, int s) {
  int q[MAX], vis[MAX] = {0}, front = 0, rear = 0;
  vis[s] = 1;
  q[++rear] = s;
  while (front < rear) {
    int u = q[++front];
    cout << u << " ";
    for (int i = head[u]; i != -1; i = nxt[i]) {
      int v = ver[i];
      if (!vis[v]) {
        vis[v] = 1;
        q[++rear] = v;
      }
    }
  }
}

// 图的深度优先搜索
void DFS(int adj[][MAX], int n, int u, int vis[]) {
  vis[u] = 1;
  cout << u << " ";
  for (int i = 1; i <= n; i++) {
    if (adj[u][i] && !vis[i]) {
      DFS(adj, n, i, vis);
    }
  }
}

int main() {
  int n, m;
  int adj[MAX][MAX], head[MAX], ver[MAX * 2], nxt[MAX * 2], tot = 0;

  // 输入节点数和边数
  cout << "请输入节点数和边数: ";
  cin >> n >> m;

  // 初始化邻接矩阵和邻接表
  memset(adj, 0, sizeof(adj));
  memset(head, -1, sizeof(head));

  // 输入边的信息
  for (int i = 0; i < m; i++) {
    int u, v;
    cout << "请输入第" << i + 1 << "条边的两个端点: ";
    cin >> u >> v;
    adj[u][v] = 1;
    adj[v][u] = 1; // 无向图邻接矩阵对称
    ver[++tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
    ver[++tot] = u;
    nxt[tot] = head[v];
    head[v] = tot;
  }

  // 输出邻接矩阵
  cout << "邻接矩阵: " << endl;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cout << adj[i][j] << " ";
    }
    cout << endl;
  }

  // 输出邻接表
  cout << "邻接表: " << endl;
  for (int i = 1; i <= n; i++) {
    cout << i << ": ";
    for (int j = head[i]; j != -1; j = nxt[j]) {
      cout << ver[j] << " ";
    }
    cout << endl;
  }

  // 广度优先搜索
  cout << "广度优先搜索结果: ";
  BFS(head, ver, nxt, n, 1);
  cout << endl;

  // 深度优先搜索
  cout << "深度优先搜索结果: ";
  int vis[MAX] = {0};
  DFS(adj, n, 1, vis);
  cout << endl;

  return 0;
}

2. 邻接矩阵转邻接表

我们可以遍历邻接矩阵，将每条边的两个端点在邻接表中对应的链表中加入一个新的结点。具体来说，我们可以遍历邻接矩阵中所有非零元素，将邻接矩阵中第 $i$ 行第 $j$ 列的元素 $adj[i][j]$ 对应的邻接表中的结点 $ver$ 加入 $j$，并将 $ver$ 插入到链表头 $head[i]$ 中。这里需要注意的是，因为是无向图，所以对于每条边，我们需要在邻接表中同时插入两个结点，分别对应这条边的两个端点。

下面是用 C++ 实现的代码：

void AdjMatrixToList(int adj[][MAX], int n, int head[], int ver[], int nxt[], int tot) {
  tot = 0;
  memset(head, -1, sizeof(head));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (adj[i][j] == 1) {
        ver[++tot] = j;
        nxt[tot] = head[i];
        head[i] = tot;
      }
    }
  }
}

3. 邻接表转邻接矩阵

我们可以遍历邻接表，将每条边的两个端点在邻接矩阵中对应的元素设为 $1$。具体来说，我们可以遍历邻接表中的所有结点，对于每个结点 $ver_i$，遍历以 $ver_i$ 为起点的所有边，将邻接矩阵中第 $i$ 行第 $j$ 列的元素设为 $1$。

下面是用 C++ 实现的代码：

void AdjListToMatrix(int head[], int ver[], int nxt[], int adj[][MAX], int n) {
  memset(adj, 0, sizeof(adj));
  for (int i = 1; i <= n; i++) {
    for (int j = head[i]; j != -1; j = nxt[j]) {
      adj[i][ver[j]] = 1;
    }
  }
}

4. 图的广度优先搜索

广度优先搜索（BFS）使用队列来实现，每次取出队列的头结点，遍历它的所有相邻结点，将未访问的结点入队，并标记为已访问。下面是用 C++ 实现的代码：

void BFS(int head[], int ver[], int nxt[], int n, int s) {
  int q[MAX], vis[MAX] = {0}, front = 0, rear = 0;
  vis[s] = 1;
  q[++rear] = s;
  while (front < rear) {
    int u = q[++front];
    cout << u << " ";
    for (int i = head[u]; i != -1; i = nxt[i]) {
      int v = ver[i];
      if (!vis[v]) {
        vis[v] = 1;
        q[++rear] = v;
      }
    }
  }
}

5. 图的深度优先搜索

深度优先搜索（DFS）使用递归或栈来实现。下面是用递归实现的代码：

void DFS(int adj[][MAX], int n, int u, int vis[]) {
  vis[u] = 1;
  cout << u << " ";
  for (int i = 1; i <= n; i++) {
    if (adj[u][i] && !vis[i]) {
      DFS(adj, n, i, vis);
    }
  }
}

请用C++实现广度优先算法、深度优先算法和A*算法

由于题目不确定细节，以下是我自己实现的简单版本，供参考：

1. 广度优先算法（BFS）

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100
#define INF 1e9

int n, m; /* n: 点数，m: 边数 */
int graph[MAX_N][MAX_N]; /* 邻接矩阵 */
int dist[MAX_N]; /* 距离数组 */
int visited[MAX_N]; /* 是否访问过 */

int queue[MAX_N]; /* 队列 */
int front = 0, rear = -1;

void bfs(int start) {
    for (int i = 0; i < n; ++i) {
        dist[i] = INF; /* 初始化距离数组 */
        visited[i] = 0;
    }
    dist[start] = 0; /* 起点距离为0 */
    visited[start] = 1;
    queue[++rear] = start; /* 入队 */

    while (front <= rear) { /* 队列非空 */
        int cur = queue[front++]; /* 出队 */
        for (int i = 0; i < n; ++i) {
            if (graph[cur][i] && !visited[i]) { /* 如果存在边且未访问过 */
                dist[i] = dist[cur] + 1; /* 更新距离 */
                visited[i] = 1;
                queue[++rear] = i; /* 入队 */
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1; /* 无向图，建双向边 */
        graph[v][u] = 1;
    }

    bfs(0);

    for (int i = 0; i < n; ++i) {
        printf("%d ", dist[i]);
    }
    printf("\n");

    return 0;
}

2. 深度优先算法（DFS）

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100

int n, m;
int graph[MAX_N][MAX_N]; /* 邻接矩阵 */
int visited[MAX_N]; /* 是否访问过 */

void dfs(int cur) {
    printf("%d ", cur); /* 访问当前节点 */
    visited[cur] = 1;
    for (int i = 0; i < n; ++i) {
        if (graph[cur][i] && !visited[i]) { /* 如果存在边且未访问过 */
            dfs(i); /* 递归深搜 */
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1; /* 无向图，建双向边 */
        graph[v][u] = 1;
    }

    dfs(0);

    return 0;
}

3. A*算法

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_N 100
#define INF 1e9

typedef struct {
    int x;
    int y;
} Point;

int n, m;
Point points[MAX_N]; /* 点数组 */
int graph[MAX_N][MAX_N]; /* 邻接矩阵 */
int dist[MAX_N]; /* 距离数组 */
int visited[MAX_N]; /* 是否访问过 */

/* 计算两个点之间的欧几里得距离 */
double dist_point(Point p1, Point p2) {
    double dx = (double) (p1.x - p2.x);
    double dy = (double) (p1.y - p2.y);
    return sqrt(dx * dx + dy * dy);
}

/* 启发函数，估计点x到点y的距离 */
double heuristic(int x, int y) {
    return dist_point(points[x], points[y]);
}

/* 优先队列实现（小根堆） */
typedef struct {
    int n; /* 当前节点数量 */
    int a[MAX_N]; /* 节点数组 */
    double f[MAX_N]; /* 估价函数值 */
} Heap;

void heap_init(Heap *h) {
    h->n = 0;
}

void heap_push(Heap *h, int x, double f) {
    int i = ++h->n;
    while (i > 1 && f < h->f[i / 2]) { /* 上浮操作 */
        h->a[i] = h->a[i / 2];
        h->f[i] = h->f[i / 2];
        i /= 2;
    }
    h->a[i] = x;
    h->f[i] = f;
}

int heap_pop(Heap *h) {
    int min = h->a[1];
    int x = h->a[h->n--];
    int i = 1, j = 2;
    while (j <= h->n) { /* 下沉操作 */
        if (j < h->n && h->f[j] > h->f[j + 1]) {
            j++;
        }
        if (h->f[j] >= h->f[i]) {
            break;
        }
        h->a[i] = h->a[j];
        h->f[i] = h->f[j];
        i = j;
        j *= 2;
    }
    h->a[i] = x;
    return min;
}

int heap_empty(Heap *h) {
    return h->n == 0;
}

void a_star(int start, int end) {
    for (int i = 0; i < n; ++i) {
        dist[i] = INF; /* 初始化距离数组 */
        visited[i] = 0;
    }

    Heap heap;
    heap_init(&heap);
    dist[start] = 0; /* 起点距离为0 */
    heap_push(&heap, start, heuristic(start, end)); /* 将起点加入队列 */

    while (!heap_empty(&heap)) { /* 队列非空 */
        int cur = heap_pop(&heap); /* 取出优先级最高的节点 */
        visited[cur] = 1;
        if (cur == end) { /* 到达终点 */
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (graph[cur][i] && !visited[i]) { /* 如果存在边且未访问过 */
                double new_dist = dist[cur] + dist_point(points[cur], points[i]);
                if (new_dist < dist[i]) {
                    dist[i] = new_dist;
                    heap_push(&heap, i, dist[i] + heuristic(i, end)); /* 加入队列 */
                }
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        int x, y;
        scanf("%d %d", &x, &y);
        points[i].x = x;
        points[i].y = y;
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u][v] = 1; /* 无向图，建双向边 */
        graph[v][u] = 1;
    }

    a_star(0, n - 1);

    printf("%d\n", dist[n - 1]);

    return 0;
}