Kas yra grafiko duomenų struktūra?

A Grafikas yra nelinijinė duomenų struktūra, susidedanti iš viršūnių ir briaunų. Viršūnės kartais dar vadinamos mazgais, o briaunos yra linijos arba lankai, jungiantys bet kuriuos du grafiko mazgus. Formaliau grafiką sudaro viršūnių rinkinys ( IN ) ir kraštų rinkinys ( IR ). Grafikas žymimas G(V, E) .

Grafo vaizdavimas

Štai du dažniausiai pasitaikantys grafiko vaizdavimo būdai:

1. Gretimo matrica
2. Gretimų sąrašas

Gretimo matrica

Gretumų matrica yra būdas pavaizduoti grafiką kaip loginės vertės (0 ir 1) matricą.

Tarkime, kad yra n viršūnės grafe Taigi, sukurkite 2D matricą adjMat[n][n] kurių matmenys n x n.

išimčių tvarkymas java

• Jei yra briauna nuo viršūnės i į j , ženklas adjMat[i][j] kaip 1 .
• Jei nuo viršūnės nėra briaunos i į j , ženklas adjMat[i][j] kaip 0 .

Nenukreipto grafiko vaizdavimas gretimų matricoje:

Žemiau esančiame paveikslėlyje parodytas neorientuotas grafikas. Iš pradžių inicijuojama visa Matrica 0 . Jei yra kraštas nuo šaltinio iki paskirties vietos, įterpiame 1 abiem atvejais ( adjMat[paskirtis] ir adjMat [ Kelionės tikslas]) nes galime eiti bet kuriuo būdu.

Nenukreiptas grafikas į gretimų matricą

Nukreipto grafiko vaizdavimas gretimų matricoje:

Žemiau esančiame paveikslėlyje parodytas nukreiptas grafikas. Iš pradžių inicijuojama visa Matrica 0 . Jei yra kraštas nuo šaltinio iki paskirties vietos, įterpiame 1 tam konkrečiam adjMat[paskirtis] .

Nukreiptas grafikas į gretimų matricą

Gretimų sąrašas

Sąrašų masyvas naudojamas briaunoms tarp dviejų viršūnių saugoti. Masyvo dydis lygus skaičiui viršūnės (t. y. n) . Kiekvienas šio masyvo indeksas reiškia tam tikrą grafiko viršūnę. Masyvo indekso i įraše yra susietas sąrašas, kuriame yra viršūnės, esančios greta viršūnės i .

Tarkime, kad yra n viršūnės grafe Taigi, sukurkite an sąrašo masyvas dydžio n kaip adjList[n].

• adjList[0] turės visus mazgus, kurie yra prijungti (kaimynas) su viršūne 0 .
• adjList[1] turės visus mazgus, kurie yra prijungti (kaimynas) su viršūne 1 ir taip toliau.

Nenukreipto grafiko vaizdavimas gretimų sąraše:

Žemiau pateiktame neorientuotame grafe yra 3 viršūnės. Taigi, bus sukurtas 3 dydžio sąrašų masyvas, kuriame kiekvienas indeksas žymi viršūnes. Dabar viršūnė 0 turi du kaimynus (ty 1 ir 2). Taigi, į masyvo indeksus 0 įterpkite viršūnes 1 ir 2. Panašiai 1 viršūnė turi du kaimynus (ty 2 ir 0), todėl į masyvo 1 indeksus įterpkite viršūnes 2 ir 0. Panašiai 2 viršūnėje įterpkite jos kaimynus į sąrašo masyvą.

Nenukreiptas grafikas į gretimų vietų sąrašą

Nukreipto grafiko vaizdavimas gretimų vietų sąrašui:

Žemiau pateiktas nukreiptas grafikas turi 3 viršūnes. Taigi, bus sukurtas 3 dydžio sąrašų masyvas, kuriame kiekvienas indeksas žymi viršūnes. Dabar viršūnė 0 neturi kaimynų. 1 viršūnėje ji turi du kaimynus (ty 0 ir 2). Taigi į masyvo 1 indeksus įterpkite viršūnes 0 ir 2. Panašiai 2 viršūnėje įterpkite jos kaimynus į sąrašo masyvą.

Nukreiptas grafikas į gretimų vietų sąrašą