Kas ir virziena grafiks un kādas ir tā galvenās īpašības?

Virziena grafs (vai diagrāfs) ir datu struktūra, kas sastāv no virsotnēm (mezgliem) un virzienotām malām (līnijām), kas savieno šīs virsotnes. Katram malai ir virziena, kas norāda, kura virsotne ir sākuma, bet kura — beigu punkts.

Galvenās īpašības:

• Virsotnes (Nodes / Vertices): Grafika elementi, attēloti ar punktiem. Var apzīmēt objektus, stāvokļus vai posmus.
• Malas (Edges / Arcs): Savienojumi starp virsotnēm. Virziena grafikā mala ir ar norādi, kas norāda pāreju no vienas virsotnes uz otru. Marķēta ar sakārtotu pāri (u, v), kur u ir sākuma virsotne, v — beigu virsotne.
• Virziena: Galvenā īpašība, kas atšķir virziena grafu no nevirziena. Pāreja ir iespējama tikai pa mala norādīto virzienu. Mala no A uz B nenozīmē iespēju pāriet no B uz A, ja nav atsevišķas malas no B uz A.
• Aplīši (Loops): Mala, kas savieno virsotni ar pašu sevi (v, v).
• Daudzskaitlīgas malas (Multiple Edges): Vairākas malas, kas savieno to pašu virsotņu pāri tajā pašā virzienā. Vienkāršā virziena grafikā daudzskaitlīgas malas nav atļautas.
• Izolētas virsotnes: Virsotnes bez iebraucošajām un izejošajām malām.
• Virsotnes pakāpe:
  • Ieejošo malu skaits (In-degree): Cik iebraucošo malu ir virsotnē.
  • Izejošo malu skaits (Out-degree): Cik izejošo malu ir virsotnē.

Pielietojums QA:

• Stāvokļu grafi galīto automātu testēšanai.
• Kontroles plūsmu grafi koda analīzei un testu gadījumu izstrādei.
• Atkarību modelēšana sistēmās (piemēram, atkarības starp pakalpojumiem vai moduļiem).
• Lietošanas scenāriju testēšana ar stingru darbību secību.