Estrutura de armazenamento
Para armazenar um gráfico, sabemos que o gráfico possui nós e bordas. Para um gráfico alimentado, cada borda também possui um valor de peso. Existem dois tipos principais de estruturas de armazenamento de gráficos comumente usadas:
Matriz adjacente Tabela adjacente
Matriz adjacente
Sabemos que, para representar nós, podemos representá-los com uma matriz unidimensional. No entanto, para a relação entre nós, não podemos simplesmente representá-los com uma matriz unidimensional. Podemos representá-los com uma matriz bidimensional, ou seja, um método de representação formador de matriz.
Assumimos que A é essa matriz bidimensional, então um elemento AIJ em A não apenas reflete a relação entre o nó VI e o nó VJ, mas também o valor de AIJ pode representar o tamanho do peso.
Aqui está um exemplo de uma representação da matriz de adjacência de um gráfico não direcionado:
A partir da figura acima, podemos ver que a matriz de adjacência do gráfico não direcionada é uma matriz simétrica e deve ser uma matriz simétrica. E o valor na diagonal do canto superior esquerdo para o canto inferior direito é zero (a diagonal indica o mesmo nó)
Qual é a matriz de adjacência de um gráfico direcionado?
Para gráficos ponderados, o valor da AIJ pode ser usado para representar o tamanho do peso. Os dois gráficos acima são gráficos sem pesos; portanto, seus valores são 1.
Tabela adjacente
Sabemos que o método de armazenamento da matriz de adjacência do gráfico usa uma matriz n*n. Quando essa matriz é uma matriz densa (por exemplo, quando o gráfico é um gráfico completo), é claro que o método de armazenamento da matriz de adjacência é escolhido.
Mas se essa matriz for uma matriz esparsa, a estrutura de armazenamento de mesa adjacente é uma estrutura de armazenamento mais que economiza espaço.
Para o gráfico não direcionado acima, podemos usar uma tabela de adjacência para representá -lo da seguinte maneira:
O nó conectado a cada nó é seu nó adjacente.
Comparação entre a matriz de adjacência e a tabela de adjacência
Quando o número de nós no gráfico é pequeno e há muitos lados, a eficiência do uso de uma matriz de adjacência é maior.
Quando o número de nós é muito grande e o número de arestas é muito menor que o número de bordas do gráfico completo do mesmo nó, é mais eficiente adotar uma estrutura de armazenamento de tabela de adjacência.
Implementação de Java da matriz de adjacência
Classe de Modelo Matrix adjacente
O nome da classe da classe Modelo da Matriz Adjacência é amwgraph.java. Ele pode construir um gráfico representado por uma matriz de adjacência através dessa classe e fornecer nós de inserção, inserir arestas e obter o primeiro nó adjacência e o próximo nó adjacência de um determinado nó.
importar java.util.ArrayList; importar java.util.LinkedList;/** * @Description Classe de modelo de matriz adjacente * @author beanlam * @time 2015.4.17 */public classe AMWGRAPH {private ArrayList vertexlist; // armazenamento privado int [] [] arestas public amwgraph (int n) {// Inicialize a matriz, matriz unidimensional e número de bordas bordas = new int [n] [n]; vertexlist = new ArrayList (n); numefedges = 0; } // Obtenha o número de nós public int getNumofvertex () {return vertexlist.size (); } // Obtenha o número de arestas public int getNumofedges () {return nmofedges; } // retorna os dados do nó i public Object getValueByIndex (int i) {return vertexlist.get (i); } // retorna o peso de v1, v2 public int getWeight (int v1, int v2) {retorna arestas [v1] [v2]; } // Insira o nó public void insertVertex (object vertex) {vertexlist.add (vertexlist.size (), vértice); } // Insira o nó public void insertEdge (int v1, int v2, int peso) {bordas [v1] [v2] = peso; Numofedges ++; } // excluir o nó public void DeLeteedge (int v1, int v2) {arestas [v1] [v2] = 0; Numofedges--; } // Obtenha o índice do primeiro nó adjacente public int getfirstneighbor (int index) {for (int j = 0; j <vertexlist.size (); j ++) {if (bordas [index] [j]> 0) {return j; }} retornar -1; } // busca o próximo nó de adjacência de acordo com o subscrito do nó de adjacência anterior public int getNextneighbor (int v1, int v2) {for (int j = v2+1; j <vertexList.size (); j ++) {if (bordas [v1] [j]> 0) {return j; }} retornar -1; }}Teste da classe Modelo da Matriz de Adjacência
Em seguida, configure a classe de modelo de teste com base no seguinte gráfico direcionado
O programa de teste testamwgraph.java é o seguinte:
/** * @Description Test Class of Amwgraph Class * @Author Beanlam * @Time 2015.4.17 */public classe testamwgraph {public static void main (string args []) {int n = 4, e = 4; // representa o número de nós e o número de bordas, respectivamente, string, respectivamente, string, respectivamente rótulos [] = {"v1", "v1", "v3", "v4"}; // identificação de nó amwgraph gráfico = novo amwgraph (n); para (rótulo da string: etiquetas) {graph.insertVertex (etiqueta); // inserir nó} // insira quatro arestas Graph.insertEdge (0, 1, 2); Graph.InsertEdge (0, 2, 5); Graph.InsertEdge (2, 3, 8); Graph.InsertEdge (3, 0, 7); System.out.println ("O número de nós é:"+Graph.getNumofvertex ()); System.out.println ("O número de arestas é:"+graph.getNumofedges ()); Graph.DeleteEdge (0, 1); // delete <v1, v2> system.out.out.println ("Após a exclusão <v1, v2> borda ..."); System.out.println ("O número de nós é:"+Graph.getNumofvertex ()); System.out.println ("O número de arestas é:"+graph.getNumofedges ()); }}Os resultados da saída do console são mostrados na figura abaixo:
Resumir
O exposto acima é todo o conteúdo deste artigo sobre a descrição do idioma Java da estrutura de armazenamento e exemplos de código da matriz de adjacência. Espero que seja útil para todos. Amigos interessados podem continuar se referindo a outros tópicos relacionados neste site. Se houver alguma falha, deixe uma mensagem para apontá -la.