Què és l'estructura de dades del gràfic?
A Gràfic és una estructura de dades no lineal que consta de vèrtexs i arestes. Els vèrtexs també es coneixen com a nodes i les arestes són línies o arcs que connecten dos nodes qualsevol del gràfic. Més formalment, un gràfic es compon d'un conjunt de vèrtexs ( EN ) i un conjunt d'arestes ( I ). El gràfic es denota per G(V, E) .
convertir nombre enter en cadena java
Representacions de gràfics
Aquestes són les dues maneres més habituals de representar un gràfic:
- Matriu d'adjacència
- Llista d'adjacència
Matriu d'adjacència
Una matriu d'adjacència és una manera de representar un gràfic com una matriu de booleà (0 i 1).
Suposem que n'hi ha n vèrtexs al gràfic Per tant, creeu una matriu 2D adjMat[n][n] amb dimensió n x n.
- Si hi ha una aresta des del vèrtex i a j , senyal adjMat[i][j] com 1 .
- Si no hi ha cap vora des del vèrtex i a j , senyal adjMat[i][j] com 0 .
Representació del gràfic no dirigit a la matriu d'adjacència:
La figura següent mostra un gràfic no dirigit. Inicialment, s'inicialitza tota la Matrix 0 . Si hi ha una vora des de la font fins a la destinació, inserim 1 en ambdós casos ( adjMat[destinació] i adjMat [ destinació]) perquè podem anar de qualsevol manera.
Gràfic no dirigit a la matriu d'adjacència
Representació del gràfic dirigit a la matriu d'adjacència:
La figura següent mostra un gràfic dirigit. Inicialment, s'inicialitza tota la Matrix 0 . Si hi ha una vora des de la font fins a la destinació, inserim 1 per això en concret adjMat[destinació] .
Gràfic dirigit a la matriu d'adjacència
Llista d'adjacència
S'utilitza una matriu de llistes per emmagatzemar vores entre dos vèrtexs. La mida de la matriu és igual al nombre de vèrtexs (és a dir, n) . Cada índex d'aquesta matriu representa un vèrtex específic del gràfic. L'entrada a l'índex i de la matriu conté una llista enllaçada que conté els vèrtexs adjacents al vèrtex i .
bucle foreach mecanografiat
Suposem que n'hi ha n vèrtexs al gràfic Per tant, creeu un matriu de llista de mida n com adjList[n].
- adjList[0] tindrà tots els nodes connectats (veïns) al vèrtex 0 .
- adjList[1] tindrà tots els nodes que estan connectats (veïns) al vèrtex 1 etcètera.
Representació del gràfic no dirigit a la llista d'adjacència:
El següent gràfic no dirigit té 3 vèrtexs. Per tant, es crearà una matriu de llista de mida 3, on cada índex representen els vèrtexs. Ara, el vèrtex 0 té dos veïns (és a dir, 1 i 2). Per tant, inseriu els vèrtexs 1 i 2 als índexs 0 de la matriu. De la mateixa manera, per al vèrtex 1, té dos veïns (és a dir, 2 i 0). Per tant, inseriu els vèrtexs 2 i 0 als índexs 1 de la matriu. De la mateixa manera, per al vèrtex 2, inseriu els seus veïns a la matriu de la llista.
Gràfic no dirigit a la llista d'adjacència
Representació del gràfic dirigit a la llista d'adjacència:
El gràfic dirigit a continuació té 3 vèrtexs. Per tant, es crearà una matriu de llista de mida 3, on cada índex representen els vèrtexs. Ara, el vèrtex 0 no té veïns. Per al vèrtex 1, té dos veïns (és a dir, 0 i 2) Per tant, inseriu els vèrtexs 0 i 2 als índexs 1 de la matriu. De la mateixa manera, per al vèrtex 2, inseriu els seus veïns a la matriu de la llista.
Gràfic dirigit a la llista d'adjacència