Hirdetés
(használd a CYBSEC25PH kuponkódot további 20 ezer ft kedvezményért!)
-
Mobilarena
Új hozzászólás Aktív témák
-
Radíros
csendes tag
És (#2385) Joooe üzenetére...
Ez a bitmátrix egy csúcs-szomszédsági mátrix,
amely azt mondja meg az M[i,j] elemben, hogy
az i-edik csúcsból vezet-e él a j-edik csúcsba.
(Pl. ha igen: magas a bit, ha nem, akkor alacsony)
Ha ezt érted élmátrix alatt, akkor a szkópban lehet
a következő megoldás is:
1. állítsd elő a mátrix tranzitív lezártját
2. a tranzitív lezártból könnyen jönnek
az erős komponensek egy rendezésre
visszavezethető halmaz-osztályozással
Sajnos a tranzitív lezárt számítása n^3 * log n műveletigényű,
viszont könnyen párhuzamosítható és a hw-be épített
bitműveleteket is jól kihasználja.
(Az én logikám szerint ezt a legegyszerűbb implementálni.)
Ha valaki felcsigázódott szívesen részletezem... -
Joooe
tag
Én inkább egy bitmátrixot tartanék megfelelőnek erre a feladatra.
A memóriában az is elfér (10000^2/8 = kb. 12 MB)
Bár elgondolkodtató, hogy ez a megközelítés nem használja ki az élek relatíve alacsony számát.
Ami gyorssá teheti a megvalósítást, hogy ha a mátrix azt mutatja, hogy az i-edik csúcsból elérhető a j-edik, akkor a j-edik sort hozzá VAGY-oljuk az i-edik sorhoz, ezzel tovább bővítve az i-ből elérhető csúcsok listáját, azokkal ami j-n keresztül elérhető.
Ez mindenféle implementációban elvégzendő művelet, hogy megvizsgáljuk, hogy mi van ha arra megyünk, de azt hiszem így tudjuk leggyorsabban megtenni. Így processzortól függően egyetlen művelet során nagyon sok (64?) csúcsra történik meg a vizsgálat.
Az még egy kicsit elgondolkodtató, hogy mikor végeztünk, hiszen ezt többször el kell végezni, de ha végeztünk, akkor azokat a csúcsokat listázzuk amire mátrix[i,i]=1, azaz elérhető magából maga, azaz tagja valamely irányított körnek.
[Szerkesztve]
[Szerkesztve]
Új hozzászólás Aktív témák
● olvasd el a téma összefoglalót!
- Új Dobozos PcCom Revolt Gamer Tervező Vágó laptop -65% 15,6" i7-13700H 32/1TB RTX4060 8GB FHD 144Hz
- Új Zsír Dell Inspiron 14 7441 Érintős Ultrabook Laptop -25% Snapdragon X Plus 10Mag 16/1TB SSD QHD+
- Csere-Beszámítás! DDR5 Gamer Notebook! Rog Strix G513RC / R7 6800HS / RTX 3050 / 16GB DDR5 / 512 SSD
- HP ProDesk 600 G4 DM Mini PC, I5-8600T, 8GB DDR4, 256GB NVMe SSD, Wifi, Bluetooth, Win 11, Számla, 2
- HP ProBook 450 G7, 15,6" FHD IPS, I5-10210U, 8GB DDR4, 256GB SSD, W11, Számla, 1 év garancia ( olvas
- HIBÁTLAN iPhone 13 mini 128GB Midnight -1 ÉV GARANCIA - Kártyafüggetlen, MS3330
- Update 10.10. - Bomba árak 2025-ben is! Üzleti - Consumer laptopok DELL FUJITSU HP LENOVO
- GYÖNYÖRŰ iPhone XS 64GB Space Grey -1 ÉV GARANCIA - Kártyafüggetlen, MS2912, 100% Akkumulátor
- Samsung UE46F5005AK 46" (116cm) FULL HD LED TV
- Apple iPhone 11 64GB, Kártyafüggetlen, 1 Év Garanciával
Állásajánlatok
Cég: Laptopműhely Bt.
Város: Budapest
Cég: PCMENTOR SZERVIZ KFT.
Város: Budapest