面试题：C语言优化带权图广度优先搜索

Question

现有一个带权无向图，以邻接矩阵的形式存储在二维数组 `graph[V][V]` 中，权值为0表示两顶点不相连。请用C语言实现一个优化的广度优先搜索算法，能够找到从给定源点 `src` 到目标点 `dst` 的最短路径（路径权值和最小），并返回最短路径的权值。假设图中顶点编号从0到 `V - 1`。函数原型为 `int optimizedBFS(int graph[][MAX_SIZE], int V, int src, int dst)`，其中 `MAX_SIZE` 为图的最大顶点数。需要考虑如何优化搜索过程，避免不必要的遍历。

Answer 1

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

#define MAX_SIZE 1000

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

int isQueueEmpty(Queue *q) {
    return q->front == q->rear;
}

void enqueue(Queue *q, int value) {
    q->data[q->rear++] = value;
}

int dequeue(Queue *q) {
    return q->data[q->front++];
}

int optimizedBFS(int graph[][MAX_SIZE], int V, int src, int dst) {
    int visited[V];
    int dist[V];
    memset(visited, 0, sizeof(visited));
    memset(dist, 0x3f3f3f3f, sizeof(dist));
    dist[src] = 0;

    Queue q;
    initQueue(&q);
    enqueue(&q, src);
    visited[src] = 1;

    while (!isQueueEmpty(&q)) {
        int current = dequeue(&q);
        if (current == dst) break;
        for (int i = 0; i < V; i++) {
            if (graph[current][i] > 0 &&!visited[i]) {
                visited[i] = 1;
                dist[i] = dist[current] + graph[current][i];
                enqueue(&q, i);
            }
        }
    }

    return dist[dst] == 0x3f3f3f3f? -1 : dist[dst];
}