使用BFS计算源和顶点之间的距离

本文介绍了使用BFS计算源和顶点之间的距离的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试使用邻接表来计算从源顶点到其他顶点的距离。我正在使用一个队列来完成此操作，但是我得到除源之外的每个顶点的距离为-1，但是我不确定为什么会这样

I am trying to use adjacency list to compute the distance from a source vertex to the other vertices. I am using a queue to accomplish this however I get the distance of each vertex besides the source as -1, but I am not sure why this is happening

#include <stdio.h> #include <stdlib.h> #include "input_error.h" #define VertexToSearch 1 typedef struct edge { int vertexIndex; struct edge *edgePtr; } edge; typedef struct vertex { int vertexKey; struct edge *edgePtr; int visited; int distance; } vertex; typedef struct queue { struct vertex v; struct queue* next; }queue; int vertexCount = 0; struct vertex graph[]; void load_file(char*); void insertEdge(int, int, struct vertex[]); void InsertVertex(int, struct vertex[]); void printGraph(); void bfs(); void print_distances(); queue* enqueue(queue*,vertex ); vertex dequeue(queue*); enum error program_error; int count; int main(int argc, char** argv) { load_file(argv[1]); printGraph(); bfs(); print_distances(); return 0; } void load_file(char* filename) { int vertex1; int vertex2; FILE* file = fopen(filename, "r"); if (file == NULL) { printf("%s did not open\n", filename); program_error = FILE_FAILED_TO_OPEN; exit(program_error); } fscanf(file, "%d", &count); graph[count]; for (int i = 0; i < count; i++) { InsertVertex(i + 1, graph); } for (int i = 0; i < count; i++) { fscanf(file, "\n(%d,%d)", &vertex1, &vertex2); insertEdge(vertex1, vertex2, graph); } fclose(file); } void InsertVertex(int vertexKey, struct vertex graph[]) { graph[vertexCount].vertexKey = vertexKey; graph[vertexCount].edgePtr = NULL; graph[vertexCount].visited = 0; graph[vertexCount].distance = -1; vertexCount++; } void insertEdge(int vertex1, int vertex2, struct vertex graph[]) { struct edge *e, *e1, *e2; e = graph[vertex1 - 1].edgePtr; while (e && e->edgePtr) { e = e->edgePtr; } e1 = (struct edge *) malloc(sizeof (*e1)); e1->vertexIndex = vertex2; e1->edgePtr = NULL; if (e) e->edgePtr = e1; else graph[vertex1 - 1].edgePtr = e1; e = graph[vertex2 - 1].edgePtr; while (e && e->edgePtr) { e = e->edgePtr; } e2 = (struct edge *) malloc(sizeof (*e2)); e2->vertexIndex = vertex1; e2->edgePtr = NULL; if (e) e->edgePtr = e2; else graph[vertex2 - 1].edgePtr = e2; } void printGraph() { int i; struct edge *e; for (i = 0; i < vertexCount; i++) { printf("%d(%d)", i + 1, graph[i].vertexKey); e = graph[i].edgePtr; while (e) { printf("->%d", e->vertexIndex); e = e->edgePtr; } printf("\n"); } } void bfs() { graph[0].distance = 0; queue* q = NULL; q = enqueue(q,graph[0]); while(q->next != NULL){ vertex u = dequeue(q); while(u.edgePtr != NULL){ if(graph[u.edgePtr->vertexIndex -1 ].distance == -1){ graph[u.edgePtr->vertexIndex -1 ].distance = u.distance + 1; enqueue(q, graph[u.edgePtr->vertexIndex -1 ]); } u.edgePtr = u.edgePtr->edgePtr; } } } void print_distances() { for (int i = 0; i < count; i++) { printf("%d %d\n", i + 1, graph[i].distance); } } queue* enqueue(queue* q,vertex v) { queue* new = malloc(sizeof (queue)); new->next = NULL; new->v = v; if (q == NULL) { q = malloc(sizeof(queue)); q = new; } else { while (q->next != NULL) { q = q->next; } //add new node at the end q->next = new; } return q; } vertex dequeue(queue* q) { vertex v; queue* tempPtr; tempPtr = q; //makes temp the address of the node to be deleted v = tempPtr->v; q = q->next; //sets the new head as the address of the next node return v; }

推荐答案

我知道了，基本上我的队列实现是可怕的，出队没有清除队列，这个 while（q-> next！= NULL）是不正确的，应该是 while（q！= NULL）下面是该程序的正确实现

I have figured it out, basically my queue implementation was horrible and dequeue was not clearing out the queue, also this while(q->next != NULL) was incorrect it should be while(q != NULL) Below is the correct implementation of this program

#include <stdio.h> #include <stdlib.h> #include "input_error.h" #define VertexToSearch 1 typedef struct edge { int vertexIndex; struct edge *edgePtr; } edge; typedef struct vertex { int vertexKey; struct edge *edgePtr; int visited; int distance; } vertex; typedef struct queue { struct vertex v; struct queue* next; }queue; int vertexCount = 0; struct vertex graph[]; queue* q = NULL; void load_file(char*); void insertEdge(int, int, struct vertex[]); void InsertVertex(int, struct vertex[]); void printGraph(); void bfs(); void print_distances(); void enqueue(vertex); vertex dequeue(); enum error program_error; int count; int main(int argc, char** argv) { load_file(argv[1]); printGraph(); bfs(); print_distances(); return 0; } void load_file(char* filename) { int vertex1; int vertex2; FILE* file = fopen(filename, "r"); if (file == NULL) { printf("%s did not open\n", filename); program_error = FILE_FAILED_TO_OPEN; exit(program_error); } fscanf(file, "%d", &count); graph[count]; for (int i = 0; i < count; i++) { InsertVertex(i + 1, graph); } for (int i = 0; i < count; i++) { fscanf(file, "\n(%d,%d)", &vertex1, &vertex2); insertEdge(vertex1, vertex2, graph); } fclose(file); } void InsertVertex(int vertexKey, struct vertex graph[]) { graph[vertexCount].vertexKey = vertexKey; graph[vertexCount].edgePtr = NULL; graph[vertexCount].visited = 0; graph[vertexCount].distance = -1; vertexCount++; } void insertEdge(int vertex1, int vertex2, struct vertex graph[]) { struct edge *e, *e1, *e2; e = graph[vertex1 - 1].edgePtr; while (e && e->edgePtr) { e = e->edgePtr; } e1 = (struct edge *) malloc(sizeof (*e1)); e1->vertexIndex = vertex2; e1->edgePtr = NULL; if (e) e->edgePtr = e1; else graph[vertex1 - 1].edgePtr = e1; e = graph[vertex2 - 1].edgePtr; while (e && e->edgePtr) { e = e->edgePtr; } e2 = (struct edge *) malloc(sizeof (*e2)); e2->vertexIndex = vertex1; e2->edgePtr = NULL; if (e) e->edgePtr = e2; else graph[vertex2 - 1].edgePtr = e2; } void printGraph() { int i; struct edge *e; for (i = 0; i < vertexCount; i++) { printf("%d(%d)", i + 1, graph[i].vertexKey); e = graph[i].edgePtr; while (e) { printf("->%d", e->vertexIndex); e = e->edgePtr; } printf("\n"); } } void bfs() { graph[0].distance = 0; enqueue(graph[0]); while(q != NULL){ vertex u = dequeue(); while(u.edgePtr != NULL){ if(graph[u.edgePtr->vertexIndex - 1].distance == -1){ graph[u.edgePtr->vertexIndex - 1].distance = u.distance + 1; enqueue(graph[u.edgePtr->vertexIndex - 1]); } u.edgePtr = u.edgePtr->edgePtr; } } } void print_distances() { for (int i = 0; i < count; i++) { printf("%d %d\n", i + 1, graph[i].distance); } } void enqueue(vertex v) { queue* new = malloc(sizeof (queue)); new->next = NULL; new->v = v; if (q == NULL) { q = malloc(sizeof(queue)); q = new; } else { while (q->next != NULL) { q = q->next; } //add new node at the end q->next = new; } } vertex dequeue() { vertex v; queue* tempPtr; tempPtr = q; //makes temp the address of the node to be deleted v = tempPtr->v; q = q->next; //sets the new head as the address of the next node return v; }