广度优先算法到目标结点最短路径

广度优先算法可以用来求解到目标结点的最短路径。该算法从起点开始，逐层搜索所有与当前结点相邻的结点，直到找到目标结点为止。在搜索过程中，需要记录每个结点的距离和前驱结点，以便在找到目标结点后回溯路径。

具体实现过程如下：

1. 将起点加入队列，并将其距离设为0。

2. 从队列中取出一个结点，对其所有未访问的相邻结点进行访问，并更新它们的距离和前驱结点。

3. 将已访问的结点标记为已访问，并将它们加入队列。

4. 重复步骤2和3，直到找到目标结点或队列为空。

5. 如果找到目标结点，则回溯路径，输出最短路径。

如果存在多条最短路径，广度优先算法可以保证找到其中一条路径。

相关问题

利用C语言创建一个无向图 用广度优先算法进行图的遍历求从第一个结点到最后一个结点最短路径和长度，输出最短路径和长度

好的，下面是一个示例程序，展示如何使用C语言创建无向图，并使用广度优先搜索算法求从第一个结点到最后一个结点的最短路径和长度：

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

#define MAX_NODE 100

// 定义图节点结构体
typedef struct GraphNode {
    int val;  // 节点值
    int visited;  // 是否被访问过
    struct GraphNode* neighbors[MAX_NODE];  // 邻居指针数组
    int numNeighbors;  // 邻居个数
} GraphNode;

// 创建新的节点
GraphNode* createGraphNode(int val) {
    GraphNode* node = (GraphNode*) malloc(sizeof(GraphNode));
    node->val = val;
    node->visited = 0;
    node->numNeighbors = 0;
    return node;
}

// 添加无向边
void addUndirectedEdge(GraphNode* node1, GraphNode* node2) {
    node1->neighbors[node1->numNeighbors++] = node2;
    node2->neighbors[node2->numNeighbors++] = node1;
}

// 创建无向图
GraphNode* createGraph() {
    GraphNode* node1 = createGraphNode(1);
    GraphNode* node2 = createGraphNode(2);
    GraphNode* node3 = createGraphNode(3);
    GraphNode* node4 = createGraphNode(4);
    GraphNode* node5 = createGraphNode(5);
    GraphNode* node6 = createGraphNode(6);
    GraphNode* node7 = createGraphNode(7);
    GraphNode* node8 = createGraphNode(8);

    addUndirectedEdge(node1, node2);
    addUndirectedEdge(node1, node3);
    addUndirectedEdge(node2, node4);
    addUndirectedEdge(node2, node5);
    addUndirectedEdge(node3, node6);
    addUndirectedEdge(node3, node7);
    addUndirectedEdge(node4, node8);
    addUndirectedEdge(node5, node8);
    addUndirectedEdge(node6, node8);
    addUndirectedEdge(node7, node8);

    return node1;
}

// 定义队列结构体
typedef struct QueueNode {
    GraphNode* node;  // 节点指针
    int distance;  // 距离起点的距离
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

// 创建新的队列
Queue* createQueue() {
    Queue* q = (Queue*) malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

// 入队操作
void enqueue(Queue* q, GraphNode* node, int distance) {
    QueueNode* qNode = (QueueNode*) malloc(sizeof(QueueNode));
    qNode->node = node;
    qNode->distance = distance;
    qNode->next = NULL;

    if (q->front == NULL) {
        q->front = qNode;
        q->rear = qNode;
    } else {
        q->rear->next = qNode;
        q->rear = qNode;
    }
}

// 出队操作
QueueNode* dequeue(Queue* q) {
    if (q->front == NULL) {
        return NULL;
    }

    QueueNode* qNode = q->front;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }

    return qNode;
}

// 广度优先搜索
void bfs(GraphNode* start, GraphNode* end) {
    Queue* q = createQueue();

    enqueue(q, start, 0);
    start->visited = 1;

    while (q->front != NULL) {
        QueueNode* qNode = dequeue(q);
        GraphNode* node = qNode->node;
        int distance = qNode->distance;

        free(qNode);

        if (node == end) {
            printf("最短路径长度为：%d\n", distance);
            return;
        }

        for (int i = 0; i < node->numNeighbors; i++) {
            GraphNode* neighbor = node->neighbors[i];
            if (!neighbor->visited) {
                neighbor->visited = 1;
                enqueue(q, neighbor, distance + 1);
            }
        }
    }

    printf("无法到达终点节点！\n");
}

int main() {
    GraphNode* graph = createGraph();
    bfs(graph, createGraphNode(8));
    return 0;
}

在这个示例程序中，我们首先定义了一个 `GraphNode` 结构体来表示图节点，其中包含了节点值、是否被访问过、邻居节点指针数组以及邻居节点个数等信息。然后我们使用 `createGraphNode` 函数来创建新的节点，并使用 `addUndirectedEdge` 函数来添加无向边，从而创建无向图。在本例中，我们创建了一个包含8个节点的无向图。

接着，我们定义了一个 `QueueNode` 结构体来表示队列节点，其中包含了节点指针和距离起点的距离等信息。然后我们使用 `createQueue` 函数来创建新的队列，并使用 `enqueue` 函数和 `dequeue` 函数来进行入队和出队操作，从而实现广度优先搜索。

最后，我们在 `main` 函数中创建了无向图，并使用 `bfs` 函数来进行广度优先搜索，求出了从第一个结点到最后一个结点的最短路径和长度。

你可以在本地编译运行这个程序，查看输出结果。

c语言使用广度优先遍历实现无向图的最短路径

实现无向图的最短路径可以使用BFS（广度优先搜索）算法。以下是使用C语言实现BFS算法的示例代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100

typedef struct ArcNode {
    int adjvex; // 邻接点的下标
    struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    int data; // 顶点的数据
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 邻接表
    int vexnum, arcnum; // 顶点数和边数
} ALGraph;

void BFS(ALGraph G, int start, int end) {
    int visited[G.vexnum]; // 标记顶点是否被访问过
    int queue[MAX_VERTEX_NUM]; // 存放待遍历的顶点
    int front = 0, rear = 0; // 队列的头尾指针
    int path[G.vexnum]; // 存放路径
    int i, j, k, flag = 0;
    ArcNode *p;

    for (i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
        path[i] = -1;
    }

    visited[start] = 1;
    queue[rear++] = start;

    while (front < rear) {
        i = queue[front++];

        p = G.vertices[i].firstarc;
        while (p != NULL) {
            j = p->adjvex;
            if (!visited[j]) {
                visited[j] = 1;
                path[j] = i; // 记录路径上的前驱结点
                queue[rear++] = j;
            }
            if (j == end) {
                flag = 1;
                break;
            }
            p = p->nextarc;
        }

        if (flag) {
            break;
        }
    }

    if (path[end] == -1) {
        printf("No path from %d to %d\n", start, end);
    } else {
        printf("Shortest path from %d to %d: ", start, end);
        k = end;
        while (k != start) {
            printf("%d <- ", k);
            k = path[k];
        }
        printf("%d\n", start);
    }
}

int main() {
    int i, j, k, n, m, u, v;
    ALGraph G;
    ArcNode *p;

    printf("Enter the number of vertices and edges: ");
    scanf("%d %d", &n, &m);
    G.vexnum = n;
    G.arcnum = m;

    for (i = 0; i < n; i++) {
        G.vertices[i].data = i; // 顶点编号
        G.vertices[i].firstarc = NULL; // 初始化第一个邻接点指针
    }

    printf("Enter the edges:\n");
    for (k = 0; k < m; k++) {
        scanf("%d %d", &u, &v);
        p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = v;
        p->nextarc = G.vertices[u].firstarc; // 将新边插入到邻接点链表的头部
        G.vertices[u].firstarc = p;

        p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = u;
        p->nextarc = G.vertices[v].firstarc;
        G.vertices[v].firstarc = p;
    }

    printf("Enter the start and end vertices: ");
    scanf("%d %d", &u, &v);

    BFS(G, u, v);

    return 0;
}

这段代码实现了BFS算法，其中`ALGraph`结构体表示无向图，`BFS`函数用于搜索无向图中的最短路径。在`main`函数中，先读入图的顶点数和边数，再读入每条边的起点和终点，最后读入起点和终点，并调用`BFS`函数搜索最短路径。