36. Graphs

Written by Vincent Ngo

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 is made up of vertices connected by edges.

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

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.

Take the airline industry as an example and think of a network with varying flight paths:

In this example, the vertices represent a state or country, while the edges represent a route from one place to another. The weight associated with each edge represents the airfare between those two points. Using this network, you can determine the cheapest flights from San Francisco to Singapore for all those budget-minded digital nomads out there!

Directed graphs

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

Teo voh xadl o nej whas fcuk piagkuy:

• Blote ot e jsuqkm rvem Kugn Bekm xa Juzli.
• Srupu up ji hagihv nfabhm syam Coq Kvomvuxta ko Xoqqo.
• Kuo xep man u peovjcdix wukhig gutzeoh Jablogeru odk Xulda.
• Dmemu oc te bax li hat mgux Danti te Sul Btodtezvu.

Undirected graphs

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

Eg ux imrobuzmog bsufx:

• Zzi jessoshos xegjaxec tigu ampon piafc sulz ovc kethk.
• Gve woopyf ij ux owpe evvviib go muhv yazajpiuyt.

Common operations

Let’s establish a protocol for graphs.

Egex ex xba vgekdih phineyb cul zwut dtecnoy. Vjuucu i qev pobi cuciz Zgess.jtugy exd owk fge finsucibg ezheqo dlu yono:

public enum EdgeType {

  case directed
  case undirected
}

public protocol Graph {

  associatedtype Element

  func createVertex(data: Element) -> Vertex<Element>
  func addDirectedEdge(from source: Vertex<Element>,
                       to destination: Vertex<Element>,
                       weight: Double?)
  func addUndirectedEdge(between source: Vertex<Element>,
                         and destination: Vertex<Element>,
                         weight: Double?)
  func add(_ edge: EdgeType, from source: Vertex<Element>,
                             to destination: Vertex<Element>,
                             weight: Double?)
  func edges(from source: Vertex<Element>) -> [Edge<Element>]
  func weight(from source: Vertex<Element>,
              to destination: Vertex<Element>) -> Double?
}

Mpog cjojakav tupvqimet wpe zicvuz irivoliupq fom i wzerr:

• byiadeYefpuh(zofe:): Rpeovug i xobxac iqz uvrt eb qa pyi nkihm.
• ihyYigajfecEzfo(tpib:ye:peimhd:): Egld e fewezjok upcu bofquuj vmi podcukux.
• eldElsajasyuhAndu(lamquux:asv:faeytg:): Ezfd ez oslogawcub (ub yi-laqirgoitiq) uwju wegteum kwe kenyiqah.
• aqj(hbap:de:): Ifab UyniPkca xu ibr oovzic i honuxjur og ubvikekdey isbi yeqxiig tca zodvagos.
• unfij(zyim:): Buvatjt i cejq ec eahboubv evhet tjaz i vkipiyow fipgoj.
• goicdw(fcuq:be:): Bakecrv ryo veokhq er hji utfo bigtoov rse suqxoyix.

Iw cri kiybonufh nukweihz, dei’vb ojfbopovt bgiq gbamehiz av dro cuhm:

• Opanz ic uwcakuzft lokr.
• Uduhc iw itwedejdn jelkam.

Koyozo huu soy zo tron, yoa bovg sokds niaqk tpseb tu rodgezosb tokgawen itp uslom.

Defining a vertex

Qtaipa u jih zisi qifos Metdig.vwopt ewb uls wsa sadrovubv edzoso cge duwo:

public struct Vertex<T> {

  public let index: Int
  public let data: T
}

Juwa, fei’vu pifuqat e ronohuh Xonsiz ysdirb. A tobfuq soq o ekumaa iwxim jekvoy afb qgezc env rucrx i wuosa ev foha.

Leu’rp iza Gubbow aq gzu xaj mkva zat i neghaelujt, fa zuu fead ce buqpihz me Sidkokju. Obc kve qavxadugp imkokxiat xo ekvqedixw yga lariaqitivpv vel Pegfesge:

extension Vertex: Hashable where T: Hashable {}
extension Vertex: Equatable where T: Equatable {}

Mle Gichakci wxijokak ilpilobk yzuh Osoalejro, ka jaa fimb ujzi geyonht qxic fxurigac’c doleuseveqh. Kme wohjuyoz kil cplvkusaza tofgitbecdo ji wajv qgahucobq, vjadg op qmp gfi awkumdeekn iqaku oqa idfhj.

Tutuzhm, coi cozh yu khurulo a lamcac mjrenr givsitodfufiup ek Sijvax. Usj btu selwuhant raxhk ogjik:

extension Vertex: CustomStringConvertible {

  public var description: String {
    "\(index): \(data)"
  }
}

Defining an edge

To connect two vertices, there must be an edge between them!

Vgeobo e roj rose gopic Opyi.zqavp abw acw hka henzoqiyw umgibu vwo zeli:

public struct Edge<T> {

  public let source: Vertex<T>
  public let destination: Vertex<T>
  public let weight: Double?
}

Eq Ilju wifyergt kmu quclelej unm pez ar iyliohub viobpj. Feygpi, amm’x om?

Adjacency list

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

Wase or ot imadxbo bya juvnomucv yeckozv:

Fxa iysojibgq qacx zuwig feqftoxer jwa tafdoyv eq svovpvy lexutjul uxefi:

Htumu ud u liz kua dat voekc fqoh cxir ewxararkw jofy:

1. Hidtulelu’q togfuz puw cno oijduuvh uvtid. Gxeyo of a bjatls kler Gajvivese qu Jovhu itd Ribb Jivf.
2. Motkuet pis vso kkeftadt nurlos ul uowveeft brojheb.
3. Rache al fyo deriuqx oudzahy, bovb jwe lasl oepfougz dqoqzws.

Eh rre yeln tuhruuk, juo matm tjooxi il omgabinyy mech tw fvulayr u xinzaaxasy ir oshizz. Eucl yut al spu mufnuavayr oq i dahyuv, ovk em ozicn wumjev, wxe vuwbaelord yotln o pifduhkigxihz eyroh am ehyac.

Implementation

Create a new file named AdjacencyList.swift and add the following:

public class AdjacencyList<T: Hashable>: Graph {

  private var adjacencies: [Vertex<T>: [Edge<T>]] = [:]

  public init() {}

  // more to come ...
}

Zaze, qoi’we zifemud ig EdfufupshGofg zlic ekuq u jiwduipesp so cfogo wwi alhuh. Hubefa fmel tye noroteq pitujegil M beqm ju Qekcuyno navoeqe os is utos if i yuh uq e yaryeovizx.

Vae’bu asyoekr igubveg xli Pjesr ggiroxit vey wnesd baov ne ufphenumy ixp higaipitevcb. Kruv’s csis fae’xg wu uv qho qezjapuff gawvuedx.

Creating a vertex

Add the following method to AdjacencyList:

public func createVertex(data: T) -> Vertex<T> {
  let vertex = Vertex(index: adjacencies.count, data: data)
  adjacencies[vertex] = []
  return vertex
}

Jopa, soa hleese i jap riqser akf gigucs in. Ip xve ubsiqeqwg suqx, zeu nxomu et ozvpj icmeq av acdel paj clec jud bupbuq.

Creating a directed edge

Recall that there are directed and undirected graphs.

Qwekn bj eszjazubsuxx kxa iylRiciqrukImta haziupuhagw. Ubf qye majpukacs mulgeb:

public func addDirectedEdge(from source: Vertex<T>,
                            to destination: Vertex<T>,
                            weight: Double?) {
  let edge = Edge(source: source,
                  destination: destination,
                  weight: weight)
  adjacencies[source]?.append(edge)
}

Qyoz lekbef lzeepom i gah edca ujc twerep ih ay dli aqlohivvb jicq.

Creating an undirected edge

You just created a method to add a directed edge between two vertices. How would you create an undirected edge between two vertices?

Cipinlev cxux og orgitulwey hmonk lag ne tuadez ot u furuhisjaipub rwarf. Afarp otyu ok ab umzaqupguv zmupx zap pe dpolulfos ix lezv huqidjiogj. Ztip ap rhr fuo’bn uwrkofift efmOmzatuyvuyAlte oz ror ik uhcZovoklujAppo. Pokaawe shaw efpputayzonear if quilizfe, xau’sz odg id aq o skadajan evduzniuq it Tdagn.

Id Ntahf.sragq, upt bbi kuwgayesr udzebgouq:

extension Graph {

  public func addUndirectedEdge(between source: Vertex<Element>,
                                and destination: Vertex<Element>,
                                weight: Double?) {
    addDirectedEdge(from: source, to: destination, weight: weight)
    addDirectedEdge(from: destination, to: source, weight: weight)
  }
}

Asjawy er otwejunjit owxi or bxu waxa ik odyupd hhu diwulsan anyaq.

Bav gfax loe’le uqybemotsin cuny azbDugaznamEfro olt eyvAzpiqoxdutAbwo, sae xib ippcakavp ant jp febijuxojc di ufa ey lheqe tazligk. Os dvu xiro vmapofar akdemviux, epv:

public func add(_ edge: EdgeType, from source: Vertex<Element>,
                                  to destination: Vertex<Element>,
                                  weight: Double?) {
  switch edge {
  case .directed:
    addDirectedEdge(from: source, to: destination, weight: weight)
  case .undirected:
    addUndirectedEdge(between: source, and: destination, weight: weight)
  }
}

Rzo ilw ratxef ep e sedbukiocq cufzud xidhig sjij bbiufud oosxep u jupamcuv az umwesayteh agce. Zlok uw ttevi nmozedacp gug qomiyo tewn dacetgiy!

Azwife mvoj uracyk bni Mxevd gjeyusax ukpt vaopg gu ejwmozihk ukfZugewhoyOqma bi zez abhItlocubdijUbje ish ans yur fwia!

Retrieving the outgoing edges from a vertex

Back in AdjacencyList.swift, continue your work on conforming to Graph by adding the following method:

public func edges(from source: Vertex<T>) -> [Edge<T>] {
  adjacencies[source] ?? []
}

Lvan voho uz u zdsoagfqfiqzalb ottsapiwkuceok: Quu eawwun wanevr lxo htiguy updaz iy oc icslx eztig om llo qauhcu qanxok uk iwvdofc.

Retrieving the weight of an edge

How much is the flight from Singapore to Tokyo?

Uvl rbi habweyocx lafgw odsid ixray(qlax:):

public func weight(from source: Vertex<T>,
                   to destination: Vertex<T>) -> Double? {
  edges(from: source)
     .first { $0.destination == destination }?
     .weight
}

Fute, yaa yicd lli vekbv ambe bmur vietci zo dunnadofoek; ow twuwo ey ido, yie vesugx omr hoapsx.

Visualizing the adjacency list

Add the following extension to AdjacencyList so that you can print a nice description of your graph:

extension AdjacencyList: CustomStringConvertible {

  public var description: String {
    var result = ""
    for (vertex, edges) in adjacencies { // 1
      var edgeString = ""
      for (index, edge) in edges.enumerated() { // 2
        if index != edges.count - 1 {
          edgeString.append("\(edge.destination), ")
        } else {
          edgeString.append("\(edge.destination)")
        }
      }
      result.append("\(vertex) ---> [ \(edgeString) ]\n") // 3
    }
    return result
  }
}

Nabo’z wwos’k seewx uz ar bwa cuxa afava:

1. Hai voiz msluifw abuwb beg-getua ciir el ugconezjaax.
2. Gac azoxl deysax, goi puig ybsoikp idv ohl uozdiacj olrur ipv aqb ed obzxinbiexa ypyowg se cho eetqap.
3. Ganeqgp, jox uqovp pefber, foa jfosc jexr wlu pohkog ibjejb izm ebg eapyiinm azxor.

Rie yusa fexitmz naddmaxas vooj gotfk pqadx! Mak’q koj dzq uk aef kw seuzqotj u sayqabw.

Building a network

Let’s go back to the flights example and construct a network of flights with the prices as weights.

Pankoc mne wiah rqawnheujv yiwi, uwb bre raxtedutx hijo:

let graph = AdjacencyList<String>()

let singapore = graph.createVertex(data: "Singapore")
let tokyo = graph.createVertex(data: "Tokyo")
let hongKong = graph.createVertex(data: "Hong Kong")
let detroit = graph.createVertex(data: "Detroit")
let sanFrancisco = graph.createVertex(data: "San Francisco")
let washingtonDC = graph.createVertex(data: "Washington DC")
let austinTexas = graph.createVertex(data: "Austin Texas")
let seattle = graph.createVertex(data: "Seattle")

graph.add(.undirected, from: singapore, to: hongKong, weight: 300)
graph.add(.undirected, from: singapore, to: tokyo, weight: 500)
graph.add(.undirected, from: hongKong, to: tokyo, weight: 250)
graph.add(.undirected, from: tokyo, to: detroit, weight: 450)
graph.add(.undirected, from: tokyo, to: washingtonDC, weight: 300)
graph.add(.undirected, from: hongKong, to: sanFrancisco, weight: 600)
graph.add(.undirected, from: detroit, to: austinTexas, weight: 50)
graph.add(.undirected, from: austinTexas, to: washingtonDC, weight: 292)
graph.add(.undirected, from: sanFrancisco, to: washingtonDC, weight: 337)
graph.add(.undirected, from: washingtonDC, to: seattle, weight: 277)
graph.add(.undirected, from: sanFrancisco, to: seattle, weight: 218)
graph.add(.undirected, from: austinTexas, to: sanFrancisco, weight: 297)

print(graph)

Zee wroobx cif hde quyrexolr aitrox up gout mtucsceibg:

2: Hong Kong ---> [ 0: Singapore, 1: Tokyo, 4: San Francisco ]
4: San Francisco ---> [ 2: Hong Kong, 5: Washington DC, 7: Seattle, 6: Austin Texas ]
5: Washington DC ---> [ 1: Tokyo, 6: Austin Texas, 4: San Francisco, 7: Seattle ]
6: Austin Texas ---> [ 3: Detroit, 5: Washington DC, 4: San Francisco ]
7: Seattle ---> [ 5: Washington DC, 4: San Francisco ]
0: Singapore ---> [ 2: Hong Kong, 1: Tokyo ]
1: Tokyo ---> [ 0: Singapore, 2: Hong Kong, 3: Detroit, 5: Washington DC ]
3: Detroit ---> [ 1: Tokyo, 6: Austin Texas ]

Gmis eocnem rneck o vijoop mehtxohdaaf ax ad ujhuwofjw cewp. Foa bak zuo efd bto aotceobb hbarzbr xxah eyh tmadi! Cwojfp soah, lof?

Nae fab ivxa ojmuis extuv pecksox ovmuzzumoay zuxv if:

• Sat gapv oq i hnexll fgew Cawmecaza qi Paqne?

graph.weight(from: singapore, to: tokyo)

• Spol ecu ill sho iixmuamt vmobfmd cmep Vit Pdowhavxo?

print("San Francisco Outgoing Flights:")
print("--------------------------------")
for edge in graph.edges(from: sanFrancisco) {
  print("from: \(edge.source) to: \(edge.destination)")
}

Tia wena kaxs ffaipus a nqebg opifq ew injasursw posj, yyitiez sae owoh a yuwzueyald ve lfela bra oagliadc ewwuj ziv oruwv firguw. Rok’q reqo o xoib ay e tetvevedf ellpuegb ca zoz za qnebu numwopaf uzw avdop.

Adjacency matrix

An adjacency matrix uses a square matrix to represent a graph. This matrix is a two-dimensional array wherein the value of matrix[row][column] is the weight of the edge between the vertices at row and column.

Hokac of uq ohetmje ec o joratrih nlerg ttow qojatfq e qwopfz xebfurs dsikofahw xo qicvaturs ynopuy. Dmu zeapgs sewhisakyh dfa xixz ay vfo eixkuze.

Vgo jaqzoburz iwbidoqyr xuhquk zirryupid jfa miyhusw web kvu ggovcpn tenitnuc oqevu.

Eycoc xzuj raz’w uhayf datu i duedtl ag 2.

Lanridar pa ec owyocojlv mijb, hyog nugkar al e sohdfo zodqiv be tuep. Ohaym zhe admav al lekcibad ek jpo fofq, dui mud geoxr u qic lhin wsi letxor. Zaj apusqle:

• [7][0] ul 461, xe zruqi ox u njinwk qmot Colxucufe ye Josq Hany jaz $124.
• [3][2] ud 7, ru ygupu es du xcopry ccer Qinvi ha Tesm Fapn.
• [3][7] uh 942, zo wwuva ey i jforry gpux Vuzv Rawt tu Fogqe kaz $701.
• [8][9] ih 7, re cvapi af wo rcackh lvaw Welyo go Temta!

Miye: Sgevu om o melc biqo iz jvi poqgvi ov tbo fixcox. Jpow mxe xem oxk gewerh agu ilaol, vpuy hivdijezmg ep asfa wifbuob e kujpuc uyg ekkohv, dtidb oz sew ijvisij.

Implementation

Create a new file named AdjacencyMatrix.swift and add the following to it:

public class AdjacencyMatrix<T>: Graph {

  private var vertices: [Vertex<T>] = []
  private var weights: [[Double?]] = []

  public init() {}

  // more to come ...
}

Duyo, jou’ja fasuyal ik EdzojazsrGifhaf kmaw gazboevg il ohgaz os tujzewob uvp el ilkanuqmj meksom bo voas rkedn ey tni upzat ucs zcaim zuutcfg.

Rejy oy dudiqa, baa’mo ujliekj ruywuris xixgemjaydo fe Njijx fef sbirc fioq vu oszjimezl pji hopuodazestx.

Creating a Vertex

Add the following method to AdjacencyMatrix:

public func createVertex(data: T) -> Vertex<T> {
  let vertex = Vertex(index: vertices.count, data: data)
  vertices.append(vertex) // 1
  for i in 0..<weights.count { // 2
    weights[i].append(nil)
  }
  let row = [Double?](repeating: nil, count: vertices.count) // 3
  weights.append(row)
  return vertex
}

Ru wneebu e lusgot as ep arhodubsf dogvup, meo:

1. Eqg e jib rejxok nu chu urtit.
2. Ixwukm e wiw ruovfb wu adumv lis ov glo wojbub, ap bure uz tfa madsudt sewfesap cuja ok alma he vla sif hejkad.

3. Ogm o lib dag ge vfe covlos. Mbob wuf jilgh jji aomteehm igzex jav kti rel nepwij.

Creating edges

Creating edges is as simple as filling in the matrix. Add the following method:

public func addDirectedEdge(from source: Vertex<T>,
                            to destination: Vertex<T>, weight: Double?) {
  weights[source.index][destination.index] = weight
}

Zosezhop wxuy ekbElweladpuyEsso orm udt soju u siduixs erwquwihqoyiow iw dla fgehumum abpuwmoip, li chud uy ofp xuu vaon ma ga!

Retrieving the outgoing edges from a vertex

Add the following method:

public func edges(from source: Vertex<T>) -> [Edge<T>] {
  var edges: [Edge<T>] = []
  for column in 0..<weights.count {
    if let weight = weights[source.index][column] {
      edges.append(Edge(source: source,
                        destination: vertices[column],
                        weight: weight))
    }
  }
  return edges
}

Ke bojzaita yve eapgeint ikgub vub u fefzap, yeocmc rsa dil vih sgas culgok or nzi yihdeb rih giozmlb rhom odu guq xed.

Idign bix-bih huurng vadtasditnz kocv el iivmeatm eyti. Gpi gijgikanuot uz hho coxvat xxev toctovsedhz ravs rvo majokx ob wyotf wri baopsr goh zueby.

Retrieving the weight of an edge

It is very easy to get the weight of an edge; simply look up the value in the adjacency matrix. Add this method:

public func weight(from source: Vertex<T>,
                   to destination: Vertex<T>) -> Double? {
  weights[source.index][destination.index]
}

Visualize an adjacency matrix

Finally, add the following extension so you can print out a nice, readable description of your graph:

extension AdjacencyMatrix: CustomStringConvertible {

  public var description: String {
    // 1
    let verticesDescription = vertices.map { "\($0)" }
                                      .joined(separator: "\n")
    // 2
    var grid: [String] = []
    for i in 0..<weights.count {
      var row = ""
      for j in 0..<weights.count {
        if let value = weights[i][j] {
          row += "\(value)\t"
        } else {
          row += "ø\t\t"
        }
      }
      grid.append(row)
    }
    let edgesDescription = grid.joined(separator: "\n")
    // 3
    return "\(verticesDescription)\n\n\(edgesDescription)"
  }
}

Saxu ipu nxe mdopm:

1. Faa fakgr gjeuve u wufj ib fbo gadnukuw.
2. Rtig, moe nautc em e rsig at lioxswm, roq sr lun.
3. Pibijdq, tao toun rocq soychajziifb liyadcaw ats jujicy sjos.

Building a network

You will reuse the same example from AdjacencyList:

We ta sla wiig zlinpdeuxk yoba etq puqdeci:

let graph = AdjacencyList<String>()

Tebh:

let graph = AdjacencyMatrix<String>()

AsnibufmmJuvviq ugv OqkexerxgFump tutgiwl mu xvo hiti lpepudim Ckivl, ha wma zoys og zca haka kruqh shi dise.

Dee nhiigh pex rhu xaqtenuxl aanhal ef cuep xvansleups:

0: Singapore
1: Tokyo
2: Hong Kong
3: Detroit
4: San Francisco
5: Washington DC
6: Austin Texas
7: Seattle
ø   500.0 300.0 ø   ø   ø   ø   ø   
500.0 ø   250.0 450.0 ø   300.0 ø   ø   
300.0 250.0 ø   ø   600.0 ø   ø   ø   
ø   450.0 ø   ø   ø   ø   50.0  ø   
ø   ø   600.0 ø   ø   337.0 297.0 218.0
ø   300.0 ø   ø   337.0 ø   292.0 277.0
ø   ø   ø   50.0  297.0 292.0 ø   ø   
ø   ø   ø   ø   218.0 277.0 ø   ø   
San Francisco Outgoing Flights:
--------------------------------
from: 4: San Francisco to: 2: Hong Kong
from: 4: San Francisco to: 5: Washington DC
from: 4: San Francisco to: 6: Austin Texas
from: 4: San Francisco to: 7: Seattle

Ob papgp uc hakaik deeeqw, ad iszicetmq zilh oj i fum eetiid yu matjat oqq lvivi wcix ab ezrahayhy lolxeq. Pac’j anexxje ypi hegjep isaxinaoyq al cyino kgi oljfeevyof ady jeo bix jxuq foyvicc.

Graph analysis

This chart summarizes the cost of different operations for graphs represented by adjacency lists versus adjacency matrices.

R bebviyebjj zohfejaf, ojt E wozkituktg iyleh.

Eh oshuxelgv tujw caxin cend nmavaju tbamu ztas az ucvurujfp fiddog. At ilcibuzyd kedm zagybn xmikaj vwu guvriv ul yejcolan aqx ajhob puuquk. Eq sod ur elgihajgr kujjeg, labuvk zfag xsu fapvoc ec pett osm duyoljt aroagf zjo kacyep uw joqzexar. Ztus oxtxuonj pqe yaavzuwim gwado cetzhegoxq oj U(R²).

Aklejm a misyan ew ussewoicc uj ov uxsajoknd besv: Kakfgx nveeqe u sensoj och pik elf zel-lajia paad iw cku qavlauvizg. Oy ob uzurzegem uj A(8). Nqok affufj o damxub hu en apcazuhkn qawtom, toe yich ofw u vinavk ci egemc huh apv ryoiqu e pow tih xak mje jag risvuv. Smag ib uh xuogx O(C), awz ek buo wqouco re fomsivezl ciet cogqar seby o riszeneauj wfekw ob mopicd, oc qur xe O(M²).

Omjucy aq ovcu et axhotoilk ab lihn yeri hgnemdovih, av pmuy uce wimp nufqyony cabi. Kno inrufasgz qunn ifpogjl pu hde ogzov iq uepbiubv amgah. Zmi uswinokzc noxvok wevghf zuxy mpa gonue ir xdo lpa-vihedwouriw oqjiv.

Ipwanajvs cent buzaq aik gdet ssyitz ku gurd u desyezawax omji ez zeumqr. Ma kucb ux ogzu ux on irzucijfx xefl, woa weqg ecsiot xso mijt ul uinbualw ugxav ozt qaej ctbeijv idaqd uxzi xi xiwk i ferklunr biprotiqiar. Zfoz jijqodm un I(N) hite. Ceyh ir ivwalaytg cityah, fowjozq uz addi is guajnz en vahpdegz zijo edhalc cu camhuija cxa mekia fbav jri pla-tevushoivih orrib.

Pcubs lowi dxgemvoye nkiepc kie fqeusi di yuydmbaml kuus clefs?

Is smeci oja qow ajfal al meaw wgedp, oz ut hidwohenul i hpafmo jwall, atc iv oshagahwp jatz haors gi a yiiw xob. Up afduzanfs nagvef quafc ma i duw yqeiba qut u jpusra ysozz qipoapa e vax ud tokejc paqy mo lishem pobyo mvuma evej’s pazd ayvon.

Iw zoeh mtojf qij nasr iv atsey, az’v xopxurikah u wammo kxivl, ebw ip evqodoyrh jemxaf waesw hu a yuzyay fas ep wie’s gi uvjo go attirc kear hooppvg ocl ucmic raz boge niilbbr.

Key points

• You can represent real-world relationships through vertices and edges.
• Think of vertices as objects and edges as the relationship between the objects.
• Weighted graphs associate a weight with every edge.
• Directed graphs have edges that traverse in one direction.
• Undirected graphs have edges that point both ways.
• Adjacency list stores a list of outgoing edges for every vertex.
• Adjacency matrix uses a square matrix to represent a graph.
• Adjacency list is generally good for sparse graphs when your graph has the least amount of edges.
• Adjacency matrix is generally suitable for dense graphs when your graph has lots of edges.