Tutorial da estrutura de dados do gráfico

Na computação, um gráfico é um conjunto de nós conectados por links. A principal diferença entre uma árvore e um gráfico é que uma árvore tem um nó raiz, enquanto um gráfico tem mais de um nó raiz. Você já deve ter conhecimento básico da estrutura de dados de árvores antes de vir aqui, pois os conceitos ali, serão usados ​​aqui com pouca ou nenhuma explicação. Se você não tiver esse conhecimento, leia o tutorial intitulado, Tutorial da estrutura de dados de árvores para iniciantes, no link, https: // linuxhint.com/árvore_data_structure_tutorial_beginners/.

Um nó em um gráfico é chamado de vértice (plural - vértices). Às vezes, ainda é chamado de nó; também pode ser chamado de ponto. Um link em um gráfico é chamado de vantagem. Às vezes, ainda é chamado de link; também pode ser chamado de linha.

Gráfico com muitos recursos

Esta figura mostra um gráfico com muitos recursos:

Os círculos (discos) são vértices. Qualquer linha reta ou linha ou loop curva é uma vantagem.

Recursos do gráfico

Vértice

Um vértice é um objeto. Pode ser uma casa; pode ser uma pessoa; Pode ser um substantivo abstrato; pode ser qualquer objeto que você possa pensar.

Borda

Uma borda é uma conexão (relação) entre dois vértices; A conexão pode ser abstrata.

Laço

Um loop é uma vantagem que conecta um vértice a si mesmo.

Borda de seta

Considere duas pessoas: John e Peter. Se John emprestar Peter $ 100, e se John e Peter são vértices, então a vantagem de empréstimos estará apontando para Peter. Se ambos os parceiros esquecem que Peter está devido a John, e Peter empresta John $ 100, então no outro extremo da mesma vantagem, uma ponta de flecha estará apontando para John. Se Peter emprestasse, mas US $ 75 a John e não US $ 100, então uma vantagem diferente conectaria Peter a John. Esta segunda vantagem terá sua ponta de flecha apontando para John. No segundo caso, há duas bordas, com uma ponta de seta cada uma, apontando em direções opostas.

O vértice ao qual uma borda aponta é um vértice da cabeça para aquela borda. O vértice do qual uma borda sai, é um vértice da cauda.

Incidente

Uma borda conecta dois vértices. Diz -se que a borda é incidente em qualquer um dos vértices. A borda não precisa ter uma ponta de flecha. Os dois vértices são conhecidos como pontos de extremidade da borda. É possível ter um gráfico onde um vértice não pertence a nenhuma vantagem, mas isso não será considerado neste tutorial.

Gráfico não direcionado

Uma vantagem pode ser uma flecha, ou não pode. Um gráfico onde nenhuma borda é uma seta é um gráfico não direcionado. Uma vantagem pode ser representada por uma linha reta ou uma curva ou um loop.

Gráfico direcionado

Um gráfico onde cada borda é uma seta (direção) é um gráfico direcionado. Uma borda de seta pode ser representada por uma linha reta com uma ponta de seta ou uma curva com uma ponta de seta ou um laço com uma ponta de seta.

A ausência de uma direção na borda de um gráfico não direcionado significa que cada borda do gráfico não direcionado é bidirecional.

Grau de um vértice

O número de arestas incidentes em um vértice é o grau de vértice. Um loop tem duas incidências em um vértice, então um loop é contado duas vezes.

Ordem de um gráfico

A ordem de um gráfico é o número de vértices no gráfico.

Multigraph

Um multigraph é um gráfico, onde para alguns pares de vértices, há mais de uma bordas. Um multigraph não direcionado é um gráfico no qual as bordas não têm instruções (não são setas). Um multigraph direcionado é aquele em que cada borda é uma seta e para pares de vértices com mais de uma seta, um vértice é a cauda dessas flechas e o outro vértice é a cabeça das mesmas setas. O diagrama a seguir mostra um multigraph não direcionado:

Mais de uma bordas (eu.e. Várias bordas) para um par de vértices também são chamados de bordas paralelas.

Tremor

Uma aljava é uma multigraph que permite loops (um ou mais loops). Alguns multigrafos não permitem loops.

Gráfico simples

Um gráfico simples é um gráfico em que não há dois pares de vértices. Loops não são permitidos em um gráfico simples.

Gráfico vazio

Um gráfico vazio é um gráfico sem vértices e, portanto, sem bordas.

Gráfico misto

Um gráfico misto é um gráfico onde algumas bordas são setas e outras não; Em outras palavras: algumas arestas têm instruções e outras não são direcionadas.

Gráfico ponderado

É possível ter um gráfico no qual um número, conhecido como peso, é atribuído a cada borda. Algumas bordas têm o mesmo número, mas os números geralmente são diferentes. Esse gráfico é chamado de gráfico pesado. Os números para um gráfico específico podem representar comprimentos ou custos (preços) ou magnitude de algum tipo, dependendo do problema.

Indegree e ao ar livre

O vocabulário, o indegredo e o averno. O gráfico pode ou não ser um multigraf. O gráfico pode ou não ter loops.

O número de pontas de seta conectadas a um vértice é o indegredo daquele vértice. Uma seta com uma única ponta de seta tem uma extremidade da cabeça e uma extremidade traseira. O número de caudas conectadas a um vértice é o vertez daquele vértice.

Nota: Um gráfico com várias arestas para o par de vértices, onde as múltiplas bordas estão em direções opostas, não é abordada neste tutorial.

Representação de software de um gráfico

Um gráfico pode ser representado no software da maneira como é desenhado no diagrama. Um gráfico também pode ser representado em software por uma matriz matemática (matriz bidimensional). Uma dessas matrizes é chamada de matriz de adjacência.

Matriz de adjacência

Uma matriz de adjacência é uma matriz quadrada. Os títulos para as fileiras são todos os vértices, escritos em ordem ascendente. Os títulos para as colunas ainda são os mesmos vértices, escritos em ordem crescente. A contagem das linhas ou colunas de uma matriz começa a partir de 1 e não zero, como com as matrizes. Ao identificar um elemento em uma matriz, o número da linha é escrito primeiro antes do número da coluna.

Para um gráfico não direcionado, cada entrada (elemento) na matriz de adjacência é o número de bordas que conectam os dois vértices correspondentes. Um loop deve ser contado duas vezes. Para um gráfico direcionado, cada entrada na matriz de adjacência é o número de bordas que deixa um vértice de linha e entrando no vértice da coluna correspondente ou é o número de bordas que deixam um vértice da coluna e entrando no vértice da linha correspondente. A escolha é a do programador. Nesta situação (ambos os casos), um loop ainda deve ser contado uma vez.

Nota: Um gráfico é um diagrama é uma estrutura de dados por si só. Uma matriz de adjacência também é uma estrutura de dados por si só.

Gráfico não direcionado e matriz de adjacência

Os diagramas a seguir mostram um gráfico não direcionado e a matriz de adjacência correspondente:

A diagonal principal de uma matriz é a diagonal do topo esquerdo ao canto inferior direito. Uma matriz não direcionada é simétrica sobre a líder diagonal. A entrada da matriz para a linha A e a coluna C é 1, o que significa que há uma borda conectando o vértice A e o vértice C. A entrada da matriz para a linha C e a coluna B é 3, o que significa que existem 3 arestas conectando o vértice C e o vértice B. As outras entradas são explicadas da mesma forma.

A soma das entradas para uma linha fornece o número de arestas (grau) para o vértice correspondente. A soma das entradas para a linha A é 2, o que significa que 2 arestas estão conectadas ao vértice a. A soma das entradas para a linha B é 6, o que significa que 6 arestas estão conectadas ao vértice B. O restante das entradas é explicado da mesma forma.

Gráfico direcionado e matriz de adjacência

Os diagramas a seguir mostram um gráfico direcionado e a matriz de adjacência correspondente:

A matriz de adjacência para um gráfico direcionado não é necessariamente simétrico sobre a líder diagonal. A entrada da matriz para a linha A e a coluna C é 1, o que significa que uma borda folhas do vértice A a vértice C. A entrada da matriz para a linha C e a coluna B é 3, o que significa que 3 arestas deixam do vértice C para o vértice B. As outras entradas são explicadas da mesma forma.

A soma das entradas para uma coluna dá o indegredo para o vértice (coluna). A soma das entradas para uma fila dá o vertex (da linha). A soma das entradas para a coluna A é 1, o que significa que uma borda é direcionada ao vértice a. A soma das entradas para a linha B é 2, o que significa que 2 bordas saem do vértice b. O restante das entradas é explicado da mesma forma.

Operações gráficas

Uma estrutura de dados, como um gráfico, consiste em um conjunto de valores de dados ou um conjunto de objetos, além da relação entre os objetos, além das operações (funções) entre os objetos. Os relacionamentos em um gráfico são indicados pelas bordas. Para isso, um gráfico deve ter pelo menos as seguintes operações:

adjacente (G, X, Y)

G significa gráfico. Esta operação verifica se uma borda conecta o vértice x e o vértice y. O valor e a posição de uma entrada em uma matriz indicam a conexão de uma borda (e seu tipo).

vizinhos (G, X)

Esta operação retorna uma lista de todos os vértices diretamente conectados ao vértice x. O valor e a posição de uma entrada em uma matriz indicam a conexão de uma borda.

Remone_vertex (g, x)

Esta operação remove um vértice, x de um gráfico. Se o vértice não tivesse vantagem, não há problema. No entanto, se o vértice tivesse links, os links (bordas) também devem ser removidos. O valor e a posição de uma entrada em uma matriz indicam a presença de um determinado vértice. Se um vértice for removido, a matriz deve ser reajustada.

add_vertex (g, x)

Isso adiciona um vértice, x sem adicionar bordas, ou substitui um vértice que tinha bordas, mas foi removido. O valor e a posição de uma entrada em uma matriz indicam a presença de um determinado vértice. Se um vértice for adicionado, a matriz deve ser reajustada.

add_edge (g, x, y)

Esta operação adiciona uma nova vantagem entre o vértice x e o vértice y se a borda não estivesse lá. O valor e a posição de uma entrada em uma matriz indicam a presença de uma borda específica. Se uma vantagem for adicionada, a matriz deve ser reajustada.

remove_edge (g, x, y)

Esta operação removeria a borda entre o vértice x e o vértice y se a borda estivesse lá. O valor e a posição de uma entrada em uma matriz indicam a presença de uma borda específica. Se uma borda for removida, a matriz deve ser reajustada.

get_vertex_value (g, x)

Esta operação retorna o valor, v associada ao vértice, x. Para conseguir isso, você precisa de um conjunto de subconjuntos para rótulos de vértices e seus valores.

set_vertex_value (g, x, v)

Esta operação fornece um novo valor, v para o valor associado ao vértice, x. Para conseguir isso, você precisa de um conjunto de subconjuntos para rótulos de vértices e seus valores.

Alguns gráficos associam valores às suas bordas também. Esses gráficos precisam das seguintes operações adicionais:

get_edge_value (g, x, y)

Esta operação retorna o valor, v associada à borda (x, y). Para conseguir isso, você precisa de um conjunto de subconjuntos para bordas e seus valores.

set_edge_value (g, x, y, v)

Esta operação fornece um novo valor, v para o valor associado à borda (x, y). Para conseguir isso, você precisa de um conjunto de subconjuntos para bordas e seus valores.

Conclusão

Um gráfico é um conjunto de vértices conectados com bordas. Um gráfico pode ser não direcionado ou direcionado. As bordas podem não ser direcionais ou direcionais. Loops podem estar presentes ou ausentes em um gráfico. O que você deve aprender a seguir é definido, conjunto de energia e multiset relacionado a gráficos. Depois disso, você deve aprender os diferentes tipos de gráficos, como um gráfico orientado, gráfico regular, gráfico completo, gráfico bipartido, gráfico de torneios, gráfico de rede de fluxo, etc.

Chrys