Kas ir diagrammas datu struktūra?

A Grafiks ir nelineāra datu struktūra, kas sastāv no virsotnēm un malām. Virsotnes dažreiz sauc arī par mezgliem, un malas ir līnijas vai loki, kas savieno jebkurus divus grafa mezglus. Formālāk grafiks sastāv no virsotņu kopas ( IN ) un malu kopa ( UN ). Grafiku apzīmē ar G(V, E) .

Grafa attēlojumi

Šeit ir divi visizplatītākie diagrammas attēlošanas veidi:

1. Blakus matrica
2. Blakus esošo vietu saraksts

Blakus matrica

Blakus matrica ir veids, kā attēlot grafiku kā Būla matricu (0 un 1).

romiešu cipari 1-100

Pieņemsim, ka tādi ir n virsotnes grafikā Tātad, izveidojiet 2D matricu adjMat[n][n] ar izmēru n x n.

• Ja ir mala no virsotnes i uz j , atzīmējiet adjMat[i][j] kā 1 .
• Ja no virsotnes nav malas i uz j , atzīmējiet adjMat[i][j] kā 0 .

Nevirzīta grafika attēlojums blakus matricai:

Zemāk esošajā attēlā parādīts nevirzīts grafiks. Sākotnēji tiek inicializēta visa Matrica 0 . Ja ir mala no avota līdz galamērķim, mēs ievietojam 1 abos gadījumos ( adjMat[galamērķis] un adjMat [ galamērķis]) jo mēs varam iet jebkurā virzienā.

Nevirzīts grafiks blakus matricai

Virzīta grafika attēlojums blakusesības matricai:

Zemāk esošajā attēlā parādīts virzīts grafiks. Sākotnēji tiek inicializēta visa Matrica 0 . Ja ir mala no avota līdz galamērķim, mēs ievietojam 1 šim konkrētajam adjMat[galamērķis] .

Novirzīts grafiks uz blakus matricu

Blakus esošo vietu saraksts

Sarakstu masīvs tiek izmantots, lai saglabātu malas starp divām virsotnēm. Masīva lielums ir vienāds ar skaitu virsotnes (t.i., n) . Katrs indekss šajā masīvā attēlo noteiktu diagrammas virsotni. Ieraksts masīva indeksā i satur saistīto sarakstu ar virsotnēm, kas atrodas blakus virsotnei i .

spēle balodis android

Pieņemsim, ka tādi ir n virsotnes grafikā Tātad, izveidojiet an sarakstu masīvs izmēra n kā adjList[n].

• adjList[0] būs visi mezgli, kas ir savienoti (kaimiņš) ar virsotni 0 .
• adjList[1] būs visi mezgli, kas ir savienoti (kaimiņš) ar virsotni 1 un tā tālāk.

Nevirzīta grafika attēlojums blakus sarakstam:

Zemāk esošajā nevirzītajā diagrammā ir 3 virsotnes. Tātad tiks izveidots 3. izmēra sarakstu masīvs, kurā katrs indeksi apzīmē virsotnes. Tagad virsotnei 0 ir divi kaimiņi (t.i., 1 un 2). Tātad, ievietojiet virsotni 1 un 2 pie masīva indeksiem 0. Līdzīgi 1. virsotnei tai ir divi kaimiņi (t.i., 2 un 0), tāpēc masīva indeksā 1 ievietojiet virsotnes 2 un 0. Līdzīgi virsotnei 2 ievietojiet tās kaimiņus saraksta masīvā.

Nevirzīts grafiks uz blakus vietu sarakstu

Orientēta grafika attēlojums blakus vietu sarakstam:

Zemāk norādītajā diagrammā ir 3 virsotnes. Tātad tiks izveidots 3. izmēra sarakstu masīvs, kurā katrs indeksi apzīmē virsotnes. Tagad virsotnei 0 nav kaimiņu. Virsotnei 1 tai ir divi kaimiņi (t.i., 0 un 2), tāpēc masīva 1. indeksā ievietojiet virsotnes 0 un 2. Līdzīgi virsotnei 2 ievietojiet tās kaimiņus saraksta masīvā.

Novirzīts grafiks uz blakus vietu sarakstu