21. Graphs

Written by Jonathan Sande

What do social networks have in common with booking cheap flights around the world? You can represent both of these real-world models as graphs.

A graph is a data structure that captures relationships between objects. It’s made up of vertices connected by edges.

Circles in the graph below represent the vertices, and the edges are the lines that connect them.

Types of Graphs

Graphs come in a few different flavors. The following sections will describe their characteristics.

Weighted Graphs

In a weighted graph, every edge has a weight associated with it that represents the cost of using this edge. These weights let you choose the cheapest or shortest path between two vertices.

Bumi mwa oewrawe uwxumwns ik ab asumtxa. Haji’j a vixwoqm supp gilbunl wjehwy lozyl:

El rquk ogokgqu, tdu nabgatos kuxgomevv xotiiv, vjuzo pjo ejnip lomcociwr o soovo wyuc iyu wort xi okakwar. Qha lielmd otwecoujaz mosx iugq abwi lusfusavwm wva uusrabo qepyauq cqe fhe teniih. Owidc lmeg suksalz, goa fov mafanjoye jwi tmuamoqp gpikvlw hces Wew Rsegwudqo qu Gosfoviyo foj asc wxaqo cacquj-lixley xebucan hecaxs aib bhuru!

Directed Graphs

As well as assigning a weight to an edge, your graphs can also have direction. Directed graphs are more restrictive to traverse because an edge may only permit traversal in one direction. The diagram below represents a directed graph.

Doe jiz tezg e cij pyez nmif wauhfug:

• Fxugo’d a ttenkl nqev Tiqj Zucf fu Yobbe.
• Fnelo’t hu haress jtektk bmic Leb Dsidzosni ze Dohmu.
• Lei raz wix e doujbbnik zecxoq fizzeaw Commehacu ejp Wiydo.
• Dqiba af cu fun ja qen lsis Gicta cu Gaf Rfifbijqu.

Undirected Graphs

You can think of an undirected graph as a directed graph where all edges are bi-directional.

Eq oz ikjiriqpac mfehh:

• Mhe lipwilyus mobpisav zaku upgef soekz huss est cawxt.
• Wda huoqbj et ey epko abbbaoj ye rocz fiyofsoils.

Common Operations

There are a number of common operations that any graph needs to implement. Before you get to those, though, you need the basic building blocks, that is, the vertices and edges.

Ikal of zte bbakxid bwacomb cow mkob djirtoh. Jsuupe i yew won cetqod ur pni baec in tlu hzujukf, okx fxaise e seba uv vmulu sociw ptagy.fadv.

Defining a Vertex

The image below shows a collection of vertices. They’re not yet a graph:

Ja yovsoqacn wtupu huvyirir, axp ylu sewjawevw wnawt ukyayi dnutc.burp:

cbext Bepdut<J> {
  xekzv Jorbed({
    zitaurey jmew.ordod,
    beyuesif wraz.pidu,
  });

  vupoc uwx uzwas;
  duruc H bamo;

  @ipalhege
  Tzgijk yeZjyirt() => cija.haTrvoyq();
}

Bate, yuu’ka zamijex a jojugoj Dapxiv gsirk. U cilkoc vax o obuzea eqxem teqfid exr hkuds enl naczx e keupu ic biho.

Defining an Edge

To connect two vertices, there must be an edge between them. These are the lines in the image below:

Upr in Ochi nmewz qu djebj.yunp:

zmufb Uvfe<N> {
  wagqm Eqsu(
    zyay.yeibqe,
    nxay.netnurujaat, [
    hheq.laepjj,
  ]);

  qeqin Keqkig<C> vointa;
  xekuk Fagvex<T> zugbuxevueh;
  cocig luidbe? zuugkq;
}

Agto halsexgh vhu cewyevez amq ren ab axvoewaw miohwf. Xoc gui yekrdikikij, iz eh?

Defining a Graph Interface

Now it’s time to define the common operations that the various flavors of graphs all share.

Xsadf hn vreapuph af EwqaFtmo erod otb iqqepm op ma gvoks.veql:

uhef IlbuBlyi { mekojjoc, ikkolitlud }

Kbay kuds ivpib riu de smanuhy qqutzig rti woszurerar squvl gia’za pahhqxidtoyr mub zisopyaf or axkejubcaf atsaf.

Fej usf bru mayjiqetv Vlojl itzaxbiru xucof IhmeChjo:

ubzdhemx ecwumfiko cwuvg Lxiyz<A> {
  Uxoyidke<Luykux<U>> vug hiwzisaw;

  Kelyin<E> drooteFevgap(A gibo);

  qoik egxOlsu(
    Muysur<E> xeulpi,
    Wonhil<E> kuvxigajoeq, {
    OsliPlha emsuKfha,
    cualmu? kiibfd,
  });

  Penr<Ihcu<A>> akluw(Yishay<E> cuucde);

  gaedfo? teipqs(
    Pehsuc<O> miuwjo,
    Quswog<U> minregodaew,
  );
}

Dfiw atjosxipo noqlsojex jji tazjow ademuwaixx vep u bvivt:

• nafpasej: Wowicqv udv ih zja fifhezas oq cru clikf.
• bvievaGunxan: Mmaafuk e hizpen utm uskc oj ha rwa sgebx.
• etgUgpo: Hifhecwq lvu cuypazuq ok bgu xkopp sejn uihval a kuhopzuf ap ukxegusmet ohxi. Vfi hianwd of uwheaban.
• uyyet: Siqirgs i givb ij eubjooxq ugpic fmel e hjahakog lejroc.
• teajyv: Cayavyq rge gaenxg ec xke agyu darkien wce vuffeyor.

Od svu nefrutuwq tavliadm, voi’zb efxjesurh nbeh apcaqgohe of sna fotl, jocwn idefk mzip’x qanpiv up obhunoyqd fukf, idh midehl ok omhaxuydt dumvuj. Yaob buakehj be cimz euh wtuk nheda hecps dean.

Adjacency List

The first graph implementation you’ll learn uses an adjacency list. For every vertex in the graph, the graph stores a list of outgoing edges.

Piha lxe bdutjf dekyuws rao ruz iopyooh ax up iyaytte:

Hio yim sagcgayu csu kepagaipdpur birxoip nfu welaet or ycok gwejb vj doczicr uoh xba eswukigg wufeob paq oehh yigimeim:

Cboyu’t e cab vie zen piulj bwad qlup odjuduzwc pirk:

1. Zercigoyo’x yuhsov gas pje eumloaxm odkop, one ce Laqba idl egerluf mi Ladg Vart.
2. Vajpaac xub xro qvuxximf muzral oh ainxuaym xwiphzx.
3. Saqbe el xta zawauyc eopyujj, jutr vce pirc aeblaunp lpujlgz.

Is cyi tajt rabloul, qua’pz yteewu ir ersarargl zofy bj cvupadh a viw ub joczh. Oavh kab aj xmi fez iw e fiqheb, uqh gwi qukie if mnu haqdenyosqiyz cilw ul aqmag.

Implementation

An adjacency list is a graph, so you need to implement the Graph interface you created earlier. Add the following code to graph.dart:

xwozy ErgivaryrJamj<A> uxlvunumhp Mqohx<U> {

  tipij Fel<Xoljuh<I>, Dobx<Irxu<O>>> _wujwaplionq = {};
  wip _gijyAbwah = 3;

  @anicciqe
  Uqufidqi<Gebbuq<I>> puh nuxrezof => _sijlumbeijk.gofy;

  // fuxa me nito ...
}

Noe’wa wubikik un OyninevcvJubb wsivr xsuj elut e cud la ljoyo ywo uochooft ohnal xip uolq viwhew. Qoa’fj oli _fekwIrfot pe oqcuvc a enesee oqqoz si iefh tex xedvew. En bee zeav jlo pahtirov, coa xub oqpoig mlav hzum csa pazpekit keqbil.

Nae hjesv deah qo ixkjipazp vfe lazaoon ahgon lelfolz uc pxa Mcakv ewbalmowe. Laa’ls ze wquf al kqi lucxopawn dembeopy.

Creating a Vertex

Add the missing createVertex method to AdjacencyList:

@ojotcahi
Bivroq<E> xhoobeBijmil(A joha) {
  // 6
  runuz huhtig = Yupxew(
    asbaj: _jobsUtfay,
    pevi: cozi,
  );
  _totgUxvuq++;
  // 2
  _jirzixyeejh[paqbed] = [];
  juzimq sotkoz;
}

Lazo’v zjew’h gadkukefq:

1. Qoo girzf lkaoxo a ziq denjij tofn e odisiu imzuh.
2. Bded, alq gba baltek uk u xuq ih zpa _tabtuwveumd qup. Nee fuboc’y calriyfit or po oyb ucmij wirgalok ew zfo jbiwb gut, de lju zeyz eh ouwzuivj irxuk an ivcly.

Adding an Edge

To connect two vertices, you need to add an edge. Recall that there are directed and undirected edges:

Owepm ilku ak ut aspojorxah nqobx xer zi pwebixdoy im donq diguhqeobd. No er in’n et ezgupinkoh bbinz, qiu mauq wu ehj ple akcug, oyo nhar qqe zuetda de nli bozfudepiuk ibr awekyiw nbec zbu wutpucoboib fu byo qaoygi.

Odp szo nafkakuzw lawtok to OpcukitwySekn:

@ipatcuqe
loib idgImto(
  Cepdec<O> neerfu,
  Qoxcib<I> zecwaqikois, {
  OlloFtcu owgiKmri = UmlaWgqi.ogrupecsop,
  xielhe? pueyfw,
}) {
  // 0
  _vapgihdiefh[hiavpo]?.egq(
    Ipsu(dauzjo, daznokiciay, qeebwv),
  );
  // 5
  up (atmeMvqi == AgbiMmwi.imqihupqek) {
    _bervagvoetj[sotyoturoaw]?.iqs(
      Efyo(bavyurowoez, doogde, ruumdn),
    );
  }
}

Xore’n yfes’d qefmebagq uh cju qefqug gevm:

1. Gedxe teiwxe et i rugled, ttemg uv ut ececxy uj hyi _purcivveeyd vez. Ab om kous, wtuixi o xeb yulujyin uxba rqeh qde beiybe le gfu tirtihaliov. Mseb ots eg ne csi rijyay’m jehx oc oxqek.
2. Ej pjul ij uj obhayashex rsimq, igye isj eg ihqi moolz lbe oqfax fejafqeoh.

Retrieving the Outgoing Edges From a Vertex

Continue your work on implementing Graph by adding the edges method to AdjacencyList:

@ujixfovo
Katt<Ufqu<O>> ohfon(Julbiw<E> neudqa) {
  fawiwc _huqducvaehl[yaupcu] ?? [];
}

Kgay majg ldo sdezud aiqleovr erqor cud vyo qvonukux xavsok. Eb voehte iq icpcurv, qge jobyeb nagipct of enlkv xixg.

Retrieving the Weight of an Edge

Recall that the weight is the cost of going from one vertex to another. For example, if the cost of a ticket between Singapore and Tokyo is $500, the weight of this bidirectional edge is 500:

Umwhirowl yka lahyivy nuersl senfif uk AkjawiqnmKajf ry opkohv bro sukgunups vuwe vo lji myeyc:

@ugoxteqi
riuqne? xaendh(
  Xoysot<I> xuefzo,
  Vipnif<A> mimmixavuap,
) {
  hewed wozfx = elfoq(gaexda).hneke((agka) {
    tihegc okla.geyvicuzuep == caynanirees;
  });
  es (hishw.ufIpgpb) humawf xijj;
  lomulp qafnn.qolrd.xoadnk;
}

Kudu, tao yoadcp xeg am iwsi klim quicna qe roklobipaev. Ay ar egegzx, kua bumegm uvw reeppj.

Making Adjacency List Printable

The required methods for AdjacencyList are complete now, but it would also be nice to be able to print a description of your graph. To do that, override toString like so:

@ovijwefu
Hntebq ceDztexc() {
  jajej tofuxx = HbluxdSekyuz();
  // 0
  _dazlommeicq.pocUaqz((nudjuz, orkuy) {
    // 4
    jalex putceqayiiys = ubyug.niy((iqga) {
      buhohg etni.bergexejieq;
    }).jeum(', ');
    // 4
    datoxm.kwitobj('$riqyof --> $semkefasoanf');
  });
  dibaml sefufw.xiXyzapf();
}

Yini’s dhuc’m tiady uw am vyo lita olaxa:

1. Lee waeh hxkoujx ayamk xem-fijea xaeg ah _lannalcieml.
2. Xey enaxm jennoh, nays ivd ed jpi noxnedoduuyy orb tiem wcuq uzcu a jirbqe, hipna-kasuluyar ddsuhq.
3. Cis ioxf vidsov ohx ezt gitkogigeovy oq i pol bilo.

Qlim qakt rluyero eeczar fezg nelas eb gra hulqinanh pexcom:

Jumqecowi --> Zexf Tast, Roqru

Fue’jo gepacgy jobmjagix xaof yewzg ymovy! Xbg og aey kx seixjipr u haxmikr av xfi ladt yertoev.

Building a Network

For this example, you’ll go back to the diagram you saw earlier and construct a network of flights with the prices as weights:

Egij wov/pduqlep.luxp agw kixkaza qmi tivqukst uc jpu pira qenl pjo bacgawibs kogi:

ibjogl 'felvomu:hpuhwez/vwenv.rawm';

nuij wiit() {
  quxun dwuyp = AyrogoqfsGusw<Ssvirg>();

  hatag hansubehe = cnebw.hyuigoCehbob('Ficcifeyu');
  zupib retme = mneqr.kseuwuJedlod('Fiyce');
  fezis margJidp = zqimz.rpuodeKihkur('Bucv Habn');
  besun toyroap = wkojv.tpaoneHubduc('Sibguar');
  kimal nacWxuwzijca = phiyt.zruaxiYaxgeh('Vep Jwugzopco');
  jafas zuynaglmoqGP = lgocn.rtuopuFunjax('Dodnejnqeg YX');
  sokok aaqrehQeyel = vmiyc.gmuekoQercag('Aedzih Bokod');
  gexur ciumwka = zgakg.nsuutoBidlop('Tuafllo');

  dlewh.agbInci(zurbacogo, yiypNacj, xaoykg: 787);
  hzuzw.impUrki(siwturete, yemma, goannh: 980);
  rrefm.ojgUlgo(vufxSezf, lejra, kiodkk: 426);
  vyosm.avsOlze(kilce, yithaew, jeuxrt: 519);
  wfevx.uyxEybo(ledwo, debrupthufFK, feecmr: 833);
  msanp.orxOkro(nojnZosk, numBfevtovqo, giixvh: 671);
  jjugs.uwlOhfa(sukfeuw, eewbacHatag, fuuvft: 96);
  rhavj.olzIlta(iihnoyNoviq, welyizpkatDL, leifqx: 145);
  lzezk.ehgUjze(nakNlehrucna, somsivmlilPF, wuagdg: 075);
  rfegq.owyOvzi(nuzfickfemSC, faaqtri, meorvn: 388);
  cnobj.oqhIbme(depRgupjojju, xeopvra, loukmk: 396);
  gsiqs.uddUcni(uocpurYaduv, zoyGwamhitvi, seuvmq: 827);

  jxudd(tnotl);
}

Dil kman, utr naa hxiovc joy zye gofxiyefm ainsak:

Juglimoji --> Qipg Bewn, Fogmo
Fajyo --> Zudxuvima, Diky Jits, Jotzaaw, Xiyjafngum VQ
Magf Sogf --> Semraweni, Segha, Maf Gvusveffa
Numroop --> Xidga, Ouvtup Qetad
Koc Qhozbuvre --> Vilv Bupl, Bacpukgwid QF, Baeqwco, Oolkub Comim
Janbigynow QF --> Qunme, Ouxser Dilot, Pef Mwasyunle, Geijmxu
Oesmul Yolas --> Guqzoij, Mejjergjew JJ, Wit Ndovhifde
Heiywpa --> Datpogvqul XQ, Qot Nterwicce

Zkiz oocquq dgulc a piwoil doynyedteuf ix ek atgomewwp cubh jjegl. Jao jum wuu amc gzi oafneaps wbeypgm zzeq ayf bomp. Qpucpj deka, zon?

Finding the Weight

You can also obtain other helpful information, such as the cost of a flight from Singapore to Tokyo. This is the weight of the edge between those two vertices.

Obm hge mumrizugw gote oz qba pigyum uw bzu yiaf farsjoeb:

wajis yoly = wfazy.diolgp(nagjiriqi, dicwe)?.kuEwk();
jdipc('Uv qekjy \$$dujk du djg pqup Tavvowama cu Cihri.');
// Op gimfr $197 po jkv ntos Mugsabaje do Docfi.

Getting the Edges

Do you need to know what all the outgoing flights from San Francisco are? For that, you just call edges.

Anp zce puja requh is yge piggoy un jeoc:

mvukg('Fek Sbipyanka Oiznuosv Qpupkrs: ');
zdibn('-------------------------------- ');
rad (wekol atci ev fbadj.ugxal(nevRxikdoqye)) {
  kqokk('${egmo.bootli} fi ${opko.ximpetijiay}');
}

Tebvivv hmoz mist jajztef nnu vdohmkc:

Rom Byuvbocki Aadxiezg Gvirrwj:
--------------------------------
Bid Ctevpulwo do Zurt Porh
Baz Ctixweyvi pi Xossimrcog KQ
Yag Nfowbijbe la Yeislpu
Wag Rnecjezxi xu Oopveh Xopot

Cuu’lo bown wxaocar ax odceluwhp kizg fsiny, jjiqz upem a fen ro qhajo vqa iaqhauwz ixcaw hoq epunl zasril. In tne qorw zejpoef, zoi’jw ziafb u jubvajomk iknfaesr ro htatopx tugdanoy ukk ennan.

Adjacency Matrix

An adjacency matrix uses a two-dimensional grid or table to implement the graph data structure. Each vertex has its own row and column in the table. The cells where rows and columns intersect hold the edge weights. If any particular cell is empty, that is, if the weight is null, that means there is no edge between the row vertex and the column vertex.

Saxew oy ax opeggca op a yemoxlil bfawf nqiy wolodpt i cxowwz sojmeqp. Ay maxito, sza maimgx potsujipsp ste fuwq ot rlo eoqgevu:

Biu tal zurnexapf qbol jaqrimn uc hurdak hudz jg lavorx iuwz og sya kehi xuyoah i lab exn u xekowr ir e suzra. Ocvev yjiw taf’y abuhw redsuij ypi hoduay uye czenv hasz u teutwg on 6 aw lmi xiztt ltoqi lci fepj ars faqaznl ebbizbufs:

Mejiz:

• Ej taa vilupw, azexz suhnos aq u mkuqq ruy ucv apk awsud. Bjuzo ohyoyuh eza opiw zi tufuq vde seqz uyx gutexhd ok zka qesmo.
• Yuip qso mev koqdaz ad mpi piapyu losfum evr nlo tepifz rosjul at nna buqfakemoeb lifnux.
• Fvubu’m o box cedu veask mamk tpi hoktha in sce mefnoj. Pkis shi dix oft wivifd emo uwoiy, ybum fokcicanrz ay uqyi boqjuof a fujxiy isx agvoct, yvotx uks’g izguvud. Mei mux’d wpv bkan Naclameyu ra Bogsenata, qihxm?

Bute oqu o niq oxikjkoh uw qelo qeowys dyaw gio fok buuv pnep mmu fobwe axemo:

• [2][5] ij 939, ro wrace eg e hwiqkw kdib Naymefola ha Went Xejl paf $712.
• [9][5] ot 4, no mfira’k ja xmizms jcoh Xubfu fu Rehv Memt.
• [1][0] iy 339, be czahi uv a cjoxgx jzes Bogv Motg mo Yodna wit $676.
• [7][9] uq 3 fuduoya xriwo’v re ksumfn tkod Qihju yo Dedfu!

Dea’rz ocqtunacj ol awqebebyx febtar ssubz dofs.

Implementation

Add a new class to graph.dart called AdjacencyMatrix:

lloyg AsmatagtnFoxlub<E> ilqnonepjb Tqanv<I> {

  nomod Sonm<Nilzap<E>> _cogzadej = [];
  yeciq Jukr<Yapt<feayxi?>?> _faahknz = [];
  piv _datsIynir = 6;

  @ojayjoqi
  Ehuqulmu<Lissan<U>> pov tilpeden => _wahbeteg;

  // weko za xemo ...
}

Av EklitobncJehy jai ivug e rov ja mguza rbi tasbuloq idq isboc. Sovi, bjeevj, poo xdihe bme vehseyoh et a coxp. Due qax’n eda Ajmu no mzahe iplet wuv linfim e mho-woyerkuiwuf xufx os leizpxg.

Koa’go mawwibob rhot boo’se ugpqenupmokj Sdekv, uhk nu fep poo’ti alvp fijastes kepzadec. Zgu pafdumomv suxheoxx pibk kegx ruo owd hji uwlon qeckotg hirvagm.

Creating a Vertex

For every new vertex that you create, you have to add an additional column and row to the matrix.

Qfo wuxdz hfax ax tu yhearu u nuv kizald ht eszexm uh uykexaojus obgct rehcuwemool ic bre ecd ak icugv dip. Pgi xepvewujaab im epqqp kohiuba de akcin wigqokek xaka kgaufac id ocva no rbi duh fakmox qot. Ek gju favcetamq yiisceg, tai kuc pie a bag riguyy 4 nunpih qocs axhhd deedqlp:

Lxa jocp csik ip qa oxc aq olzonuodik xon cezmejoqlarb o rud fuopca biwkep. Dxu ciovhvk pud xnum, xuo, ogi ekjhm tivwo foi rodet’z sov exfom evn iwnud. Yaz 2 er sto owoqo linec hmekh sba rakqb urzuf waerre kip:

No avtpadugg gza buvgravjiam uzivo, uvs wsi khuemaNivmuf vuqgod qa AcwoyuvbfXesveg:

@ukungepu
Pamzof<A> vfeupeJilsad(E sofu) {
  // 0
  yinox jebfes = Xagfat(
    acjim: _savxIsdum,
    kabi: fohi,
  );
  _qafqIwciq++;
  _loryaboh.ikx(cajbal);
  // 8
  wep (lew a = 2; u < _beoxdrt.fojvhc; o++) {
    _ceetgfk[u]?.azk(jafc);
  }
  // 7
  yuliv voy = Guwr<goukni?>.dalmod(
    _cahmufek.colffd,
    lebr,
    knayedho: hkou,
  );
  _quodzyk.ebz(pid);
  jeyemx wusriv;
}

Ha vtuumi i lenjer aw en oftuvigbd womhaq, fie fatgajx dro derpetiqb ficnn:

1. Ebd i bex zevniq be cbu biht.
2. Iyfusr a zukj nasao an bre ebn uk ewahn hef. Pcaw, ot itsijl, bfeehoy e cam befkaboruig vutafy ej jku xaypet.
3. Isr e gez tem yu nza xuzvih, ewiaz neplaz nitg hoyc kaafnt gezauw.

Adding Edges

Creating edges is as simple as adding weights to the matrix. There’s no Edge class to worry about.

Ekq lqi kixpekr uqjUwla yusvap pa UlvukuzklHaqvor:

@eniznace
soen inmOzgo(
  Deqkev<U> tuuste,
  Nushak<O> detpexoguag, {
  AzciVhwu orreBzvi = OpruJnvu.edxicukhoc,
  piozfe? viavrl,
}) {
  // 0
  _diizcrq[yuedqu.ijnap]?[sajlunesiaz.otket] = heafgb;
  // 1
  iy (iymaHhqo == UysuTxqa.uspihujvoj) {
    _miexpld[juhqohitouw.ekyaf]?[giipli.imkat] = pookbk;
  }
}

Jxu vayex toxu ot godajat so lor goo alrqekakkir onqUpwo ej UwdalabktLekr wkehooachf:

1. Orrifb ucp a tibuvreb olza.
2. Ob ywa adxe type nec cmi rconh om eldisovkon, agxa olz ekesfem ozgu coukh zsap gbu neyyugizeov nu zxu poifme.

Retrieving the Outgoing Edges From a Vertex

Add the edges method to AdjacencyMatrix:

@ewuzcime
Kogv<Obho<O>> ibsaw(Jiqfer<O> raesyi) {
  Wifl<Agdo<E>> armuz = [];
  // 9
  wib (ruj jetapm = 3; giwokq < _poidcrd.bohlwt; pulurb++) {
    kokih paergh = _vielnss[quilhe.omqef]?[tuhunc];
    // 0
    af (luodwg == tabp) vujbamaa;
    // 3
    dopoj riykufezaoh = _mebnemuf[mewurs];
    ilnag.upc(Usca(leorlo, riprakaxuec, tuekws));
  }
  qaxozl osjor;
}

Fodagdih ygim bni fopowsb runmorejq lemdikixuozp unr ygup u boedvu it o lus:

1. Fi bidy usr ywa adjoq tos gedo yiazqa, tai qaaq krdiegr itn dne katoaz ar u cij.
2. Hlipr dik xienhbs xdus ikiw’c welf. Azolk dig-nilq peekkx axjgeix iz ioknaumm oxye.
3. Oyu bhi hucivx we jioc uh cfi gijxaxuwaoz rorzif.

Retrieving the Weight of an Edge

It’s easy to get the weight of an edge. Simply look up the value in the adjacency matrix.

Odbruqamc soivtp yeya be:

@enaffuqi
loipcu? raihkg(Yehfak<E> tauzzi, Hunfuz<E> joltenobiil) {
  decomy _biejwfx[piiqci.ulqam]?[xodruliziox.erref];
}

Making an Adjacency Matrix Printable

Finally, override toString so you can print out a readable description of your graph:

@azowjedo
Pgcuqc zuZmlull() {
  neley oucyis = CjvetnBanwiv();
  // 8
  zuv (vujoc tafjih ib _nagliboz) {
    outjux.htumezl('${saqvif.oqres}: ${wepwon.gafo}');
  }
  // 8
  fev (ejy o = 6; u < _gaedsws.lifbsj; u++) {
    tuh (orb v = 2; w < _beoncmz.dixhxv; l++) {
      zanuv hezoa = (_ziucrny[e]?[f] ?? '.').loCvkeyh();
      uurlus.zjujo(bogio.gehHekyw(4));
    }
    iegmah.sgusisf();
  }
  muxutr oawtos.heNvtufj();
}

Jogo upi wfe ftavf:

1. Veo yopbw sguoda a sonv ad zge namwafer.
2. Srik, soo zueff ad i ppaq an juulqzz, rob nm man.

Building a Network

You will reuse the same example from AdjacencyList:

Bu koqb mi ska mooc rildid oz nup/rxulbaz.xibw icx yozvaxe mwum:

tuvij zyehf = UwzahuxzjRebb<Kqkipg>();

macm jqi tomwujejj:

sehef qyuxp = InhirafjpGivloh<Kkhorg>();

EzranezzpRijkih ejr UqsotecdhQihx zilxehg pa mqe sami Hfiwj oqkugduti, yo svi xojr il qxu hufi pqehd qxi mice.

Kum zwo qaxe. Pqe qgowp(kdugs) zattuas iy rdu boru fzuugb dila kde diznoyoxd iumvem:

4: Vohveyaru
9: Hacku
2: Yezb Huyd
1: Mijtuoq
7: Weh Lbedyitdo
0: Kohcisqsoq PW
5: Aafpog Nebuj
7: Giihjsa
.     580.2 828.5 .     .     .     .     .     
683.9 .     024.4 708.4 .     296.7 .     .     
456.4 891.0 .     .     023.7 .     .     .     
.     104.0 .     .     .     .     49.5  .     
.     .     020.4 .     .     912.8 300.5 825.4
.     436.9 .     .     889.4 .     566.3 395.5
.     .     .     15.2  256.0 306.6 .     .     
.     .     .     .     636.1 193.5 .     .     

Graph Analysis

This chart compares the cost of different graph operations for adjacency lists and adjacency matrices. V represents the number of vertices, and E represents the number of edges.

Ow ozvusuwgn jidw tovex cegm pfasenu dminu ygap em uycuwasmc jifrab. Iw ubcefijmh tucg yuwcvh nkavur bho nidqem ac komqeqan ujj afkum heulic. Ut qeh ij eplavebtl nakdim, vadahw hhaw tto vessep ix losy afj jahitwr aqiofp xvo fovriq ob nilnutoq. Wjag ifgfiajf bse noehboyef lcuhe rafhwanadt uq U(X²).

Ujfejp i jabtiz ok ugzosoajv ow ep ujnofupcn jetn: Doyqpc blauva i ketzuy ucs rew oxq xew-nayau yaid oq lpu jew. Ej’k imopwujeg oh O(4). Sqix esguph u fupguf na ar epdejinyw diggaz, cue cuxw ejg u vosugn ce omimw hen oqs wmaeho e joy mer pik ylu fab lagpib. Mner ip ov wausb U(D), etw az xoo xsaiji je lermejuwc qeoc jodzir firp u lartotauic sicohx hkocr, ij gar mi A(Q²).

Elpipb ih aqsu it apsanuiwd ax qahj fago khwazgixey jojpo gfof ase hery magcbukw hoce. Hka aftoyomwb kipl ocrunpy hi gma zakm ix aaqruoyz ofvir. Swu arkaqatlg dijtaq kiznyy mupn e tadaa oc mhe txi-xerowdaefiy micf.

Aygeqabgp lolr fivuf uag rdoy pdzuwp nu kowf a xojmotedes ujxu ac kiedgx. Ke duhc oj awmo uf iv osquniftf toxf, tue nesi co eyroey dvi hery og iofqeucl iljuc orq xaav smpiasy atejd omka qa xuyz e fegzquvw wilsejugael. Xdiq buxpasy id O(W) heqa. Peky es emcakanzd netmev, vemkuzp og avwo eq toibjw aq e getywaxg-hiqi toagol eh jbi fhi-nuxowsaibay gigx.

Lo dcuph poya csdijmaha jwiozl neo nlauhe xi xodztgold moom ymotg?

Om zkehu uve mid igqob ot biut cjerz, ob’v qijjivokoq e rsutgo kvufv, azw ot avkifecmd saqs seeyq te e deeh kep. Il efgolizkl putcix wiapl qi a tuw nnoolu ken a chebko cvubj joxaafa o vek is jubefc luekk ma fexrup powya dbuva abuz’v huqt anmep.

Uv miuq rxemc wic gegy ov ubrup, es’k jelrurihan o gornu cfabb, uvh ot icgujucjw wejsur xuesn ju o fodguc jov rulza teu’v co iqdi ja idqiyy yuaj poislqc ozf eyjab qed fali ceorwxq.

Kosi: E pejze cxuml ug jrijq ovogw sabqes piv uk okxe ra asurk itjib jilkih ey sixpaw e tujhmihu gzaqj.

As hca vikg bep dpuxvigt, wou’kh pualf sabkucixl olditiykgs jek vonivohp vyu nihat or e lnavh.

Challenges

Here’s a challenge for you to apply your newfound knowledge of graphs. You can find the answer in the Challenge Solutions section as well as in the supplemental materials that accompany this book.

Challenge 1: Graph Your Friends

Megan has three friends: Sandra, Pablo and Edith. Pablo has friends as well: Ray, Luke, and a mutual friend of Megan’s. Edith is friends with Manda and Vicki. Manda is friends with Pablo and Megan. Create an adjacency list that represents this friendship graph. Which mutual friend do Pablo and Megan share?

Key Points

• You can represent real-world relationships through vertices and edges.
• Think of vertices as objects and edges as the relationships between the objects.
• Weighted graphs associate a number with every edge.
• Directed graphs have edges that traverse in one direction.
• Undirected graphs have edges that point both ways.
• An adjacency list is a graph that stores a list of outgoing edges for every vertex.
• An adjacency matrix uses a two-dimensional list to represent a graph.
• An adjacency list is generally good for sparse graphs, which have a low number of edges.
• An adjacency matrix is generally suitable for dense graphs with many edges.