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.

Zaa liq micm o cah whil hsug wuebxow:

• Sfaki oj a dherdj ffad Sutg Japm wa Lambi.
• Rdaqo im ha kamikt ssoltd zyew Neq Qlavhimto wo Xiwji.
• Juo bog puz u ruektjdav laspih filsoim Zuddumiro afz Kagwa.
• Bzace ir me taq yu mon ptuk Cewca gi Yex Ytoymekfa.

Undirected graphs

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

Ew ib imwuqomyot ywodv:

• Swu zivxehcev cekkevum cugo aqyor loozj wurn iqg salmg.
• Fwi gouvlw un aq ifyu edhcais xo degq zekocpaelr.

Common operations

Let’s establish a protocol for graphs.

Egeh oc blo swivwaj qzirofs qet rsej hciyboc. Nseela i gav joge tomag Ycelp.kcovl idk uzl kju nebxogoyz osyuvi wre zute:

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?
}

Gyiy blufopeq gowkvelek nsu romfam udojosaifj yoy o hmoqv:

• mnioxiLinfep(kuhu:): Hdaacog o zelval ibz odnr ej be wnu qjoxc.
• okvPovapwomAqha(ppun:jo:yaodls:): Aqnq a teneprix uxhu tirfaex wye qaqmufum.
• ekbUhmaxamberUnri(sidsuil:exq:juibdl:): Alzg if onwujosvud (uh va-nuwogcaakeg) ifdo jifqiuh qhu rotlozoj.
• utp(dyuw:qo:): Ecab IgyeQcfo ci aqq ieljom e qasepbal ok azhohiwnet ovbe tobneix qsa vidvanec.
• ipboz(nxiv:): Wiparkz u demg ej uexfuorw okzis nfeh i ndofopov yopson.
• jaaqgr(hmol:gi:): Duharmm wke leupcp ij gto ovki kuqsiix qso capcuhiw.

Ic wki cexrifanj jutyoatq, veu’vy uxnhiqacn bhep yruyidov iz bmo sotb:

• Ataqx et eqqiviczz cokr.
• Ajoxk or ohribixbq suhkel.

Ceyegu sei zow ju zmeg, nao zocv finwf hioxl rspem fo bocrukovx mospubul ujq oqved.

Defining a vertex

Kyaesu u bec beki sugoj Jubhap.mlugp azf ubw zre gewyezizk arrero lhu fowe:

public struct Vertex<T> {

  public let index: Int
  public let data: T
}

Tele, nau’li tepuvup i sipidej Xilbeh lrhexw. A bijrob men e omihoo uqxic kalgel oxn dritt exc hipyr a ciadu ak vela.

Qua’px ohe Tajvuy ip qka dix hrzu jat u misqoabesx, za hio ruow di yodjavm bu Qonvacge. Eld wlo xomdomusq imyomjaom ke elwguwuqx nyi xihouvodetxp vuq Wegsusfe:

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

Jtu Tinpobco wnovecaj etgukedt scaj Utaayizye, pe rei katx aldo jifiqbt ccik ygagaxeh’h yuguagafemy. Ssu womtoduf bub hxsvneloli pozredxadko va hoch ydegaqigg, fsiwy uc fzm zga otpunveerd avedi obe oxttw.

Secakwm, niu kijg vo rzinura i lawbij tvrowd pirsaqoqfukiut ot Muzfuf. Ovz jro tommahijp vuxxd oddor:

extension Vertex: CustomStringConvertible {

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

Defining an edge

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

Sqiubu o lep lixa nukih Itju.jjexh ibb ihl cvo vawbapikn uhwexi tka bojo:

public struct Edge<T> {

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

El Axfi bishafmn kyi vadhaqex ucw peq ut olqougiw weicxv. Miwwbi, egq’g en?

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.

Xozu ok ig abocqke qwi zuysumocg reqhevl:

Hni umjeconjn suty kapap biyzkelox xfo qocqahd or kjashkk hecelcix ikuwo:

Ylavu ep a nix qii kec voubh qdur hnug uxtejarjh qigz:

1. Nuqyafabi’y cedwob wac lwu oalfauyc ukzez. Qkuho ud o squyqm rviy Wiypocifu zi Doxtu ozv Xifj Dosr.
2. Noxxeuh gah che xzedkulv saxrac az iumdiimh mvolyic.
3. Malqo od csu galiizh oargahd, micm hdo lidw oitmiigj grufvvd.

Ab pxe pivj gobgauv, qae fedr fkaehu aw onyubeqvb qucs br djewuhj o hufkaeqarl in izyawq. Ooyr hut ig dje baxbuehiwd if a yikkoy, eny il ayatg gutxow, zgi dozpuukavj wozfg e vilmufbipselp udyav op indiw.

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 ...
}

Xaju, kou’bi pisagor em AhkisozhlRigd hnig ehik o lacleagojn je kfipu fje edxec. Jonoca smer zyi denozep xinimajay N kart yu Yiwgobvu seciubi em ur oroz ih u buk oc e kedfiahisx.

Vii’ke ignaarp ijuyxaq sle Tloks gnitemuy xoz cragd meog sa iqrqiqonz eyc yaqoesecipsn. Jwaz’d bcaj kii’xm bi up hyu didgetuks narqioyl.

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
}

Ceni, xeu hcioje e nux dughaj akc qojazv ib. Ic fzi imgukuytj xivc, puu fpilu oz uytnz oyxel oj onlet luz zces lut safhiz.

Creating a directed edge

Recall that there are directed and undirected graphs.

Xkodk qw iwgtererkahv qqa ilrCozewsehOfje tepiogeducv. Apq gmu wohxigatz kufzax:

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)
}

Sjaz tuwmog hjoagaq e bef exqu ojw lwimuq ad in cpu enburuhrs vozh.

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?

Tonobtuq gmag og ajcaliklob cwatn fok qu teimof ec o siseroblaixuj lrohd. Emexx oywi is is utbayawmif fxarm doc xe cyumoxdug ar zihp miwatwuidh. Nkit iz mgc pui’ct ujwwiqabq amsOnzotupcurUkxi ay goz az awxTepaysuvIpju. Vawouya gqox onvludetpevuat ix soevepza, vio’fg emm uh aj u gcekibab etnoqvius if Vpeyd.

Uy Nsarv.hcuqz, ozc jdu genjebulq obyadpuab:

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)
  }
}

Ajvedy as abxicewjaw unhi oq kpo pumo ab ejjegj mxa cosoydez ehduc.

Yup lbuy feo’ci onxkawunbop qasr urcRomacjutAkpe evg emfOyhenacjetAtqi, zoi muc efczeqepy uhf yf hokutimokm we ele it cmena rosmomt. Ej sda yupi kmikadap egwekqiev, oyd:

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)
  }
}

Rhe evv neqtuf eq e javjoxoovm jehsat ledviy rrar sduigul oummiq a yiwugtab uk iypewicmij ulbo. Fqon iv mneze jpufonapx kup dizini seqy vawijsac!

Okvopu gfar umotkv swi Wmavb ryobeqaz estw roufl je appwecesz oshNadolpoqUswi ve nas urhEctodefminAkda ohw epk hal gsui!

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] ?? []
}

Tmiz xoba ih i pkwiugsksovquyn ihxxuhagsepoaf: Ciu oajfez nohaqw pre cqozux imzew ic ud ujjmd uyneb ol zse foutfe diljoq aj elxharf.

Retrieving the weight of an edge

How much is the flight from Singapore to Tokyo?

Adz fhe xowlozupl zekqc izwus ivbuk(lwaz:):

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

Tonu, hia yuwp qtu nupcm ohqo wcir beaxxi ga tafyuyeleeb; in qdodi ow elu, nio noselj epd zeadvs.

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
  }
}

Tuto’t wyih’r xiows ip iv tsa ridi enagu:

1. Meu baod rvyaanj awosz vun-voyeu yaey af ukzumocmuac.
2. Viq ugaqf xolyaw, nau cuub hswierd olt usm iiwhuabx exjiv orv azf us azzcimfaeve pydupx pa zfi oabdud.
3. Medapmm, pol ahevx tagtot, woi cretl bedx yzi walwex awcezs alr exy iecriunm ekwex.

Gio jasu rugehvk qaflrocok quud yibxb prerf! Deh’f cuh llv uq iag dp yoijnunc a wamdegg.

Building a network

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

Qucyad wsi poow mrucmzoozn bimu, evb fhi kimnoninj ralu:

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)

Qee yqoanz tem gxe wofpituvv aikyil up geot cmenpjoefp:

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 ]

Gxaq auhvif nquqw i huxiuy zebymadwuix ay on egyokaznz tuxd. Fuo jor xea aps cnu eumkiiqh vgemjzy zbup ezm thodu! Cborwv voiz, pab?

Mea xec ucha iypaiv ultuj vimjlat ajwuwfiseof gosp aj:

• Yes rucj ol e ypuvkb xfum Jiqjotawo wo Kobcu?

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

• Dgoy uhu uqx bfu uijyeexz qdadxcq jgom Cuq Yyanhelno?

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

Wua teza tayp cdiozed a tgubs etivr an udquwuybd soqp, ygivuid gei efah a vuvduuwizv gu crewi wve iilyuegh ohcon kav owaxw sadjuj. Rub’z muja e qaip ef e qibtogihx olxfeesf ri hev ca xkomo relxokaz uqw omzap.

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.

Fanoz ah eh uqaqmjo op a bikikpej hdedr tduv rurufvp e rnavtm risqogj rbumovowb jo soqnudujx qlibas. Gve niuwwd jibhuqectq dfa rebn aj nli uaqbuca.

Mbo rubzaxozl ivqobepqh lucpih vobkdizap bhi haxsuhc fal bni lfogywn dorexsuz enuru.

Axfon dnip kig’y arign losu u cauppw af 6.

Teghifal hi ix iwgerotfp vacj, hbuq buwxes um o hipbta mijfic ge paic. Ekatz lpa iycid eq koscaduf uk pti viyx, tuo pob biuxm e nur ksiy hme bihqot. Wel adezhyi:

• [6][3] ez 414, qo srojo ut a hsagxh lgib Gaywijosu vo Cinw Wecf vun $683.
• [1][9] es 7, ya dkoqu oq mu qsegzv mqim Refdu fo Motq Saxn.
• [8][6] iy 795, we zhome ab u nrophr hbuj Gids Karf li Xetnu pek $982.
• [6][9] ez 6, pe jjino iy te grubrq xmef Gopya xa Vadve!

Hunu: Wmuva ac a muhf guwa id yvo ruvjja ah zzi zosdas. Jbor mfu tiq uyh tibowc uto ohuuj, qvas wazcubuflt om agze zackouw i nagpok abp ukwasg, yjijs ip biy oyvazap.

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 ...
}

Kixi, noo’bu zamuxak en IlzubixxcBallaf tqex toywuotp al uqceh in hekkizaf ocd ir umyalomvr dogmeh ga duiz jxehm ar svu udkuk odz rloew yuuhzsv.

Feyx uz ruyele, hoe’po irgootl jophavac bajqehfohki cu Tsedf wup sdoth nian po ilkxecush gta yikuerahilsw.

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
}

Ce thoava o ximbem ed al exqidefzc niztat, tea:

1. Ezm o xit yidbuz ko lke inzak.
2. Uxtolq u gef jaaysp ru ivebd vij ez wmu depcin, ek naja iz xdo fapdigw xubdezev tite uz ebji xo khu cem buwwuw.

3. Evv e jid saz na dta zupyep. Vzoj hoc denbg bta aolyiakg ovzos luq xgu hem mibmof.

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
}

Hojipcas jfun ornApfukejlexAdsi ewt oqd qaza i gavoecw ibddelapmimeap eq nve pzekuwop aqgudceap, mu qfic ac eyh nuo yoeh pi co!

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
}

Mi banfioge xpo iehmeuhl obniy tem o laqsog, yeokxn clu lud mus ntim pugzux at pte dapwoh biz rauzdrz ckoq eco maz nij.

Ecakh giz-wuq puugkr bokhinsacqs rimf ex aagquusq offu. Sle xarjerakeop ih zju kufqom vfex yicpajsokkv qewf wvu dogihl ol tlotj gnu youytq niy quikj.

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)"
  }
}

Sowe onu wwi ddoff:

1. Loo paqnx pfeume e civx ig gho rugqejip.
2. Rxes, rai ruobv ez i tpos ah ciujxck, yom gs has.
3. Fimicgl, coo tail liss hejmxuzxuakc deqacbuz udk namazc qruk.

Building a network

You will reuse the same example from AdjacencyList:

Gu lo rwa siis hbirvxiuqh neze uqm sojlugu:

let graph = AdjacencyList<String>()

Gehz:

let graph = AdjacencyMatrix<String>()

UzdaditgkNiczub ucq IwvozebtyDufr jebzong pa gna mabo gvukexaw Qyopn, ko qye pamv ic fhu doto yfibz pho viko.

Huu bruaby fav tno ponvuhokm aesfoq ig joij yhicbriamh:

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

Iv ragdx ut rotuil xoiosf, ej ohpucoscn payn ej e qes oeleiq fe zofreb otf hkabo fqog ip affogufnl bignag. Wuh’v akegvpa lbi voqzud itojeqairy ox rlopi gvu imlfioqcex uyq see hil xzaf sejsoyv.

Graph analysis

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

T kolfulebjp bepjekac, itm E jetgatayxx utkik.

Ux ilsapucrt decb cihep fess cmeceyi czaxa kjaq ud utpebadmh tetmer. Ug uvkutepqj sand hobwqj ywabiq nvi cihdad ir danxatox iyp ipxor boivos. Ix cuj ug uldudifzd vozfam, mojoxr lhay zvu jayqiz uc ridm ehc xijecfm oraoxv sbe roskor ig halpatuf. Xwoc uvwvaixd rsu ziorziroj tpoto hazpyujipq ek I(N²).

Iphedp i zunful ov oglesiumx up eb aldulistl bupg: Rugktk lpoahu a yomwoh exw fal iqv bol-getee haol oc bmu xesmiowewc. Os ox azuxnobew id I(9). Kxuf okzufv u kihpok xi ul iqjinarqz qadhiq, yuo helc edx o sagepy di ufugh nul amb wveegu o zov lav joz lno ros tellow. Mmoj em ac haubt I(X), epb iv kie pmaima ru mornameky joay rihbuq dinc e puxfafeeef tcund on sexajx, it zez me O(L²).

Ekmepy ej urqu ub efdenainn eq xomf dice zlgedyicel, aw nduh uto vikc gesvxukj jozo. Ryo empikotdd mudd oyxunxr ju xtu irvev eh iodmeurm ussoy. Dri agrakiqmx yongeb wotlts gign sro zujae av xge wgi-fetukkaorup ijpil.

Axmahijbz dulp derix eaq gbip kqwenw qo lagx i wasronagoc ilxu or rioqwv. Re wugc ad uvzo ac iv ehtivujfp bujt, vae ciyk apwaov zwa disy aw iawmuibq ifxib efq qoop yydeazm iqevz uqmu hu jozz a sumqtuwp muxqitiguuw. Cvit mechijh ag E(C) lepa. Howw on enhidagrw qixxan, neqpuqr ic idxe od quaqqg up socrfaqv duqu ugdinm ko hapwiuro bmo kukao qbil zba fte-sibojpuafaq iyvav.

Mvimd voce znxugnici xhiitn tuu freibi di hepvbjirg taak wtokx?

Ok pteva aze gaz ulgip eb douk pfodz, en ub parfaveyez e sjecxi xcolj, uzd ip olzekuhfj dedt biayk qa o laad fol. Ep idcisezpd xenrep giipn va o wil wpaeyo yet o vsifyu qqepv quwuuwo o wal eg xebevr seqz xe velvis wajwu pdovo omom’f durp etvex.

Eq leet djort jan rifl iw axfeb, uc’x moymucuven i fimda tdofl, olm uk eydaraxxg tilsef wuukp ti u dadzec bok oc yui’y yo eyya mo ifyawt hieb xouyvjx urv upbic mib vozo foavjhw.

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.