C语言中使用BFS查找节点之间的路径

Question

我是 C 语言的新手，在使用 Java 之后，我更难使用指针了我试图编写一段代码，使用广度优先搜索在图中的两个节点之间查找路径（不一定是最小值）。这是我的代码：

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 200

void push(int a);
int  pop(void);
void bfs(int a,int b,int len);
int nextnode(int a);

typedef struct node{
    int data;
    struct node* next;
}node;

int res[MAXSIZE];
int visited[MAXSIZE];
int rear,front;
node* graph[MAXSIZE];
int len;


int path[MAXSIZE];


int nextnode(int a)
{

    if(graph[a]==NULL)
        return -1;
    else
    {

        struct node* c=graph[a];
        while(visited[c->data]!=1 && c!=NULL)
        {
            c=c->next;
        }
        if(c==NULL)
            return -1;
        else
            return c->data;

    }
}

void push(int a)
{
    path[rear]=a;
    rear++;
}
int pop()
{
    if(front==rear)
        return -1;
    int num=path[front];
    front++;
    return num;
}

int main()
{
    rear=0;
    len=0;
    front=0;
    int n,e;
    int i,a,b;
    printf("%s\n%s", "Inputting Graph... ","Enter number of nodes and edges: ");
    scanf("%d %d",&n,&e);
    printf("%s %d %s\n", "Graph Created with",n,"nodes without any edge.");
    printf("%s\n","Enter the edges in 1 2 format if an edge exist from Node 1 to Node 2" );
    for(i=1;i<=n;i++)
    {
        graph[i]=NULL;
        visited[i]=0;
    }
    struct node* new = (struct node*)malloc(sizeof(struct node));
    for(i=0;i<e;i++)
    {
        scanf("%d %d",&a,&b);
        new->data=b;
        new->next=NULL;
        struct node* curr=graph[a];
        if(curr==NULL)
        {
            graph[a]=new;
        }
        else
        {
            while(curr->next!=NULL)
            {
                curr=curr->next;
            }
            curr->next=new;
        }
    }

    printf("%s\n", "Graph Created Successfully.");
    printf("%s", "Enter the node numbers between which the path is to be found between:  ");
    scanf("%d %d",&a,&b);
    bfs(a,b,0);
    printf("Length is %d\n",len);
    for(i=1;i<=len;i++)
    {
        printf("%d\n",res[len]);
    }

}

void bfs(int a,int b,int len)
{
    int c;
    visited[a]=1;
    int flag=0;

    while(a!=-1)
    {
        c=nextnode(a);
        while(c!=-1)
        {
            c=nextnode(a);
            if(c==b)
            {
                flag=1;
                break;
            }
            push(c);
            visited[c]=1;
        }
        len++;
        res[len]=a;
        if(flag==1)
        {
            res[len]=b;
            break;
        }
        a=pop();
    }
}

我知道它很大，但请介意看一遍。我遇到的问题是在输入所有值之后和 dfs() 函数调用之前出现分段错误！请帮助。

为了理解：我使用了列表数组。每个数组索引表示一个节点，列表表示它连接到的所有边。例如：如果我的图有 1->2、1->3、2-3 条边； graph[1] 将有一个列表 2->3->NULL。而图 [2] 将有 3->NULL.

谢谢。

编辑正如 Aditi 所指出的，错误出在 while 循环的 nextnode 函数运行行中。将代码更改为

后

        while(c != NULL && visited[c->data] == 1 )

程序运行完美无缺。谢谢！

Answer 1

我认为你要做的不是 graph[i] = NULL 而是 graph[i]->next = NULL

C语言中使用BFS查找节点之间的路径

Finding path between nodes using BFS in C language

c

segmentation-fault

graph-theory

breadth-first-search

path-finding