La creación de una adyacencia matriz a partir de un gráfico JUNG
-
25-09-2019 - |
Pregunta
Graph < Integer, Integer> g = new SparseMultigraph<Integer, Integer>();
g.addVertex(1);g.addVertex(2);g.addVertex(3);
g.addEdge(0,1,2 ,EdgeType.DIRECTED);g.addEdge(1,2,3 ,EdgeType.DIRECTED);g.addEdge(2,3,1 ,EdgeType.DIRECTED);g.addEdge(3,1,3 ,EdgeType.DIRECTED);
¿Cómo puedo convertir este gráfico en una matriz de adyacencia tomando en consideración que es un grafo dirigido.
Solución
En este post se puede encontrar una matriz de adyacencia:
Amplitud y profundidad primera búsqueda - parte 3
¿Cómo implementarlo?
// Adjacency matrix
int map[21][21] = {
/* A B C D E F G H I L M N O P R S T U V Z */
{0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1}, // Arad
{2,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,0,0}, // Bucharest
{3,0,0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0}, // Craiova
{4,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0}, // Dobreta
{5,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, // Eforie
{6,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0}, // Fagaras
{7,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, // Girgiu
{8,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0}, // Hirsova
{9,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0}, // Iasi
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0}, // Lugoj
{1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0}, // Mehadia
{2,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}, // Neamt
{3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1}, // Oradea
{4,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}, // Pitesti
{5,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0}, // Rimnicu Vilcea
{6,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,0,0}, // Sibiu
{7,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0}, // Timisoara
{8,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0}, // Urziceni
{9,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0}, // Vaslui
{0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0} // Zerind
};
Tenga en cuenta que la primera línea comentada representa la letra inicial del nombre de cada ciudad. El mapeo hecho con la matriz de adyacencia se refiere a estas cartas para que sea más fácil de entender. Por ejemplo, conseguir la primera entrada de la matriz de adyacencia que se refiere a Arad: tenemos que Arad caminos que nos llevan a Sibiu, Timisoara y Zerind, por lo tanto ponemos un valor de 1 en las columnas que representan esas ciudades, en este caso , las columnas debajo de las letras S, T y Z. Así es como se hace la asignación. Ponemos un valor de 0 en las otras columnas para indicar que no hay un camino que nos lleva a esas ciudades.
Dada su gráfico, Iterar sus bordes y crear su matriz de adyacencia.