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.
p->y = y;faz todo o sentido, o adjacente dexéy.p->next = g->edges[x];Mas aedgesmatriz é inicializada como nula. Isso não fará3.next == NULLem vez de3.next == 4?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.
Eu não chamaria isso de "adicionar ao
edgesarray", já que oedgesarray tem um comprimento fixo e uma entrada para cada nó (não para cada edge ).O índice de
edgesidentifica o vértice "de" de uma aresta, e oycampo deedgenodeidentifica o vértice "para" correspondente dessa mesma aresta.Para cada vértice
x, este código mantém uma lista vinculada de arestas (nãoedges, masedges[x]), que inicialmente estará vazia.Vamos fazer isso para um gráfico de exemplo:
...que após a inicialização é preenchido com suas arestas da seguinte forma:
Vamos ver como isso preenche a
graphestrutura de dados. Começamos com este estado parag(onde assumireiMAXVque é 4 para esta representação):Os hífens representam
nullpointervalores. Presumo que tudo isso foi inicializado corretamente.Em seguida,
insert_edge(g, 0, 1, true)criaremos umpnó, que será alocado e inicializado para isto:Notavelmente, o
nextcampo énullptr, porque esse é o valor encontrado emg->edges[0].Em seguida, a próxima instrução
g->edges[x] = pfaz a ligação e, após dois contadores terem sido incrementados, a função concluiu seu trabalho:Agora chegamos ao mais interessante:
insert_edge(g, 0, 2, true);. Novamentepé apontado para um novoedgenode, mas desta vezg->edges[0]não énullptre entãop->nextapontaremos para o adicionado anteriormenteedgenode. Depois deinsert_edgeterminar, obtemos isto:E assim continua para as outras arestas: toda vez que o new
edgenodeé anexado a uma lista vinculada da qual o ponteiro principal está armazenado noedgesarray. Temos 5 listas vinculadas: uma para cada vértice.Aqui está o resultado final do exemplo acima:
Espero que isso esclareça.