Isang Gabay sa Istruktura ng Data ng Graph

Ang isang epektibong programmer ay nangangailangan ng matatag na pag-unawa sa mga istruktura at algorithm ng data. Ang mga teknikal na panayam ay kadalasang susubok sa iyong mga kasanayan sa paglutas ng problema at kritikal na pag-iisip.

Ang mga graph ay isa sa maraming mahahalagang istruktura ng data sa programming. Sa karamihan ng mga kaso, hindi madali ang pag-unawa sa mga graph at paglutas ng mga problemang nakabatay sa graph.

kung paano makakuha ng mas maraming video ram

MAKEUSEOF VIDEO OF THE DAY

Ano ang isang graph, at ano ang kailangan mong malaman tungkol dito?

Ano ang Graph?

Ang graph ay isang non-linear na istraktura ng data na may mga node (o vertices) na may mga gilid na nagkokonekta sa kanila. Ang lahat ng mga puno ay mga subtype ng mga graph, ngunit hindi lahat ng mga graph ay mga puno, at ang graph ay ang istraktura ng data kung saan nagmula ang mga puno.

Bagama't kaya mo bumuo ng mga istruktura ng data sa JavaScript at iba pang mga wika, maaari kang magpatupad ng graph sa iba't ibang paraan. Ang pinakasikat na mga diskarte ay mga listahan ng gilid , mga listahan ng katabi , at adjacency matrices .

Ang Khan Academy gabay sa kumakatawan sa mga graph ay isang mahusay na mapagkukunan para sa pag-aaral tungkol sa kung paano kumatawan sa isang graph.

Maraming iba't ibang uri ng mga graph. Ang isang karaniwang pagkakaiba ay sa pagitan nakadirekta at hindi nakadirekta mga graph; ang mga ito ay lumalabas ng marami sa mga hamon sa coding at paggamit sa totoong buhay.

Mga Uri ng Graph

Direktang graph: Isang graph kung saan ang lahat ng mga gilid ay may direksyon, na tinutukoy din bilang digraph.
Hindi nakadirekta na graph: Ang isang hindi nakadirekta na graph ay kilala rin bilang isang two-way na graph. Sa mga hindi nakadirekta na mga graph, hindi mahalaga ang direksyon ng mga gilid, at maaaring pumunta ang traversal sa anumang direksyon.
Natimbang na graph: Ang weighted graph ay isang graph na ang mga node at gilid ay may nauugnay na halaga. Sa karamihan ng mga kaso, kinakatawan ng halagang ito ang halaga ng paggalugad sa node o gilid na iyon.
May hangganang graph: Isang graph na may hangganan na bilang ng mga node at gilid.
Infinite graph: Isang graph na may walang katapusang dami ng mga node at gilid.
Trivial graph: Isang graph na mayroon lamang isang node at walang gilid.
Simpleng graph: Kapag isang gilid lamang ang nag-uugnay sa bawat pares ng mga node ng isang graph, ito ay tinatawag na isang simpleng graph.
Null graph: Ang null graph ay isang graph na walang mga gilid na nagkokonekta sa mga node nito.
Multigraph: Sa isang multigraph, hindi bababa sa isang pares ng mga node ang may higit sa isang gilid na nagkokonekta sa kanila. Sa mga multigraph, walang mga self-loop.
Kumpletuhin ang graph: Ang kumpletong graph ay isang graph kung saan ang bawat node ay kumokonekta sa bawat iba pang node sa graph. Ito ay kilala rin bilang a buong graph .
Pseudo graph: Ang graph na may self-loop bukod sa iba pang mga gilid ng graph ay tinatawag na pseudo graph.
Regular na graph: Ang regular na graph ay isang graph kung saan ang lahat ng mga node ay may pantay na degree; i.e bawat node ay may parehong bilang ng mga kapitbahay.
Nakakonektang graph: Ang konektadong graph ay simpleng anumang graph kung saan ang anumang dalawang node ay kumonekta; i.e isang graph na may hindi bababa sa isang path sa pagitan ng bawat dalawang node ng graph.
Nadiskonektang graph: Ang nakadiskonektang graph ay ang direktang kabaligtaran ng isang konektadong graph. Sa isang nakadiskonektang graph, walang mga gilid na nag-uugnay sa mga node ng graph, gaya ng sa isang wala graph.
Paikot na graph: Ang cyclic graph ay isang graph na naglalaman ng hindi bababa sa isang graph cycle (isang path na nagtatapos kung saan ito nagsimula).
Acyclic graph: Ang acyclic graph ay isang graph na walang mga cycle. Maaari itong idirekta o hindi idirekta.
Subgraph: Ang subgraph ay isang derived graph. Ito ay isang graph na nabuo mula sa mga node at mga gilid na mga subset ng isa pang graph.