c++ - 图的邻接列表表示不正确

Question

我正在尝试使用图的邻接列表表示来表示图。我的代码编译正确但显示不正确的结果，我似乎找不到逻辑我的代码不一致。这是输入和输出示例

Enter the number of Vertices 
 4

Enter the number of Edges
 6

输入边缘

0 1

1 2

2 3

3 0

0 2

1 3

顶点0的邻接表 头 -> 0-> 2

顶点1的邻接表 头 -> 1-> 3

顶点2的邻接表 头 -> 2

顶点3的邻接表 头 -> 3

请注意，0 也连接到 1

2 也连接到 1 和 0

struct grnode {

long long num;
struct grnode *next;
};

struct graph {

long long v;
long long e;
struct grnode *adj;
};

struct graph *adjlistgr(){

long long i,x,y;
struct grnode *temp;
struct graph *g = (struct graph*)malloc(sizeof(struct graph));
if (!g) {
    printf("memory error");
    return;
}
// here we scanf  the num of vertices and edges
printf("Enter the number of Vertices \n");
scanf("%lld", &g->v);
printf("Enter the number of Edges\n");
scanf("%lld", &g->e);
g->adj = malloc(g->v*sizeof(struct grnode));
for (i = 0; i < g->v; i++)
{

    g->adj[i].num = i;
    g->adj[i].next = &g->adj[i];
}
printf("Enter the Edges\n");
for (i = 0; i < g->e;i++)
{   // now we scan the edges

    scanf("%lld %lld", &x,&y);

    temp = (struct grnode*)malloc( sizeof( struct grnode*));
    temp->num = y;
    temp->next = &g->adj[x];
    g->adj[x].next = temp;
    temp = (struct grnode*)malloc( sizeof( struct grnode*));
    temp->num = y;
    temp->next = &g->adj[y];
    g->adj[y].next = temp;
}return g;
}

 void printgraph(struct graph* graph)
{                   

int n;                         
for (n = 0; n < graph->v; ++n)               
{                                      
    // struct grnode *pCrawl = graph->adj[n].num;
    struct grnode *temp;
    temp = (struct grnode*)malloc( sizeof( struct grnode*));
    temp->next=&graph->adj[n];
    temp=temp->next;
    printf("\n Adjacency list of vertex %d\n head ", n);
    long long s=temp->num;
    do 
    {
        printf("-> %d", temp->num);
        temp = temp->next;
    }while(temp->num!=s);
    printf("\n");
}}    
  int main(){      
  struct graph *mylist=adjlistgr();          
  printgraph(mylist);    
}

Answer 1

除了分配问题之外，您的数据组织还需要重新思考。

您似乎对malloc也有误解。例如，您在打印函数内分配内存。该函数应该只检查数据然后打印它。分配是不必要的。在您的代码中，您立即覆盖已分配数据的句柄:

temp = (struct grnode*)malloc( sizeof( struct grnode*));
temp->next=&graph->adj[n];
temp=temp->next;

这意味着您将失去对新数据的访问权限(并且以后无法释放它)。这就像买了房子然后扔掉 key 一样。只要说:

temp = &graph->adj[n];

当您使用指针时，请记住:指针应该指向有效数据，否则应该为NULL。分配内存时，请勿更改该内存的句柄，并确保稍后通过该句柄释放它。

关于您的图表:您有四个节点。一旦初始化这些节点，它们就会被固定。您可以在它们之间添加边，但不能重复使用它们作为四个独立链表的元素来执行双重任务。这就是您的代码想要执行的操作。

有多种描述邻接的方法。您可以向图形中添加一个矩阵，也可以创建一个包含两个连接节点并按图形组织的边结构。或者您可以为每个节点创建一个连接的链表。选择一个。

要点是您的节点和边需要两个独立的数据结构。

编辑 基于您使用链表表示连接的主要思想，我在下面实现了一个简单的单向图框架。您可以看到每个 grnode 维护自己的 grconn 连接链表。该代码还展示了如何在使用内存后清理它。

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

struct grnode;
struct grconn;

struct grconn {                 /* Connection to node (linked list) */
    struct grnode *dest;
    struct grconn *next;
};

struct grnode {                 /* Node in graph */
    int id;
    struct grconn *conn;
};

struct graph {
    int nnode;
    struct grnode *node;
};



/*
 *      Create new connection to given node
 */
struct grconn *grconn_new(struct grnode *nd)
{
    struct grconn *c = malloc(sizeof(*c));

    if (c) {
        c->dest = nd;
        c->next = NULL;
    }

    return c;
}

/*
 *      Clean up linked list of connections
 */
void grconn_delete(struct grconn *c)
{ 
    while (c) {
        struct grconn *p = c->next;

        free(c);
        c = p;
    }
}

/*
 *      Print connectivity list of a node
 */
void grnode_print(struct grnode *nd)
{
    struct grconn *c;

    printf("%d:", nd->id);

    c = nd->conn;
    while (c) {
        printf(" %d", c->dest->id);
        c = c->next;
    }

    printf("\n");
}



/*
 *      Create new graph with given number of nodes
 */
struct graph *graph_new(int n)
{
    struct graph *g = malloc(sizeof(*g));
    int i;

    if (g == NULL) return g;

    g->nnode = n;
    g->node = malloc(n * sizeof(*g->node));
    if (g->node == NULL) {
        free(g);
        return NULL;
    }

    for (i = 0; i < n; i++) {
        g->node[i].id = i;
        g->node[i].conn = NULL;
    }

    return g;
}

/*
 *      Delete graph and all dependent data
 */
void graph_delete(struct graph *g)
{
    int i;

    for (i = 0; i < g->nnode; i++) {
        grconn_delete(g->node[i].conn);
    }

    free(g->node);
    free(g);
}

/*
 *      Print connectivity of all nodes in graph
 */
void graph_print(struct graph *g)
{
    int i;

    for (i = 0; i < g->nnode; i++) {
        grnode_print(&g->node[i]);
    }
}

/*
 *      Create one-way connection from node a to node b
 */
void graph_connect(struct graph *g, int a, int b)
{
    struct grnode *nd;
    struct grconn *c;

    if (a < 0 || a >= g->nnode) return;
    if (b < 0 || b >= g->nnode) return;

    nd = &g->node[a];
    c = grconn_new(&g->node[b]);

    c->next = nd->conn;
    nd->conn = c;
}

/*
 *      Create two-way connection between nodes a and b
 */
void graph_connect_both(struct graph *g, int a, int b)
{
    graph_connect(g, a, b);
    graph_connect(g, b, a);
}



/*
 *      Example client code
 */
int main()
{
    struct graph *g = graph_new(4);

    graph_connect_both(g, 0, 1);
    graph_connect_both(g, 1, 2);
    graph_connect_both(g, 2, 3);
    graph_connect_both(g, 0, 2);
    graph_connect_both(g, 1, 3);

    graph_print(g);

    graph_delete(g);

    return 0;
}