图的邻接表表示不正确

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( sizeof( struct grnode*))分配了一个指针和returns给你一个指向分配指针的指针。如果你不使用它作为指向指针的指针，就像你不这样做，那么你有 undefined behavior.

我怀疑你真的想要malloc( sizeof( struct grnode))。

顺便说一句，in C you should not cast the result of malloc。在 C++ 中你不应该使用 malloc 无论如何。

Answer 2

除了分配问题，您的数据组织也需要重新考虑。

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

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

这意味着您无法访问新数据（以后也不能 free）。这就像买了房子然后扔掉了钥匙。足以说明：

temp = &graph->adj[n];

当您使用指针时，请记住：指针应该指向有效数据，或者它应该是 NULL。分配内存时，不要更改该内存的句柄，并确保稍后通过该句柄free它。

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

描述邻接有多种方式。您可以在图形中添加一个矩阵，也可以制作一个边缘结构来保存两个连接节点并按图形组织。或者你可以为每个节点创建一个链接列表。选择一个。

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

编辑基于您使用链表表示连接的主要想法，我在下面为单向图实现了一个简单的框架。您可以看到每个 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;
}

图的邻接表表示不正确

Incorrect adjacency list representation of a graph

c

c++

graph

adjacency-list