利用C语言创建一个无向图 用广度优先算法进行图的遍历求从第一个结点到最后一个结点最短路径和长度,输出最短路径和长度
时间: 2024-02-15 10:02:49 浏览: 101
C语言寻找无向图两点间的最短路径
好的,下面是一个示例程序,展示如何使用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` 函数来进行广度优先搜索,求出了从第一个结点到最后一个结点的最短路径和长度。
你可以在本地编译运行这个程序,查看输出结果。
阅读全文