BFS算法求无权图最短路径问题
·
目录
一、前言
前一篇文章我们详细讲了BFS的原理及实现,在使用BFS遍历图的过程中,我们可以对每个顶点进行标记,标记当前顶点距离源头顶点的距离。这个距离我们用int d[i]来存储,由于BFS的性质,d[i]中存放的就是源头顶点v到顶点i的最短路径。
二、BFS求某个顶点到其他顶点的最短路径
bool visited[MAX_VERTICES]; //用于标记顶点是否被访问过,访问过为true
queue<int> q; //C++STL中的队列,创建一个辅助队列
int d[MAX_VERTICES]; //d[i]表示从顶点v到顶点i的最短路径
void BFS_MIN_Distance(Graph graph,int v) {
//d[i]表示从顶点v到顶点i的最短路径
for (int i = 0; i < graph.num_vertices; i++) {
d[i] = INT_MAX; //初始化路径长度为无穷大
}
visited[v] = true; //标记为已访问
d[v] = 0; //顶点v到自身的距离为0
q.push(v); //入队
while (!q.empty()) { //当队列不为空时
int QueueHead = q.front(); //获取当前处于队头的顶点
q.pop(); //获取队头后然后再出队
Edge* p = FirstNeighbor(graph, QueueHead); //得到上面获取的队头的指向第一条边的指针
//这层循环将访问与QueueHead关联的所有顶点
while (p != NULL) { //p不为空说明QueueHead有关联的边
int w = p->adjVertex; //w是与v关联的顶点下标
if (!visited[w]) { //未访问
visited[w] = true; //标记为已访问
d[w] = d[QueueHead] + 1; //在上一个相关联的顶点到源顶点的距离的基础上加1
//入队,每次都是先访问标记后再入队
//所以队列中的元素一定是被访问过的,且d[i]被修正过了
q.push(w); //入队
}
p = p->next;
}
}
}
三、完整代码
#include<iostream>
#include<queue> //STL的队列
#include<limits.h> //int的最大值的宏定义在这个头文件
using namespace std;
#define MAX_VERTICES 100
typedef int VertexType;
// 定义图的边结构
typedef struct Edge {
int adjVertex; // 与边相连的另一顶点的索引
Edge* next; // 指向下一条邻接边的指针
} Edge;
// 定义图的顶点结构
typedef struct Vertex {
VertexType data; // 顶点数据
Edge* firstEdge; // 指向第一个邻接边的指针
} Vertex;
// 定义图的邻接表结构
typedef struct Graph {
int num_vertices, num_edges; // 图中顶点的数量
Vertex vertices[MAX_VERTICES]; // 存储顶点的数组
} Graph;
// 初始化图
void initGraph(Graph* graph, int num_vertices) {
graph->num_vertices = num_vertices;
graph->num_edges = 0;
for (int i = 0; i < num_vertices; ++i) {
graph->vertices[i].data = i+97; // 顶点数据字母a开始
graph->vertices[i].firstEdge = NULL; // 初始化顶点的邻接边链表为空
}
}
// 向图中插入一条边 (无向图)
void insertEdge(Graph* graph, int from, int to) {
if (from >= 0 && from < graph->num_vertices && to >= 0 && to < graph->num_vertices) {
// 创建新的边节点,插到from的这条链的链头
Edge* newEdge = (Edge*)malloc(sizeof(Edge));
newEdge->adjVertex = to;
newEdge->next = graph->vertices[from].firstEdge;
// 更新顶点的邻接边链表
graph->vertices[from].firstEdge = newEdge;
// 创建新的边节点,插到to的这条链的链头
Edge* NewEdge = (Edge*)malloc(sizeof(Edge));
NewEdge->adjVertex = from;
NewEdge->next = graph->vertices[to].firstEdge;
// 更新顶点的邻接边链表
graph->vertices[to].firstEdge = NewEdge;
graph->num_edges++;
}
}
//FirstNeighbor(graph, v)是求得与v关联的第一个顶点的指针,没有就return NULL
Edge* FirstNeighbor(Graph graph, int v) {
if (graph.vertices[v].firstEdge != NULL) { //与顶点v关联的第一条边存在
return graph.vertices[v].firstEdge;
}
return NULL;
}
bool visited[MAX_VERTICES]; //用于标记顶点是否被访问过,访问过为true
queue<int> q; //C++STL中的队列,创建一个辅助队列
int d[MAX_VERTICES]; //d[i]表示从顶点v到顶点i的最短路径
void BFS_MIN_Distance(Graph graph,int v) {
//d[i]表示从顶点v到顶点i的最短路径
for (int i = 0; i < graph.num_vertices; i++) {
d[i] = INT_MAX; //初始化路径长度为无穷大
}
visited[v] = true; //标记为已访问
d[v] = 0; //顶点v到自身的距离为0
q.push(v); //入队
while (!q.empty()) { //当队列不为空时
int QueueHead = q.front(); //获取当前处于队头的顶点
q.pop(); //获取队头后然后再出队
Edge* p = FirstNeighbor(graph, QueueHead); //得到上面获取的队头的指向第一条边的指针
//这层循环将访问与QueueHead关联的所有顶点
while (p != NULL) { //p不为空说明QueueHead有关联的边
int w = p->adjVertex; //w是与v关联的顶点下标
if (!visited[w]) { //未访问
visited[w] = true; //标记为已访问
d[w] = d[QueueHead] + 1; //在上一个相关联的顶点到源顶点的距离的基础上加1
//入队,每次都是先访问标记后再入队
//所以队列中的元素一定是被访问过的,且d[i]被修正过了
q.push(w); //入队
}
p = p->next;
}
}
}
int main() {
Graph graph;
initGraph(&graph, 8); //初始化8个顶点
insertEdge(&graph, 0, 2); //a-c
insertEdge(&graph, 0, 1); //a-b
insertEdge(&graph, 1, 4); //b-e
insertEdge(&graph, 1, 3); //b-d
insertEdge(&graph, 2, 6); //c-g
insertEdge(&graph, 2, 5); //c-f
insertEdge(&graph, 4, 7); //e-h
//利用BFS寻找顶点a到其他顶点的距离
BFS_MIN_Distance(graph, 0);
//打印d[i]数组
for (int i = 0; i < graph.num_vertices; i++) {
cout << d[i] << " ";
}
cout << endl;
return 0;
}
四、代码中所创建的图

五、运行结果

更多推荐


所有评论(0)