Spre deosebire de margini, inegale arce conecta două noduri. Una dintre ele se numește începutul arcului (arcului se bazează pe), al doilea - la sfârșitul arcului (arc include). Putem spune că fiecare margine - o pereche de arce. îndreptate unul către celălalt.
Dacă graficul și marginile sunt prezente. și arce. este numit amestecat.
Toate conceptele de bază definite pentru graficele neorientate (..... Incidența contiguitate lungimea căii realizabile etc.) rămân în vigoare pentru graficele direcționate - trebuie doar să înlocuiți cuvântul „margine“ cu cuvântul „arc“. Câteva excepții se datorează diferențelor existente între margini și arce.
Gradul de vârful în digraph - nu este un singur număr, în timp ce o pereche de numere: primul caracterizează numărul de arce de ieșire din vârful. iar al doilea - numărul de arce de intrare.
Calea în digraph - o secvență de noduri (fără repetiții), în care oricare două vârfuri adiacente sunt adiacente, iar fiecare vârf al arcului este simultan un capăt și începutul următorului arc. De exemplu, într-un grafic direcționat în Fig. 11.6 Nici un fel. 2 care duce de la vârful la vârf 5. „muta“ de pe digraph este posibilă numai în direcțiile definite de săgeți.
Tabelul 11.2. Exemple digraphs
grafice ponderate
Weighted (etichetat aka) grafic (sau digraph) - un grafic (digraph), anumite elemente din care (vârfurile nervuri sau muchii.) Comparat numarul. Graficele cel mai frecvent întâlnite cu margini deosebite. Numărul de note au nume diferite: greutatea. lungime. cost cu o schimbare.
Notă. Normal (neponderate) grafic poate fi interpretat ca un echilibru, ale cărei margini au aceeași greutate 1.
Lungimea suspensiei graficului (conectat) - este suma lungimilor (ponderilor) a acelor margini care alcătuiesc calea. Distanța dintre vârfurile - este, ca și mai înainte, lungimea calea cea mai scurtă. De exemplu, distanța de la un vârf la vertex într-un grafic ponderat d. este prezentată în Fig. 11.7. egală cu 6.
Fig. 11.7. Graficul ponderat
N -periferiya vârf v - este setul de noduri. distanța față de fiecare dintre ele (de vertex v) nu este mai mică decât N.
Modalități de reprezentare grafice
Există un număr destul de mare de moduri diferite de a reprezenta grafice. Cu toate acestea, vom prezenta aici doar cele mai utile din punct de vedere al programării.
Matricea adiacență
matricea de adiacență Sm - este o matrice pătrată de dimensiune NxN (N - numărul de noduri din grafic), următoarele reguli completate și cele zerouri:
Rețineți că această definiție este grafice orientate și neorientate adecvate. matricea de adiacență pentru un graf neorientat este simetrică în raport cu principalul său diagonală, și pentru digraph - asimetrice.
Puneți grafic ponderată utilizând matricea de adiacență este de asemenea posibilă. Este necesar doar pentru a face o mică schimbare în definiția:
Acest lucru este în concordanță cu observațiile făcute în paragraful anterior: graficul neponderate pot fi interpretate ca echilibrate, toate muchiile care au aceeași greutate 1.
Glitch vor apărea în cazul în care în coaste coloane rezolvate cu greutate 0. Apoi, este necesar pentru a stoca cele două tablouri: unul cu zero-uri si cele care servesc drept indicator al prezenței nervurilor, iar al doilea - cu greutăți ale marginilor.
Ca exemplu prezentăm matricea de adiacenta pentru cele trei grafice. descris în Fig. 11.5. Fig. 11.6 și fig. 11.7 (vezi. Fig. 11.8).
Tabelul 11.8. Exemple de matrici adiacență
Matricea de adiacență Ușor este claritatea și transparența algoritmilor bazate pe utilizarea acestuia. Un dezavantaj - în unele cerințe exagerate de memorie: dacă graficul este departe de a fi completă, matrice care stochează matricea de adiacenta. este o mulțime de „locuri goale“ (zero). În plus, pentru „dialogul“ cu utilizatorul, acest mod de prezentare a graficului nu este foarte convenabil: este mai bine să utilizați numai pentru reprezentarea internă a datelor.
notițe
cod embed :. . . GOST.
Găzduit de „Service Center Web“, cu sprijinul „DokLab“