时间戳

首页 > 解决方案 > 图的邻接列表表示不打印相邻节点。为什么？

c - 图的邻接列表表示不打印相邻节点。为什么？

问题描述

在这个邻接列表程序中，相邻的节点没有正确显示。插入函数或函数中可能有错误display。每个节点都有一个边列表，但在显示图形时不打印边列表。它可能在某个地方出现错误。
我不知道它在哪里。这可能是语义错误。

//邻接表表示的实现

#include<stdio.h>
#include<stdlib.h>

#define maxnodes 50

typedef struct node
{
    int data;
    struct node *link;    
}graph;

//inserting edge list for each node
void insert_node(graph **node_p,int i,int j)
{
    graph *temp;
    temp=(graph *)malloc(sizeof(graph));
    temp->data=j;
    temp->link=node_p[j];
    node_p[j]=temp;
}

void create_graph(graph **nodep)
{
    int i,j;
    while(1)
    {
        printf("enter source and destination nodes");
        scanf("%d %d",&i,&j);
        if(i==0 && j==0)
            break;
        insert_node(nodep,i,j);   
    }
}

void display(graph **nodep,int n)
{
    int i;
    graph *cur;
    for(i=1;i<=n;i++)
    {
        cur=nodep[i];
        printf("\n the nodes adjacent to node %d are=",i);
        while(cur!=NULL)
        {
          printf("\t%d",cur->data); 
          cur=cur->link; 
        }
    }
}

int main()
{
    int i;
    int n,ch;
    graph *nodelist[maxnodes];
    printf("enter number of number of nodes in the graph");
    scanf("%d",&n);

    for(i=1;i<=n;i++)
        nodelist[i]=NULL;

    while(1)
    {
        printf("\nenter option 1.create graph 2.display 3.exit");
        scanf("%d",&ch);
        switch(ch)
        {
           case 1:create_graph(nodelist);
                  break;
           case 2:display(nodelist,n);
                  break;
           case 3:exit(0); 
                   break; 
          default:
                 break;
        }
    }    
}

标签： c

解决方案

你的函数内部的逻辑insert_node()是完全错误的。

假设您正在构建一个无向图，如果用户输入 pair i, j，您必须将 node 推送到 nodei的邻接列表，j并将 node推送到jnode的邻接列表i。

另一个主要错误是，您总是将新创建的节点附加到temp另一个节点的邻接列表的第一个元素中，这仅在另一个节点的邻居列表为空的情况下才是正确的。你首先要检查if(node_p[i] == NULL)。如果是这样，您可以直接将 附加temp到 that node_p[i]，否则您必须遵循links 才能到达邻接列表的最后一个元素并附加到temp那里。

修改后的代码如下

void insert_node(graph **node_p,int i,int j)
    {
        /* Add j to adj list of i */
        graph *temp;
        temp=(graph *)malloc(sizeof(graph));
        temp->data=j;
        temp->link=NULL;

        if(node_p[i] == NULL) /* First Node */
            node_p[i]=temp;
        else
        {
            graph *loc;
            loc = node_p[i];
            while(loc->link != NULL)
                loc = loc->link;
            loc->link = temp;
        }
        
        /*** COMMENT THIS PORTION IF THE GRAPH IS DIRECTED ***/
        /* Add i to adj list of j */
        graph *temp1;
        temp1 = (graph *)malloc(sizeof(graph));
        temp1->data = i;
        temp1->link = NULL;

        if(node_p[j] == NULL) /* First Node */
            node_p[j]=temp1;
        else
        {
            graph *loc;
            loc = node_p[j];
            while(loc->link != NULL)
                loc = loc->link;
            loc->link = temp1;
        }
    }

如果您正在构建有向图，即，i -> j而不是j -> i，请注释掉代码的后半部分/* Add i to adj list of j */.

使用这个。我在下图的 5 个节点的图中得到了这个输出，这些节点的边是 ={1-2, 1-5, 1-3, 2-4}

enter number of number of nodes in the graph5

enter option 1.create graph 2.display 3.exit 1
enter source and destination nodes 1 2
enter source and destination nodes 1 5
enter source and destination nodes 1 3
enter source and destination nodes 2 4
enter source and destination nodes 0 0

enter option 1.create graph 2.display 3.exit 2

 the nodes adjacent to node 1 are=  2   5   3
 the nodes adjacent to node 2 are=  1   4
 the nodes adjacent to node 3 are=  1
 the nodes adjacent to node 4 are=  2
 the nodes adjacent to node 5 are=  1
enter option 1.create graph 2.display 3.exit3

推荐阅读