首页 / 技术问答 / C++问答列表 / 问答详情

C++ 使用邻接表创建图

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

我看到书中有几个问题，说有typos个，我不确定这是一个，还是因为我看不懂.

请考虑以下事项:

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处的两个 node 添加到edges数组来连接这两个 node .

下面的代码片段让我感到困惑:

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数组被初始化为空.这不会是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个，也就是第一个插入.也许是我Rust 的C，但在这方面需要一些帮助.

推荐答案

据我所知，insert_edge通过将数组索引x和y处的两个 node 添加到edges数组来连接这两个 node .

我不会称之为"添加到edges数组"，因为edges数组有固定的长度，并且每个node都有一个条目(而不是每个edge).

索引edges标识边的"From"顶点，而AN edgenode的y字段标识同一条边的对应"To"顶点.

对于每个顶点x，此代码维护一个边的链接列表(不是edges，而是edges[x])，该列表最初将为空.

让我们对一个示例图执行此操作:

enter image description here

...在初始化后使用其边填充，如下所示:

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数据 struct 的.我们从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 node ，该 node 被分配和初始化为:

    ┌────────┬────┐
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│
    └───────────┴────┘

希望这能澄清这一点.

C++相关问答推荐

exit(EXIT_FAILURE)：Tcl C API类似功能

在struct中调用函数，但struct在void中 *

在一个小型玩具项目中实现终端历史记录功能

为什么删除CAP_DAC_OVERRIDE后创建文件失败？

仅在给定的大小和对齐方式下正确创建全局

如何使用C for Linux和Windows的标准输入与gdb/mi进行通信？

防止C++中递归函数使用堆栈内存

从TCP连接启动UDP(C套接字)

C将数组传递给函数以修改数组

用C++高效解析HTTP请求的方法

在C中使用无符号整数模拟有符号整数

将size_t分配给off_t会产生符号转换错误

Leet代码运行时错误：代码不会在Leet代码上编译，而是在其他编译器中编译，如netbeans和在线编译器

通过char*访问指针的对象表示是未定义的行为吗？

"；错误：寄存器的使用无效；当使用-masm＝intel；在gcc中，但在AT&；T模式

C 程序不显示任何输出，但它接受 CS50 Lab1 的输入问题

C 语言中 CORDIC 对数的问题

无法将字符串文字分配给 C 中的字符数组

clion.我无法理解 Clion 中发生的 scanf 错误

使用 SDL2 的 C 程序中的内存泄漏

实用课程推荐
相关教程推荐
休闲君评测 |  TOOLFK工具网 |  chrome插件网 |  古诗文网 |  良许Linux教程网 |  Python之禅 |  红色石头 |  豪评测 |  入党申请书 | 

© 2020 Hi LearnFk 意见反馈 免责声明 关于我们 桂ICP备11002319号-3 友链&广告位+QQ: 1963612630