代码之家  ›  专栏  ›  技术社区  ›  Alessandro Picardi

有人能给我解释一下这个结构吗?

  •  -3
  • Alessandro Picardi  · 技术社区  · 9 年前

    我正在研究一种图论算法。我知道什么是图,什么是边等等。我在c++中有这个脚本的第一部分,它声明了一些变量和一些结构,然后定义了一个添加边的函数。

    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    
    const int M = 500;
    struct struct_edge
    {
        int v; 
        struct_edge * n;  
    };
    
    typedef struct_edge * edge;  
    struct_edge pool[M * M * 2]; 
    edge top = pool, adj[M];    
    int V, E, match[M], qh, qt, q[M], father[M], base[M];   
    bool inq[M], inb[M], ed[M][M];   
    void add_edge(int u, int v)
    {
        top->v = v, top->n = adj[u], adj[u] = top++;
        top->v = u, top->n = adj[v], adj[v] = top++;
    }
    

    如果这还不够的话,我会在脚本中加入另一部分。 边缘顶部=水池,adj[M]; 有关完整代码,请参见以下链接 http://codeforces.com/blog/entry/49402

    1 回复  |  直到 9 年前
        1
  •  3
  •   meowgoesthedog    9 年前

    为了回答第一个问题,将图形存储为 邻接列表 总体安排每个节点都有一个关联的 边缘的数量( struct_edge ),每个都有一个索引( int v; )指向边末端的节点,以及指向下一条边的指针( struct_edge* n; ). 索引为 adj[M] 数组,其中存储 M 构成图形的节点。

    第二个问题, pool 结构边缘 ,OP用它来做一个 ,即通过递增方式分配新节点 top ,它是指向堆栈顶部的指针。 初始化为 水塘

    编辑:链接的wikimedia图的指针排列图:

    enter image description here

    (注意,索引从0开始,而不是从1开始,因此图中的节点1对应于 v = 0