了解广度优先搜索

2021年11月15日 5点热度 0条评论 来源: zsx0728

文章目录

    在本教程中,您将学习广度优先搜索算法。此外,您还将在C中找到BFS算法的示例。
    遍历是指访问图的所有节点。广度优先遍历或广度优先搜索是一种递归算法,用于搜索图形或树数据结构的所有顶点。

BFS算法

    标准的BFS实现将图的每个顶点分为两类:

  1. 访问过
  2. 未访问过

    该算法的目的是在避免循环的同时将每个顶点标记为已访问。
    该算法的工作原理如下:

  1. 首先将图的任意一个顶点放在队列的后面。
  2. 将队列最前面的项目添加到已访问列表中。
  3. 创建该顶点相邻节点的列表。将不在访问列表中的那些添加到队列的后面。
  4. 重复步骤2和3,直到队列为空。

    图可能有两个不同的断开部分,因此为了确保覆盖每个顶点,我们还可以在每个节点上运行BFS算法。

BFS示例

    让我们通过一个例子来了解广度优先搜索算法是如何工作的。我们使用有5个顶点的无向图。

    我们从顶点0开始,BFS算法首先把它放在访问列表中,然后把所有相邻的顶点放在堆栈中。

    接下来,我们访问队列前面的元素,即1,并转到它的相邻节点。因为已经访问了0,所以我们改为访问2。

    顶点2有一个未访问的相邻顶点4,因此我们将其添加到队列的后面,并访问队列前面的3。


    由于3唯一的相邻节点(即0)已被访问,因此队列中仅剩下4。我们访问它。

    由于队列是空的,我们已经完成了图的广度优先遍历。

BFS伪代码
create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
    remove the head u of Q 
    mark and enqueue all (unvisited) neighbours of u
C示例
// 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;
}
BFS算法复杂度

    BFS算法的时间复杂度以表示O(V + E),其中V是节点数,E是边数。
    该算法的空间复杂度为O(V)。

BFS算法应用
  1. 通过搜索索引建立索引
  2. 用于GPS导航
  3. 路径查找算法
  4. 使用Ford-Fulkerson算法求解网络的最大流量
  5. 无向图的循环检测
  6. 用于最小生成树
参考文档

[1]Parewa Labs Pvt. Ltd.Depth First Search (DFS)[EB/OL].https://www.programiz.com/dsa/graph-bfs,2020-01-01.

    原文作者:zsx0728
    原文地址: https://blog.csdn.net/zsx0728/article/details/114652044
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。