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

标签 c queue breadth-first-search

我正在尝试使用邻接表来计算源顶点到其他顶点的距离。我正在使用队列来完成此操作，但是我将除源之外的每个顶点的距离设为 -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;
}

最佳答案

我已经弄清楚了，基本上我的队列实现很糟糕并且出队没有清除队列，而且这个 while(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;
}

关于c - 使用 BFS 计算源和顶点之间的距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35907198/

上一篇：c - 绘制椭圆时来自 sqrt() 的 "Domain error"？

下一篇：C++ uint64_t 按位与检查偶数

相关文章：

将 float 数组转换为 char 缓冲区

algorithm - 修改福特富尔克森算法的bfs，寻找增广路径

c++ - 如何在 C++ 中跟踪 BFS 深度

c++ - 在树上应用 bfs 以找到两个顶点之间的最长路径

c++ - C strcpy导致段错误

c - 为什么在 C 中调用函数时允许传递的参数数量不足？

c - 初始化结构数组 - C 代码错误

java - Java中有没有办法让事件带有变量？里面的例子

php - file_get_contents 不起作用？

python - 了解 python 中的 Queue 模块(如何运行它)

©2024 IT工具网  联系我们