Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs, Tipos de Representação, Caminhos e Ciclos, Busca Exaustiva,…
Graphs
Uma coleção de pontos em um plano chamados de vértices ou "nós", alguns deles conectados por um segmento de linha chamado aresta ou arcos.
Tipos
-
Directed
Um grafo G é direcionado se os vértices (u,v) e (v,u), não forem os mesmos. Grafos direcionados são também chamados de digrafos.
-
Tipos de Representação
Matriz de adjacência
A matriz de adjacência de grafo de n vértices é uma matriz booleana de n x n com uma linha e uma coluna para cada um dos vértices do grafo, no qual o elemento da i-ésima linha e j-ésima coluna é igual a 1 se há uma aresta entre da vértice até a vértice j.
Lista de adjacência
Uma lista de adjacência de um grafo ou um digrafo é uma coleção de listas encadeadas, uma para cada vértice, que contém todos os vértices adjacentes ao vértice da lista.
-
Caminhos e Ciclos
Caminhos
Um caminho do vértice u ao vértice v de um grafo G pode ser definido como uma sequência de vértices adjacentes (conectados por arestas) que começa em u e termina em v. Se todos os vértices do caminho forem distintos o caminho é dito como simples. O tamanho de um caminho é o número total de vértices na sequência que define o caminho menos 1.
Ciclos
Um ciclo é um caminho de tamanho positivo que começa e termina no mesmo vértice e não passa pela mesma aresta mais de uma vez.
-
Busca Exaustiva
O termo "busca exaustiva" pode ser aplicado por dois algoritmos que processam todos os vértices e todas arestas sistematicamente
Depth-first search
Ele começa a busca a partir de um vértice arbitrário e vai seguindo um caminho até encontrar um vértice sem adjacente ou que ja foi visitado (dead-end), a partir disso vai retornando até o vértice inicial checando se algum vértice não foi visitado até chegar no último dead-end, finalizando assim a busca. Principal estrutura para checar se um vértice é um dead-end é uma stack.
Principais Aplicações
Conectividade, aciclicidade, pontos de articulação
Breadth-first search
Esse tipo de busca pode ser descrito como mais cauteloso, em contrapartida ao DFS que vai seguindo um caminho até achar o dead-end, o BFS busca a partir de um vértice arbitrário e a partir dele checa os vértices adjacentes dele e repete o mesmo processo para todos esses mesmo vértices até chegar no último. Principal estrutura para realizar as buscas é a queue.
Principais Aplicações
Conectividade, aciclicidade, caminhos com o mínimo de arestas
Topological Sorting
Um tipo de ordenação criado para resolver um problema no qual procuramos uma forma de listar as vértices de um digrafo em ordem tal que para cada aresta no grafo, o vértice onde a aresta começa é listado antes do vértice onde a aresta termina.
-