使用邻接表创建图

问题描述 投票：0回答：1

我正在遵循Skiena的算法设计手册v3。

我看到有几个问题说书中有某些错别字，我不确定这是一个还是只是因为我看不懂。

考虑以下因素：

typedef struct edgenode {
    int y;                   /* adjacency info */
    int weight;              /* edge weight, if any */
    struct edgenode *next;   /* next edge in list */
} edgenode;

typedef struct {
    edgenode *edges[MAXV+1];  /* adjacency info */
    int degree[MAXV+1];       /* outdegree of each vertex */
    int nvertices;            /* number of vertices in the graph */
    int nedges;               /* number of edges in the graph */
    int directed;             /* is the graph directed? */
} graph;

void insert_edge(graph *g, int x, int y, bool directed) {
    edgenode *p;        /* temporary pointer */

    p = malloc(sizeof(edgenode));    /* allocate edgenode storage */

    p->weight = 0;
    p->y = y;
    p->next = g->edges[x];

    g->edges[x] = p;    /* insert at head of list */

    g->degree[x]++;

    if (!directed) {
        insert_edge(g, y, x, true);
    } else {
        g->nedges++;
    }
}

据我了解，

void insert_edge(graph *g, int x, int y, bool directed)
通过将数组索引
x
和
y
处的两个节点添加到
edges
数组来连接它们。

以下片段让我感到困惑：

p->y = y;
p->next = g->edges[x];

g->edges[x] = p;    /* insert at head of list */

这是如何运作的？假设我的输入是 

x = 3, y = 4
，这是第一个输入。

对于有向图，我期望类似 

3 -> 4
的东西。

  1. p->y = y;
    非常有道理，
    x
    的邻接点是 
    y
    。
  2. p->next = g->edges[x];
    但是 
    edges
    数组被初始化为 null。这不会使 
    3.next == NULL
    而不是 
    3.next == 4
    吗？
  3. g->edges[x] = p;
    什么？ 
    edges[x] == x Node
    ，这让我很困惑。

完整的代码可以在graph.c和graph.h找到。

我认为 

p.next = y;
不知何故，并且 
y.next = NULL
截至目前，即第一次插入。也许这是我生锈的 C，但需要一些帮助。

c algorithm graph graph-theory
1个回答
0
投票

据我了解，

insert_edge
通过将数组索引x和y处的两个节点添加到
edges
数组来连接它们。

我不会称之为“添加到 

edges
数组”，因为 
edges
数组具有固定长度，并且每个 node 有一个条目（而不是每个 edge）。

edges
的索引标识边的“起始”顶点，
y
的 
edgenode
字段标识同一条边的相应“到”顶点。

对于每个顶点

x
，此代码维护一个边链接列表（不是
edges
，而是
edges[x]
），该列表最初为空。

让我们以示例图为例：

...初始化后，其边缘填充如下：

insert_edge(g, 0, 1, true); 
insert_edge(g, 0, 2, true); 
insert_edge(g, 1, 2, true); 
insert_edge(g, 2, 3, true); 
insert_edge(g, 3, 4, true);

让我们看看它如何填充 

graph
数据结构。我们从 
g
的状态开始（我假设 
MAXV
为 4）：

    ┌───────────┬────┬────┬────┬────┬────┐    
g ─►│ edges     │  - │  - │  - │  - │  - │
    ├───────────┼────┼────┼────┼────┼────┤
    │ degree    │  0 │  0 │  0 │  0 │  0 │
    ├───────────┼────┼────┴────┴────┴────┘
    │ nvertices │  5 │ 
    ├───────────┼────┤
    │ nedges    │  0 │
    ├───────────┼────┤
    │ directed  │true│
    └───────────┴────┘

连字符代表 

nullpointer
值。我假设所有这些都已正确初始化。

然后 

insert_edge(g, 0, 1, true)
将创建一个 
p
节点，该节点被分配并初始化为：

    ┌────────┬────┐
p ─►│ weight │  0 │
    ├────────┼────┤
    │ y      │  1 │
    ├────────┼────┤
    │ next   │  - │
    └────────┴────┘

值得注意的是 

next
字段是 
nullptr
，因为这是在 
g->edges[0]
处找到的值。

然后下一个语句

g->edges[x] = p
建立链接，并且在两个计数器递增之后，该函数完成其工作：

                      ┌────────┬────┐
                  p ─►│ weight │  0 │
                      ├────────┼────┤
                      │ y      │  1 │
                      ├────────┼────┤
                   ┌─►│ next   │  - │
                   │  └────────┴────┘
                   │
                   │
                   │
                   │
    ┌───────────┬──│─┬────┬────┬────┬────┐    
g ─►│ edges     │  ┴ │  - │  - │  - │  - │
    ├───────────┼────┼────┼────┼────┼────┤
    │ degree    │  1 │  0 │  0 │  0 │  0 │
    ├───────────┼────┼────┴────┴────┴────┘
    │ nvertices │  5 │ 
    ├───────────┼────┤
    │ nedges    │  1 │
    ├───────────┼────┤
    │ directed  │true│
    └───────────┴────┘

现在我们来看看更有趣的：

insert_edge(g, 0, 2, true);
。 
p
再次指向新的
edgenode
，但这次
g->edges[0]
不是
nullptr
，因此
p->next
将指向之前添加的
edgenode
。 
insert_edge
完成后，我们得到：

                      ┌────────┬────┐  ┌────────┬────┐
                  p ─►│ weight │  0 │  │ weight │  0 │
                      ├────────┼────┤  ├────────┼────┤
                      │ y      │  2 │  │ y      │  1 │
                      ├────────┼────┤  ├────────┼────┤
                   ┌─►│ next   │  ────►│ next   │  - │
                   │  └────────┴────┘  └────────┴────┘
                   │
                   │
                   │
                   │
    ┌───────────┬──│─┬────┬────┬────┬────┐    
g ─►│ edges     │  ┴ │  - │  - │  - │  - │
    ├───────────┼────┼────┼────┼────┼────┤
    │ degree    │  2 │  0 │  0 │  0 │  0 │
    ├───────────┼────┼────┴────┴────┴────┘
    │ nvertices │  5 │ 
    ├───────────┼────┤
    │ nedges    │  2 │
    ├───────────┼────┤
    │ directed  │true│
    └───────────┴────┘

对于其他边也是如此：每次新的 

edgenode
都会被添加到一个链表中，该链表的头指针存储在 
edges
数组中。我们有 5 个链表：每个顶点一个。

这是上面示例的最终结果：

                      ┌────────┬────┐  ┌────────┬────┐
                      │ weight │  0 │  │ weight │  0 │
                      ├────────┼────┤  ├────────┼────┤
                      │ y      │  2 │  │ y      │  1 │
                      ├────────┼────┤  ├────────┼────┤
                   ┌─►│ next   │  ────►│ next   │  - │
                   │  └────────┴────┘  └────────┴────┘
                   │       ┌────────┬────┐  ┌────────┬────┐
                   │       │ weight │  0 │  │ weight │  0 │
                   │       ├────────┼────┤  ├────────┼────┤
                   │       │ y      │  4 │  │ y      │  2 │
                   │       ├────────┼────┤  ├────────┼────┤
                   │    ┌─►│ next   │  ────►│ next   │  - │
                   │    │  └────────┴────┘  └────────┴────┘
                   │    │       ┌────────┬────┐
                   │    │       │ weight │  0 │
                   │    │       ├────────┼────┤
                   │    │       │ y      │  3 │
                   │    │       ├────────┼────┤
                   │    │    ┌─►│ next   │  - │
                   │    │    │  └────────┴────┘
                   │    │    │       ┌────────┬────┐
                   │    │    │       │ weight │  0 │
                   │    │    │       ├────────┼────┤
                   │    │    │       │ y      │  4 │
                   │    │    │       ├────────┼────┤
                   │    │    │    ┌─►│ next   │  - │
                   │    │    │    │  └────────┴────┘
    ┌───────────┬──│─┬──│─┬──│─┬──│─┬────┐    
g ─►│ edges     │  ┴ │  ┴ │  ┴ │  ┴ │  - │
    ├───────────┼────┼────┼────┼────┼────┤
    │ degree    │  2 │  2 │  1 │  1 │  0 │
    ├───────────┼────┼────┴────┴────┴────┘
    │ nvertices │  5 │ 
    ├───────────┼────┤
    │ nedges    │  6 │
    ├───────────┼────┤
    │ directed  │true│
    └───────────┴────┘

希望这能澄清这一点。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.