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.
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;
classe pública amwgraph {
Private Arraylist Vertexlist;
// A tabela de links de pontos de armazenamento
private int [] [] bordas;
// matriz de endereço, usado para armazenar as bordas
private int nmofedges;
// Número de arestas
public amwgraph (int n) {
// Inicialize a matriz, a matriz unidimensional e o número de arestas
arestas = 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 () {
retornar numofedges;
}
// retorna os dados do nó i
Public Object getValueByIndex (int i) {
retornar vertexlist.get (i);
}
// retorna o peso de V1 e V2
public int getWeight (int v1, int v2) {
Bordas de retorno [v1] [v2];
}
// Insira o nó
public void insertvertex (objeto vértice) {
vertexlist.add (vertexlist.size (), vértice);
}
// Insira o nó
public void InsertEdge (int v1, int v2, int peso) {
arestas [v1] [v2] = peso;
Numofedges ++;
}
// Excluir nó
public void DeLeteedge (int v1, int v2) {
arestas [v1] [v2] = 0;
Numofedges--;
}
// Obtenha o subscrito do primeiro nó adjacente
public int getfirstneighbor (int index) {
for (int j = 0; j <vertexList.size (); j ++) {
if (arestas [index] [j]> 0) {
retornar j;
}
}
retornar -1;
}
// Obtenha o próximo nó de adjacência com base no subscrito do nó de adjacência anterior
public int getNextneighbor (int v1, int v2) {
for (int j = v2+1; j <vertexList.size (); j ++) {
if (arestas [v1] [j]> 0) {
retornar j;
}
}
retornar -1;
}
}Vamos dar uma olhada no código que implementa a matriz de adjacência para representar gráficos densos:
pacote com.datastructure.graph;
///// Gráfico denso - Use a matriz de adjacência para representar
// classe pública DenseGraph {
//
// private int n; // Número de nós
// private int m; // Número da borda
// Privado booleano direcionado; // é um gráfico direcionado
// private boolean [] [] g; // dados específicos da imagem
//
// // construtor
// public denseGraph (int n, boolean direcionado) {
// afirma n> = 0;
// this.n = n;
// this.m = 0; // A inicialização não tem arestas
// this.directed = direcionado;
// // g é inicializado para uma matriz booleana de n*n. Cada g [i] [j] é falso, indicando que não há nenhuma e bordas.
// // false é o valor padrão da variável do tipo booleano
// g = novo booleano [n] [n];
//}
//
// public int v () {
// retorna n;
//} // retorna o número de nós
//
// public int e () {
// retorna m;
//} // retorna o número de arestas
//
// // Adicione uma borda ao gráfico
// public void Addedge (int v, int w) {
//
// assert v> = 0 && v <n;
// afirma w> = 0 && w <n;
//
// if (hasEdge (v, w))
// retornar;
//
// // Connect V e W
// g [v] [w] = true;
// if (! direcionado)
// g [w] [v] = true;
//
// // Número de arestas ++
// m ++;
//}
//
// // Verifique se há bordas de V a W no gráfico
// boolean hasEdge (int v, int w) {
// assert v> = 0 && v <n;
// afirma w> = 0 && w <n;
// retorna g [v] [w];
//}
//
// // retorna todos os vizinhos de um vértice no gráfico
// // Como o Java usa um mecanismo de referência, o retorno de um vetor não trará nenhuma sobrecarga adicional.
// public iterable <Teger> adj (int v) {
// assert v> = 0 && v <n;
// Vector <Teger> adjV = novo vetor <TEGER> ();
// para (int i = 0; i <n; i ++)
// if (g [v] [i])
// adjv.add (i);
// retorna adjv;
//}
//}
importar java.util.arraylist;
importar java.util.list;
// Use a matriz de adjacência para representar gráficos densos
classe pública denseGraph {
privado int n;
// número de nós na figura
privado int m;
// Número de arestas na imagem
private booleano [] [] G;
// matriz adjacente G
Privado booleano direcionado;
// é um gráfico direcionado
public denseGraph (int n, booleano direcionado) {
this.n = n;
// o número de nós no gráfico de inicialização
this.m = 0;
// O número de arestas na figura é inicializado para 0
this.directed = direcionado;
g = novo booleano [n] [n];
// A matriz de adjacência G é inicializada em uma matriz bidimensional de n*n
// O índice representa o nó no gráfico, e o valor armazenado em g é se o nó tem arestas
}
// retorna o número de arestas no gráfico
public int e () {
retornar m;
}
// retorna o número de nós no gráfico
public int v () {
retornar n;
}
// adiciona arestas entre os dois nós especificados na figura
public void adicionado (int v, int w) {
if (! hasEdge (v, w)) {
// conectar [v] [w]
g [v] [w] = true;
// Gráfico não direcionado
se (! direcionado)
g [w] [v] = true;
// o número de lados na figura +1
m ++;
}
}
// determinar se existem arestas entre os dois nós
Private Boolean HasEdge (int v, int w) {
retornar g [v] [w];
}
// retorna os nós de adjacência de todos os nós V
public iterable <Teger> adjacentNode (int v) {
// adjacentl é usado para armazenar o nó adjacente de V
Lista <Integer> adjacentl = new ArrayList <> ();
// Encontre todos os nós adjacentes a V e adicione -os a adjacentl
for (int i = 0; i <n; i ++) {
if (g [v] [i])
adjacentl.add (i);
}
retornar adjacentl;
}
}
Resumir
O exposto acima é todo o conteúdo deste artigo sobre programação Java para implementar o exemplo de código de representação de gráfico denso da matriz de adjacência, e espero que seja útil para todos. Amigos interessados podem continuar se referindo a este site:
Análise de conceitos básicos e exemplos de código da árvore de estrutura de dados Java
Java Common Data Structure Entrevista Perguntas (com respostas)
Princípio do algoritmo de correspondência multimodo e código de implementação Java
Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!