Início / user-15412365

VIAGC's questions

Martin Hope
VIAGC
Asked: 2023-08-27 14:18:10 +0800 CST
  • 10

Estou seguindo o Manual de Design de Algoritmo v3 da Skiena.

Tenho visto algumas perguntas afirmando que há certos erros de digitação no livro e não tenho certeza se é um deles ou apenas porque não consigo entendê-los.

Considere o seguinte:

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++;
    }
}

Pelo que entendi, void insert_edge(graph *g, int x, int y, bool directed)conecta dois nós no índice do array xe yos adiciona ao edgesarray.

O seguinte trecho me confunde:

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

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

Como isso está funcionando? Suponha que minha entrada seja x = 3, y = 4e esta seja a primeira entrada.

Eu esperaria algo parecido 3 -> 4com um gráfico direcionado.

  1. p->y = y;faz todo o sentido, o adjacente de xé y.
  2. p->next = g->edges[x];Mas a edgesmatriz é inicializada como nula. Isso não fará 3.next == NULLem vez de 3.next == 4?
  3. g->edges[x] = p;O que? edges[x] == x Node, isso me confunde.

O código completo pode ser encontrado em graph.c e graph.h .

Acho que p.next = y;de alguma forma e y.next = NULLa partir de agora, ou seja, a primeira inserção. Talvez seja meu C enferrujado, mas preciso de ajuda nisso.

c