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

我试图使用邻接列表来计算从源顶点到其他顶点的距离。 我正在使用队列来完成这个,但是我得到除了源之外的每个顶点的距离为-1,但我不确定为什么会发生这种情况

#include  #include  #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 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 %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 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; } 

我已经弄明白了,基本上我的队列实现很可怕而且dequeue没有清除队列,同时这个while(q->next != NULL)不正确它应该是while(q != NULL)下面是正确的实现这个程序

 #include  #include  #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; } 

insertVertex(...) ,你调用graph[vertexCount].distance = -1;

您的代码很可能没有正确改变距离。 从我所看到的,你将u.edgePtr->vertexIndex设置为连接的第二个顶点的索引– 1 (在insertEdge(...) )。 这意味着您可能正在从人类可读索引(1,2,… n)转换为机器可读索引(0,1,… n-1)

bfs()你不应该第二次这样做! 我找不到任何理由设置graph[u.edgePtr->vertexIndex - 1].distance ,但我可能会弄错。 我重做了你的while循环。 试着把它放在bfs()

 while(u.edgePtr != NULL){ if(graph[u.edgePtr->vertexIndex].distance == -1){ graph[u.edgePtr->vertexIndex].distance = u.distance + 1; enqueue(q, graph[u.edgePtr->vertexIndex]); } 

我不确定为什么你的距离都没有改变,因为你的代码应该仍然影响index-1距离就好了。 尝试上面的修复,让我知道这是否足以捕获错误或是否可能有另一个。

你有一般的想法。 以下是一些简化代码的方法

  • 使用固定大小的基于arrays的队列。 256的大小是理想的,因为无符号整数索引将自动翻转。 权衡:简单的代码,但在任何给定时间队列中不超过255个项目。
  • 使用边数组。 权衡:易于实现边缘数组,但需要进行O(E)搜索以找到源自任何给定顶点的边缘。
  • 使用距离来跟踪节点是否已被访问过。 负距离意味着未访问顶点。 权衡:对我来说似乎是一个双赢,更简单的代码,更少的空间,没有额外的时间。
  • 使用顶点ID定位顶点数组中的顶点。 权衡:防止格式错误的边缘崩溃您的程序,但需要O(V)搜索才能找到顶点。

这是简化的代码。 我将它作为练习留给读者根据需要优化速度代码和/或删除队列限制。

 #include  #include  struct Vertex { int id; int distance; }; struct Queue { uint8_t head; uint8_t tail; void *data[256]; }; int main( void ) { int edge[][2] = { {2,3}, {1,4}, {1,3}, {3,4}, {4,5}, {0,0} }; struct Vertex vertex[] = { {1,0}, {2,-1}, {3,-1}, {4,-1}, {5,-1}, {0,0} }; struct Queue q = { 0, 0 }; q.data[q.head++] = &vertex[0]; while ( q.tail != q.head ) { struct Vertex *src = q.data[q.tail++]; for ( int i = 0; edge[i][0] > 0; i++ ) for ( int j = 0; j < 2; j++ ) if ( edge[i][j] == src->id ) { int destID = edge[i][(j+1)%2]; struct Vertex *dest; for ( dest = vertex; dest->id > 0; dest++ ) if ( dest->id == destID ) break; if ( dest->distance < 0 ) { dest->distance = src->distance + 1; q.data[q.head++] = dest; } } } for ( int i = 0; vertex[i].id > 0; i++ ) printf( "Vertex %d is at distance %d\n", vertex[i].id, vertex[i].distance ); } 
Interesting Posts