Lumela.
Lengolong lena, ke ile ka etsa qeto ea ho thathamisa lintlha tse ka sehloohong tse sebelisoang ho boloka li-graph ho saense ea k'homphieutha, 'me ke tla boela ke bue ka mekhoa e meng e mengata eo ka tsela e itseng e "khanyelitseng" bakeng sa ka.
Kahoo, ha re qaleng. Empa eseng ho tloha qalong - ke nahana hore bohle re se re ntse re tseba hore na kerafo ke eng le hore na ke eng (e lebisitsoe, e sa tsejoe, e lekanngoe, e se nang boima, e nang le metse e mengata kapa e se nang li-loops).
Kahoo, ha re yeng. Ke likhetho life bakeng sa meralo ea data bakeng sa "polokelo ea kerafo" eo re nang le eona?
1. Mehaho ea data ea Matrix
1.1 Matrix a haufi. Matrix a adjacency ke matrix moo lihlooho tsa mola le kholomo li tsamaellanang le linomoro tsa li-vertices tsa graph, 'me boleng ba e' ngoe le e 'ngoe ea likarolo tsa eona a(i,j) bo khethoa ke ho ba teng kapa ho se be teng ha lithapo lipakeng tsa lithapo. i le j (ho hlakile hore bakeng sa graph e sa lebelloang matrix e joalo e tla lekana, kapa re ka lumellana hore re boloka litekanyetso tsohle ka holimo ho diagonal e kholo). Bakeng sa li-graph tse se nang boima, a(i,j) e ka hlophisoa ka palo ea likhahla ho tloha ho i ho ea ho j (haeba ho se na moeli o joalo, joale a(i,j)= 0), le bakeng sa li-graph tse lekantsoeng, hape ka boima ba 'mele. (boima kaofela) ba mathoko a boletsweng.
1.2 Ketsahalo ea matrix. Tabeng ena, graph ea rona e boetse e bolokiloe tafoleng eo, e le molao, linomoro tsa mela e lumellanang le linomoro tsa li-vertices tsa eona, 'me linomoro tsa kholomo li lumellana le likarolo tse nkiloeng pele. Haeba vertex le bohale li etsahala ho tse ling, joale boleng bo seng ba zero bo ngotsoe ka seleng e tsamaellanang (bakeng sa lirafshoa tse sa lebelloang, 1 e ngotsoe haeba vertex le bohale li etsahala, bakeng sa ba sekametseng - "1" haeba moeli o le teng. "ho tsoa" ho tloha vertex le "-1" haeba e "kenyelletsa" ho eona (ho bonolo ho e hopola, hobane letšoao la "minus" le lona le bonahala le "kenyellelitsoe" palo "-1")). Bakeng sa li-graph tse boima, hape, ho e-na le 1 le -1, o ka hlalosa boima ba kakaretso ea bohale.
2. Mehaho ea lintlha tsa palo
2.1 Lethathamo la haufi. Hantle, ntho e 'ngoe le e' ngoe e bonahala e le bonolo mona. Bokaholimo bo bong le bo bong ba kerafo, ka kakaretso, bo ka amahanngoa le sebopeho sefe kapa sefe sa lipalo (lenane, vector, array, ...), e tla boloka linomoro tsa li-vertices tsohle tse bapileng le tse fanoeng. Bakeng sa li-graph tse lebisitsoeng, re tla kenyelletsa lethathamong le joalo feela li-vertices tseo ho tsona ho nang le "lebitso" ho tloha karolong ea vertex. Bakeng sa li-graph tse boima ts'ebetsong e tla ba thata haholoanyane.
2.2 Lenane la likhopo. Sebopeho sa data se tsebahalang haholo. Lethathamo la likarolo, joalo ka ha Captain Obviousness a re bolella, ha e le hantle ke lethathamo la likarolo tsa kerafo, e 'ngoe le e' ngoe ea eona e hlalosoang ke vertex e qalang, vertex e qetellang (bakeng sa li-graph tse sa lebelloang taelo ha e bohlokoa mona, le hoja bakeng sa kopano u ka khona. sebelisa melao e fapaneng, mohlala, ho hlakisa li-vertices ka tatellano ea ho eketseha) le boima (bakeng sa li-graph tse lekantsoeng feela).
U ka sheba manane a matrix a thathamisitsoeng ka holimo ka botlalo (le ka lipapiso), mohlala, .
2.3 Sehlopha se haufi. Eseng sebopeho se tloaelehileng haholo. Motheong oa eona, ke mofuta oa "ho paka" manane a haufi le sebopeho se le seng sa lipalo (sehlopha, vector). Karolo ea pele ea n (ho ea ka palo ea li-vertices tsa kerafo) ea mofuta o joalo e na le li-indices tse qalang tsa mofuta o tšoanang, ho tloha moo li-vertices tsohle tse bapileng le tse fanoeng li ngotsoeng ka tatellano.
Mona ke fumane tlhaloso e utloisisoang haholo (bakeng sa ka):
3. Adjacency Vector le Associative Adjacency Array
Ho ile ha fumaneha hore mongoli oa mela ena, eseng setsebi sa mananeo, empa ea neng a sebetsana le lirafshoa nako le nako, hangata o ne a sebetsana le lethathamo la metse. Ehlile, ho bonolo haeba graph e na le loops le mets'e e mengata. Kahoo, ho nts'etsopele ea manane a khale a mathōko, ke fana ka maikutlo a ho ela hloko "ntšetso-pele / lekala / phetoho / phetoho", e leng: vector e haufi le lihlopha tsa adjacency tsa associative.
3.1 Vector e haufi
Nyeoe (a1): kerafo e se nang boima
Re tla bitsa vector e haufi bakeng sa graph e se nang boima ba 'mele sete e laetsoeng ea palo e lekanang ea linomoro (a[2i], a[2i+1],..., moo ke baloang c 0), moo palo ka 'ngoe ea linomoro. ke a[2i], a[2i+1 ] e hlalosa moedi wa kerafo pakeng tsa dinoko a[2i] le a[2i+1], ka ho latellana.
Sebopeho sena sa ho rekota ha se na tlhahisoleseding mabapi le hore na kerafo e laetsoe (likhetho ka bobeli lia khoneha). Ha u sebelisa sebopeho sa digraph, moeli o nkoa o lebisitsoe ho tloha ho [2i] ho ea [2i +1]. Mona le ka tlase: bakeng sa li-graph tse sa lebelloang, haeba ho hlokahala, litlhoko tsa tatellano ea li-vertices tsa ho rekota li ka sebelisoa (mohlala, hore vertex e nang le boleng bo tlase ba palo e fanoeng ho eona e tla pele).
Ho C ++, ho eletsoa ho hlakisa vector e haufi u sebelisa std::vector, ka hona lebitso la sebopeho sena sa data.
Nyeoe (a2): kerafo e se nang boima, boima ba 'mele ke palo e feletseng
Ka papiso le case (a1), re bitsa vector e haufi bakeng sa kerafo e lekantsoeng e nang le litekanyo tse felletseng e le sete e hlophisitsoeng (dynamic array) ea linomoro (a[3i], a[3i+1], a[3i+2], ..., moo ke nomotsweng c 0), moo “triplet” e nngwe le e nngwe ya dinomoro a[3i], a[3i+1], a[3i+2] e hlalosang ntlha ya kerafo pakeng tsa dinomoro tse a[3i] le [3i+1], ka ho latellana, 'me boleng ba [3i+2] ke boima ba bohale bona. Kerafo e joalo e ka boela ea tsamaisoa kapa che.
Nyeoe (b): kerafo e se nang boima, boima bo sa fellang
Kaha ho ke ke ha khoneha ho boloka likarolo tse fapaneng ka har'a sehlopha se le seng (vector), mohlala, ts'ebetsong e latelang e ka khoneha. Kerafo e bolokoa ka har'a li-vector, moo vector ea pele e leng vector e haufi le graph ntle le ho bolela boima, 'me vector ea bobeli e na le litekanyo tse tsamaellanang le tsona (ts'ebetso e ka khonehang bakeng sa C++: std::pair ). Kahoo, bakeng sa moeli o hlalosoang ke para ea li-vertices tlas'a li-index 2i, 2i + 1 ea vector ea pele, boima bo tla lekana le element tlas'a index i ea vector ea bobeli.
Joale, ke hobane'ng ha see se hlokahala?
Leha ho le joalo, mongoli oa mela ena o fumane ho le molemo haholo ho rarolla mathata a 'maloa. Hantle, ho ea ka pono ea molao, ho tla ba le melemo e latelang:
- Vector e haufi, joalo ka sebopeho se seng le se seng sa "palo", e kopane haholo, e nka mohopolo o fokolang ho feta matrix a haufi (bakeng sa li-graph tse nyane), 'me ho bonolo ho e sebelisa.
- Li-vertices tsa graph, ha e le hantle, li ka tšoauoa ka linomoro tse mpe. Ho thoe’ng haeba ho hlokahala “khopamiso” e joalo?
- Kerafo e ka ba le lithapo tse ngata le lilopo tse ngata, tse nang le litekanyo tse fapaneng (tse ntle, tse mpe, esita le zero). Ha ho na lithibelo mona.
- U ka boela ua abela thepa e fapaneng mathōkong - empa bakeng sa ho eketsehileng ka seo, bona karolo ea 4.
Leha ho le joalo, ho tlameha ho lumeloa hore "lethathamo" lena ha le bolele ho fihlella ka potlako moeling. 'Me mona Associative Adjacency Array e tla ho thusa, e tšohloang ka tlase.
3.2 Mekhahlelo e amanang le kamano
Kahoo, haeba ho fihlella moeling o itseng, boima ba eona le lisebelisoa tse ling ke tsa bohlokoa ho rona, 'me litlhoko tsa mohopolo ha li re lumelle ho sebelisa matrix a haufi, joale a re nahaneng hore na re ka fetola vector e haufi joang ho rarolla bothata bona. Kahoo, senotlolo ke moeli oa graph, o ka hlalosoang e le palo e felletseng ea palo. See se shebahala joang? Na ha se senotlolo molemong oa ho kopanya? 'Me, haeba ho joalo, ke hobane'ng ha re sa e sebelise? A re beng le sehlopha sa associative moo senotlolo se seng le se seng - palo e hlophisitsoeng ea linomoro - e tla amahanngoa le boleng - palo e feletseng kapa palo ea sebele e hlalosang boima ba moeli. Ho C++, ho bohlokoa ho kenya tšebetsong sebopeho sena ho ipapisitsoe le std :: setshelo sa 'mapa (std::mapa). , int> kapa std::mapa , double>), kapa std::multimap haeba ho lebeletsoe mahlakore a mangata. Che, re na le sebopeho sa ho boloka li-graph tse nkang mohopolo o fokolang ho feta oa "matrix", o ka hlalosang li-graph tse nang le li-loops tse ngata, 'me ha o na litlhokahalo tse thata bakeng sa ho se nyenyefatse ha linomoro tsa vertex (ha ke tsebe). ke mang ea hlokang sena, empa leha ho le joalo).
4. Mehaho ea data e tletse, empa ho na le ho haellang
'Me ke' nete: ha re rarolla mathata a 'maloa, ho ka' na ha hlokahala hore re fane ka litšobotsi tse ling lipheletsong tsa kerafo 'me, ka hona, re li boloke. Haeba ho khonahala ho fokotsa likarolo tsena ka mokhoa o hlakileng, joale hoa khoneha ho boloka "li-graph tse nang le likarolo tse eketsehileng" ho sebelisa mefuta e atolositsoeng ea vector e haufi le sehlopha sa adjacency adjacency.
Kahoo, a re beng le graph e se nang boima, bakeng sa moeli o mong le o mong oo ho hlokahalang ho o boloka, ka mohlala, likarolo tse 2 tse eketsehileng tse boletsoeng ke lipalo. Tabeng ena, hoa khoneha ho hlalosa vector ea eona e haufi e le sete e laetsoeng eseng ea "para", empa ea "quartets" ea palo e feletseng (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , moo a[2i+2] le [2i+3] li tla bontša liphapang tsa ntlha e lumellanang. Bakeng sa kerafo e nang le litekanyo tse felletseng tsa mathōko, tatellano ka kakaretso e tšoana (phapang feela e tla ba hore litšoaneleho li tla latela boima ba moeli 'me li tla hlalosoa ke likarolo a[2i+3] le a[2i+4] , 'me moeli ka boeona o tla hlalosoa eseng 4, empa linomoro tse 5 tse laetsoeng). 'Me bakeng sa graph e nang le litekanyo tse se nang palo e feletseng, likarolo li ka ngoloa karolong ea eona e se nang boima.
Ha u sebelisa sehlopha sa adjacency se kopaneng bakeng sa li-graph tse nang le boima bo felletseng, hoa khoneha ho hlakisa e le boleng eseng palo e le 'ngoe, empa palo (vector) ea linomoro tse hlalosang, ho kenyelletsa boima ba moeli, tse ling tsohle tse hlokahalang. Likaroloana. Ka nako e ts'oanang, tšitiso bakeng sa nyeoe ea litekanyo tse se nang palo e tla ba tlhoko ea ho hlakisa lets'oao le nang le nomoro ea ntlha e phaphametseng (e, sena ke tšitiso, empa haeba ho se na matšoao a joalo a mangata, 'me haeba u sa etse joalo. 'me u li behe "tse qhekellang" habeli, mohlomong e se be letho) . Sena se bolela hore ho C++ lihlopha tse atolositsoeng tsa adjacency li ka hlalosoa ka tsela e latelang: std::map , std::vector> kapa std::mapa , std :: vector, moo boleng ba pele ho "key-value-vector" e tla ba boima ba bohale, 'me joale ho na le litlhaloso tsa linomoro tsa litšobotsi tsa eona.
Lingoliloeng:
Mabapi le li-graph le li-algorithms ka kakaretso:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algorithms: kaho le tlhahlobo, khatiso ea 2: Trans. ho tsoa ho Senyesemane - M.: Williams Publishing House, 2011.
2. Harari Frank. Khopolo ea kerafo. M.: Mir, 1973.
Tlaleho ea sengoli mabapi le li-vector tsena tse tšoanang le mefuta e mengata ea adjacencies:
3. Chernoukhov S.A. Li-vector tse haufi le li-associative adjacency array e le litsela tsa ho emela le ho boloka li-graph / SA Chernouhov. Vector e haufi le 'mapa o haufi e le meralo ea data e emelang kerafo // Pokello ea lingoliloeng tsa Seboka sa Machabeng sa Saense le Sebetsa "Mathata a ho kenya tšebetsong liphetho tsa ntlafatso ea mahlale le mekhoa ea ho a rarolla" (Saratov, September 14.09.2019, 2019). -Sterlitamak: AMI, 65, leq. 69-XNUMX
Mehloli e sebetsang inthaneteng mabapi le sehlooho sena:
4.
5.
Source: www.habr.com