Adicionar Aresta

Lição 5 de 14 do curso Grafos - Série de Estruturas de Dados #9 da Coddy.

Uma aresta conecta dois vértices. Como nosso grafo é não direcionado, a conexão funciona nos dois sentidos: se u e v estão conectados, então u aparece na lista de vizinhos de v e v aparece na de u.

Antes de conectar qualquer coisa, certifique-se de que ambos os vértices existam chamando addVertex em cada um (é uma operação nula se eles já existirem). Em seguida, adicione cada um na lista de vizinhos do outro. Ignore uma adição duplicada se a aresta já estiver lá. Para um laço (u == v), adicione-o apenas uma vez.

Agora vamos escrevê-lo.

Desafio

Fácil

Adicione um método addEdge à classe Graph.

Ele recebe dois inteiros u e v e os conecta em ambas as direções:

Certifique-se de que tanto u quanto v existam (use addVertex caso contrário).
Adicione v à lista de vizinhos de u (apenas se ainda não estiver lá).
Adicione u à lista de vizinhos de v (apenas se ainda não estiver lá). Se u == v, não o adicione uma segunda vez.

Experimente você mesmo

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graph.h"

static int _cmp_int(const void* a, const void* b) {
    int ai = *(const int*)a, bi = *(const int*)b;
    return (ai > bi) - (ai < bi);
}

int main() {
    Graph g;
    Graph_init(&g);
    char line[1024];
    while (fgets(line, sizeof(line), stdin)) {
        line[strcspn(line, "\r\n")] = '\0';
        char* cmd = strtok(line, " \t");
        if (!cmd) continue;
        if (strcmp(cmd, "verticesEmpty") == 0) { printf("%s\n", g.vertexCount == 0 ? "true" : "false"); }
        if (strcmp(cmd, "hasVertex") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Graph_indexOf(&g, atoi(arg)) != -1 ? "true" : "false"); }
        if (strcmp(cmd, "addVertex") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Graph_addVertex(&g, atoi(arg)); }
        if (strcmp(cmd, "addEdge") == 0) { char* a1 = strtok(NULL, " \t"); char* a2 = strtok(NULL, " \t"); if (a1 && a2) Graph_addEdge(&g, atoi(a1), atoi(a2)); }
        if (strcmp(cmd, "degree") == 0) {
            char* arg = strtok(NULL, " \t");
            if (arg) {
                int k = atoi(arg);
                int ki = Graph_indexOf(&g, k);
                printf("%d\n", ki == -1 ? 0 : g.vertices[ki].n);
            }
        }
    }
    return 0;
}

Todas as lições de Grafos - Série de Estruturas de Dados #9

1Introdução

Introdução O que é um Grafo?

2Projeto de Grafo

Classe Grafo Adicionar VérticeAdicionar ArestaPossui Aresta Obter Vizinhos Remover Aresta Tamanho

3Desafios de Prática

BFS DFS Caminho Mais Curto Contar Componentes Conectados É Bipartido