使用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("%sn%s", "Inputting Graph... ","Enter number of nodes and edges: ");
    scanf("%d %d",&n,&e);
    printf("%s %d %sn", "Graph Created with",n,"nodes without any edge.");
    printf("%sn","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("%sn", "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 %dn",len);
    for(i=1;i<=len;i++)
    {
        printf("%dn",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指出的那样，错误是在nextNode函数while循环的线路中。将代码更改为

之后

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

该程序完美地运行。谢谢！

Answer 1

我认为您要做的不是图[i] = null，而是图[i] -> next = null