c - 如何使用 BFS 查找 C 图中两个顶点之间的所有最短路径？

Question

我不确定如何使用 BFS 来查找 C 中给定图中两个顶点之间的所有最短路径。该图是未加权且无向的。到目前为止，我有以下 BFS 代码(不知道如何将其转变为查找两个给定节点之间的所有最短路径)。我不知道如何找到所有这些并存储它们。非常感谢您的帮助。

// BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
  struct queue* q = createQueue();

  graph->visited[startVertex] = 1;
  enqueue(q, startVertex);

  while (!isEmpty(q)) {
    printQueue(q);
    int currentVertex = dequeue(q);
    printf("Visited %d\n", currentVertex);

    struct node* temp = graph->adjLists[currentVertex];

    while (temp) {
      int adjVertex = temp->vertex;

      if (graph->visited[adjVertex] == 0) {
        graph->visited[adjVertex] = 1;
        enqueue(q, adjVertex);
      }
      temp = temp->next;
    }
  }
}

下面是我的完整程序:

// BFS algorithm in C

#include <stdio.h>
#include <stdlib.h>
#define SIZE 40

struct queue {
  int items[SIZE];
  int front;
  int rear;
};

struct queue* createQueue();
void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);

struct node {
  int vertex;
  struct node* next;
};

struct node* createNode(int);

struct Graph {
  int numVertices;
  struct node** adjLists;
  int* visited;
};

// BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
  struct queue* q = createQueue();

  graph->visited[startVertex] = 1;
  enqueue(q, startVertex);

  while (!isEmpty(q)) {
    printQueue(q);
    int currentVertex = dequeue(q);
    printf("Visited %d\n", currentVertex);

    struct node* temp = graph->adjLists[currentVertex];

    while (temp) {
      int adjVertex = temp->vertex;

      if (graph->visited[adjVertex] == 0) {
        graph->visited[adjVertex] = 1;
        enqueue(q, adjVertex);
      }
      temp = temp->next;
    }
  }
}

// Creating a node
struct node* createNode(int v) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = v;
  newNode->next = NULL;
  return newNode;
}

// Creating a graph
struct Graph* createGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));
  graph->visited = malloc(vertices * sizeof(int));

  int i;
  for (i = 0; i < vertices; i++) {
    graph->adjLists[i] = NULL;
    graph->visited[i] = 0;
  }

  return graph;
}

// Add edge
void addEdge(struct Graph* graph, int src, int dest) {
  // Add edge from src to dest
  struct node* newNode = createNode(dest);
  newNode->next = graph->adjLists[src];
  graph->adjLists[src] = newNode;

  // Add edge from dest to src
  newNode = createNode(src);
  newNode->next = graph->adjLists[dest];
  graph->adjLists[dest] = newNode;
}

// Create a queue
struct queue* createQueue() {
  struct queue* q = malloc(sizeof(struct queue));
  q->front = -1;
  q->rear = -1;
  return q;
}

// Check if the queue is empty
int isEmpty(struct queue* q) {
  if (q->rear == -1)
    return 1;
  else
    return 0;
}

// Adding elements into queue
void enqueue(struct queue* q, int value) {
  if (q->rear == SIZE - 1)
    printf("\nQueue is Full!!");
  else {
    if (q->front == -1)
      q->front = 0;
    q->rear++;
    q->items[q->rear] = value;
  }
}

// Removing elements from queue
int dequeue(struct queue* q) {
  int item;
  if (isEmpty(q)) {
    printf("Queue is empty");
    item = -1;
  } else {
    item = q->items[q->front];
    q->front++;
    if (q->front > q->rear) {
      printf("Resetting queue ");
      q->front = q->rear = -1;
    }
  }
  return item;
}

// Print the queue
void printQueue(struct queue* q) {
  int i = q->front;

  if (isEmpty(q)) {
    printf("Queue is empty");
  } else {
    printf("\nQueue contains \n");
    for (i = q->front; i < q->rear + 1; i++) {
      printf("%d ", q->items[i]);
    }
  }
}

int main() {
  struct Graph* graph = createGraph(6);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 1, 2);
  addEdge(graph, 1, 4);
  addEdge(graph, 1, 3);
  addEdge(graph, 2, 4);
  addEdge(graph, 3, 4);

  bfs(graph, 0);

  return 0;
}

Answer 1

Dijkstra算法与BFS密切相关，对于均匀加权图来说两者是等价的。因此，毫不奇怪的是，人们对 Dijkstra 算法进行的同样的适应，除了捕获路径的长度之外，还可以捕获最短路径，并且可以与 BFS 一起使用来查找最少节点路径。

具体来说，

1. 您可以使用空的前置节点来注释起始节点。
2. 每次将另一个节点放入队列进行遍历时，都会使用到达该节点的节点作为其前一个节点对其进行注释。

然后，当到达目标节点时，可以通过追踪前面节点的链来获得路径。如果您正确地编写了 BFS 本身，那么生成的路径将是最佳的，但不一定是唯一的。

---

要获得所有最佳路径，您可以使用上述内容的进一步调整。不是跟踪每个节点的单个前驱，而是跟踪与起始节点距离相同的前驱列表。这要求您还跟踪每个节点的距离(再次像 Dijkstra 算法)。然后，当您考虑正在访问的节点的后继节点时，您可以测试它们(包括已经访问过的节点)，以确定是否将当前节点添加到其前驱列表中。

然后，您必须继续 BFS 过程，直到满足以下条件之一:

• 队列中没有更多节点，或者
• 所有的目标节点都被访问过，并且所有入队的节点距离起始节点的距离至少与最远的目标节点一样远(但是你只需要检查队列的头节点，因为后面的节点都不能比它更接近)

此时，通过追踪前面节点的链就可以得到所有的最优路径。请注意，Dijkstra 算法也有类似的情况。