Please enable JavaScript.
Coggle requires JavaScript to display documents.
GRAFOS - Coggle Diagram
GRAFOS
Coleção de pontos chamados vértices ou nós onde alguns são ligados por meio de linhas chamadas arestas ou arcos
-
-
Implementações
Matriz de adjacência
Para um grafo de n vértices, configura uma matriz nxn
Para o endereço A(x,y), armazena 1 se existir aresta entre os vértices x e y e armazena 0 se não existir
-
Para grafos de peso, simplesmente armazena na posição referente a cada aresta o número que representa o peso/custo da aresta
Lista de adjacência
Para cada vértice x contém uma lista ligada que armazena os vértices que possuem aresta entre eles e x
-
-
Para grafos de peso, cada nódulo das listas ligadas deve conter o vértice ao qual a aresta se conecta e o valor numérico de seu peso/custo
Caminhos
-
-
-
-
Tamanho do caminho é dado pelo número de arestas atravessadas (ou número de vértices atravessados menos um)
Busca exaustiva
-
Percurso forma uma floresta composta pelos vértices do grafo e pelas arestas especiais classificadas como "arestas de árvore
-
-
-
-
Ordenação topológica
-
Responde o problema de ordenação dos vértices de forma que todas as arestas partem de um vértice antecessor e chegam em um vértice sucessor
-