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

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

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

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

3 个解决方案

#1

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

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

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

#2

In insertVertex(...), you call graph[vertexCount].distance = -1;.

在insertVertex(...)中,您调用graph [vertexCount] .distance = -1;。

It is very likely that your code isn't changing distance properly. From what I can see, you set u.edgePtr->vertexIndex to the index of the second vertex connected - 1 (in insertEdge(...)). This means you're probably converting from human-readable indexes (1, 2, ... n) into machine-readable indexes (0, 1, ... n-1)

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

In bfs() you shouldn't need to do this a second time! I couldn't find any reason to set graph[u.edgePtr->vertexIndex - 1].distance, but I could be mistaken. I've redone your while loop. Try putting this in bfs():

在bfs()中你不应该第二次这样做!我找不到任何理由设置图[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]);
       } 

I'm not sure why none of your distances are changing, because your code should still be affecting the distances at index-1 just fine. Try the fix above and let me know if that was enough to catch the bug or if there might be another one.

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

#3

You have the general idea. Here are some ways to simplify the code

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

• Use an array based queue with fixed size. The size 256 is ideal since the unsigned integer indexes will roll over automatically. Trade-off: simple code but no more than 255 items in the queue at any given time.

使用固定大小的基于阵列的队列。 256的大小是理想的,因为无符号整数索引将自动翻转。权衡:简单的代码,但在任何给定时间队列中不超过255个项目。

• Use an array of edges. Trade-off: easy to implement the edge array, but takes an O(E) search to find the edges that originate from any given vertex.

使用边数组。权衡:易于实现边缘数组,但需要进行O(E)搜索以找到源自任何给定顶点的边缘。

• Use the distance to keep track of whether a node has been visited. A negative distance means that the vertex has not been visited. Trade-off: seems like a win-win to me, simpler code, less space, no extra time.

使用距离来跟踪节点是否已被访问过。负距离意味着未访问顶点。权衡:对我来说似乎是一个双赢,更简单的代码,更少的空间,没有额外的时间。

• Use the vertex ID to locate a vertex in the vertex array. Trade-off: prevents a malformed edge from crashing your program, but requires an O(V) search to find the vertex.

使用顶点ID定位顶点数组中的顶点。权衡:防止格式错误的边缘崩溃您的程序,但需要O(V)搜索才能找到顶点。

Here's the simplified code. I leave it as an exercise for the reader to optimize the code for speed and/or remove the queue limit, as desired.

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

#include <stdio.h>
#include <stdint.h>

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 );
}