c - 从单个节点到链表中的节点有多少条链接？

Question

在C中，我可以从一个节点编写单链、双链或任何4、5个链接。但是我可以制作一个像这样的结构，其中未指定节点的链接数量，即它必须动态添加新链接。如果在 C 中不可能，那么我在哪里可以？例如:节点“a”具有指向节点“b”、“c”、“d”、“e”和“f”的链接，而“b”仅具有指向“c”、“d”、“a”的链接。 。 像那样。所以没有指定链接的数量。希望您理解我的问题。

Answer 1

是的，通过为链接使用动态分配的数组。通常，您需要存储实际链接数量 (count) 以及动态分配的链接指针数量 (maxcount):

struct node {
    size_t        maxcount;
    size_t        count;
    struct node **child;
    /* Plus node data or other properties */
};

如果每个链接(或边)都有关联的权重，您可以使用

struct node;

struct edge {
    struct node *target;
    double       weight;
};

struct node {
    size_t       maxcount;
    size_t       count;
    struct edge *edges;

    /* Visited flag, for full graph traversal */
    int          visited;

    /* Node data; here, name, as a C99 flexible array member */
    char         name[];
};

<小时/>

请注意，Graphviz 是可视化此类图表的出色工具。我定期编写测试以在输出上生成 DOT 语言图定义，以便我可以使用例如来自 Graphviz 的 dot 将它们绘制为漂亮的图表。

如果您有一个使用上面的结构边和结构节点的有向图，并且所有visited字段都清除为零，您可以安全地 - - 也就是说，不会陷入循环 - 使用递归辅助函数为这样的图创建 DOT 输出，例如

static void write_dot_node(struct node *graph, FILE *out)
{
    size_t  i;

    if (graph->visited)
        return;

    graph->visited = 1;

    fprintf(out, "\tnode%p [ label=\"%s\" ];\n", graph, graph->name);

    for (i = 0; i < graph->count; i++) {
        write_dot_node(graph->edges[i].target, out);
        fprintf(out, "\tnode%p -> node%p [ taillabel=\"%.3f\" ];\n",
                     graph, graph->edges[i].target,
                     graph->edges[i].weight);
    }
}

void write_dot(struct node *graph, FILE *out)
{
    if (!graph || !out)
        return;

    fprintf(out, "digraph {\n");
    write_dot_node(graph, out);
    fprintf(out, "}\n");
}

如果您有真正巨大的图表，则在某些情况下上述内容可能会递归得太深。然后需要将其转换为使用尚未访问的节点的显式堆栈的非递归循环，并使用 write_dot 函数初始化并丢弃堆栈:

#define  VISITED_STACKED (1<<0)
#define  VISITED_VISITED (1<<1)

int write_dot(struct node *graph, FILE *out)
{
    struct node **unseen = NULL, **temp;
    size_t        unseens = 1;
    size_t        unseens_max = 1024; /* Initial stack size */

    unseen = malloc(unseens_max * sizeof *unseen);
    if (!unseen) {
        errno = ENOMEM;
        return -1;
    }
    unseen[0] = graph;

    fprintf(out, "digraph {\n");

    while (unseens > 0) {
        struct node *curr = unseen[--unseens];
        size_t       i, n;

        /* Already visited (since pushed on stack)? */
        if (curr->visited & VISITED_VISITED)
            continue;
        else
            curr->visited |= VISITED_VISITED;

        fprintf(out, "\tnode%p [ label=\"%s\" ];\n", curr, curr->name);

        for (i = 0, n = 0; i < curr->count; i++) {
            /* Count unvisited child nodes */
            n += !(curr->edges[i].target->visited & VISITED_STACKED);

            fprintf(out, "\tnode%p -> node%p [ taillabel=\"%.3f\" ];\n",
                    curr, curr->edges[i].target, curr->edges[i].weight);
        }

        if (n + unseens > unseens_max) {
            if (n + unseens > 1048576)
                unseens_max = ((n + unseens) | 1048575) + 1048573;
            else
            if (n + unseens < 2 * unseens_max)
                unseens_max = 2 * unseens_max;
            else
                unseens_max = 2 * (n + unseens);

            temp = realloc(unseen, unseens_max * sizeof *unseen);
            if (!temp) {
                free(unseen);
                errno = ENOMEM;
                return -1;
            } else
                unseen = temp;
        }

        /* Add unvisited child nodes to stack. */
        for (i = 0; i < curr->count; i++)
            if (!(curr->edges[i].target->visited & VISITED_STACKED)) {
                curr->edges[i].target->visited |= VISITED_STACKED;
                unseen[unseens++] = curr->edges[i].target;
            }
    }

    free(unseen);

    fprintf(out, "}\n");

    return 0;
}

在这种情况下，VISITED_STACKED 位掩码表示该节点已添加到堆栈中以供稍后处理，而 VISITED_VISITED 位掩码表示该节点已被处理。

<小时/>

正如 Ovanes 在对此答案的评论中指出的那样，对于非常密集的图形，您可以使用 c++映射或哈希表，特别是当您经常需要找出某对节点是否共享边时。在这种情况下，您可以使用目标指针的可选哈希表来扩充上述结构。

只是为了好玩，我使用接口(interface) digraph.h 在实践中测试了具有每个图用户指定的重新分配大小函数和散列函数的有向加权图:

#ifndef   DIGRAPH_H
#define   DIGRAPH_H
#include <stdlib.h>
#include <stdio.h>

struct digraph_node;

struct digraph_edge {
    struct digraph_edge  *hash_next;        /* Hash table slot chain */
    size_t                hash_code;        /* Hash value */
    struct digraph_node  *target;           /* Target edge of the node */
    double                weight;           /* Weight of this edge */
};

struct digraph_node {
    struct digraph_node  *hash_next;        /* Hash table slot chain */
    size_t                hash_code;        /* Hash value */
    struct digraph_edge  *edge;             /* Array of edges */
    size_t                edges;            /* Number of edges in this node */
    size_t                edges_max;        /* Number of edges allocated for */
    struct digraph_edge **hash_slot;        /* Optional edge hash table */
    size_t                hash_size;        /* Size of optional edge hash table */
    char                  name[];           /* Name of this node */
};

typedef struct {
    struct digraph_node **node;             /* Array of pointers to graph nodes */
    size_t                nodes;            /* Number of nodes in this graph */
    size_t                nodes_max;        /* Number of nodes allocated for */
    struct digraph_node **hash_slot;        /* Optional node hash table */
    size_t                hash_size;        /* Size of optional node hash table */
    /* Graph resize policy and hash function */
    size_t (*graph_nodes_max)(size_t nodes);
    size_t (*graph_hash_size)(size_t nodes);
    size_t (*graph_hash_func)(const char *name);
    /* Node resize policy and hash function */
    size_t (*node_edges_max)(size_t edges);
    size_t (*node_hash_size)(size_t edges);
    size_t (*node_hash_func)(struct digraph_node *target);
} digraph;

void digraph_init(digraph *graph);
void digraph_free(digraph *graph);

struct digraph_node *digraph_find_node(digraph *graph, const char *name);
struct digraph_edge *digraph_find_edge(digraph *graph, struct digraph_node *source, struct digraph_node *target);

struct digraph_node *digraph_add_node(digraph *graph, const char *name);
struct digraph_edge *digraph_add_edge(digraph *graph, struct digraph_node *source, struct digraph_node *target, double weight);

int digraph_dot(digraph *graph, FILE *out);

size_t digraph_default_graph_nodes_max(size_t nodes);
size_t digraph_default_graph_hash_size(size_t nodes);
size_t digraph_default_graph_hash_func(const char *name);
size_t digraph_default_node_edges_max(size_t edges);
size_t digraph_default_node_hash_size(size_t edges);
size_t digraph_default_node_hash_func(struct digraph_node *target);

#define  DIGRAPH_INIT  { NULL, 0, 0,                        \
                         NULL, 0,                           \
                         digraph_default_graph_nodes_max,   \
                         digraph_default_graph_hash_size,   \
                         digraph_default_graph_hash_func,   \
                         digraph_default_node_edges_max,    \
                         digraph_default_node_hash_size,    \
                         digraph_default_node_hash_func     \
                       }

#endif /* DIGRAPH_H */

为简单起见，digraph_add_node() 和 digraph_add_edge() 函数始终设置 errno；如果成功，则返回 0；如果这样的节点或边已存在，则返回 EEXIST；否则返回错误代码。如果节点或边已存在，则函数会返回现有节点或边(但将 errno 设置为 EEXIST 而不是 0)。这使得添加新边变得非常容易。

在运行 Intel Core i5-6200U 处理器的 64 位 Linux 的笔记本电脑上，大约需要 18 秒才能生成 5,000 个随机节点、12,500,000 个随机边(每条边 2,500 个节点)，并使用 GraphViz 点语言描述整个图。这对我来说足够快了，因为我没有任何工具来可视化这些图表；就连 Graphviz 都被这些完全噎住了。

请注意，由于图结构包含指向图中每个节点的指针数组，因此使用上述结构不需要递归:

int digraph_dot(digraph *graph, FILE *out)
{
    size_t  i, k;

    if (!graph)
        return errno = EINVAL;

    if (!out || ferror(out))
        return errno = EIO;

    fprintf(out, "digraph {\n");

    /* Describe all nodes. */
    for (i = 0; i < graph->nodes; i++)
        if (graph->node[i])
            fprintf(out, "\tnode%p [label=\"%s\"];\n",
                         (void *)graph->node[i], graph->node[i]->name);

    /* Describe all edges from all nodes. */
    for (i = 0; i < graph->nodes; i++)
        if (graph->node[i]) {
            if (graph->node[i]->edges) {
                for (k = 0; k < graph->node[i]->edges; k++)
                    fprintf(out, "\tnode%p -> node%p [taillabel=\"%.3f\"];\n",
                                 (void *)(graph->node[i]),
                                 (void *)(graph->node[i]->edge[k].target),
                                 graph->node[i]->edge[k].weight);
            } else {
                fprintf(out, "\tnode%p;\n", (void *)(graph->node[i]));
            }
        }

    fprintf(out, "}\n");

    if (fflush(out))
        return errno;
    if (ferror(out))
        return errno = EIO;

    return errno = 0;
}

当然，如果你有那么密集的图，每个节点平均有一条到图中其他一半节点的边，一个权重矩阵(为没有边保留零权重，或者一个单独的 bool 矩阵描述哪些边确实存在)会更有意义，并且也会有更好的缓存局部性。

当矩阵以行优先顺序存储时(例如，如果您在 C 中定义二维数组)，则每一行对应一个源节点，每一列对应一个目标节点是有意义的，以便描述来自一个节点的边和/或权重的 vector 在内存中是连续的。检查从特定源节点向外定向的边比检查定向到特定目标节点的边更为常见；因此，更常见的情况是拥有更好的缓存局部性应该有助于提高整体性能。