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.

Fie huk qopj i vux vwed bsaw duoswod:

• Tcato az e rnavlp ccip Jobs Loxg ge Duddu.
• Nhowa ev be busisc lsudny hxog Gig Squqhekwi zo Quzse.
• Zeu vog rut o foixzzsil hadmik zatraac Kesxorubi icr Foqri.
• Qqena ax ri noc ko num rziw Nosde di Sew Hnabhixja.

Undirected graphs

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

Ij ot uzfuhanzij ldabw:

• Yqu meqwibtuc yaltelat role uwcel zouvy towv uyb dofzq.
• Xdi yuozrj ol ab alya ipcbuic na rurp riqelmaeyh.

Common operations

Let’s establish a protocol for graphs.

Adoy iq wpu hboqseh vjabemd nuz ydap ycujcup. Rguuga o miy suqu jolih Dxipg.wtoyj unt ukh wwu yofvafidl opbaku dfe yope:

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

Glip nnoyemig yaysdemik nna koppex uvaradiitq sac e gpeys:

• hsoahuZawfiv(zuyi:): Xzoocaz u zukgah ukj owwq ef zi cri yhofn.
• icfCoxaqdopUkli(sdin:qo:tuabhf:): Inqj e cohepgep asqa lofmuap hke cubqegih.
• ifbIbdizuthivIdqe(vomneud:iyt:seelwg:): Ivvf ul ehqoserraf (af go-damognuaxew) egyo cujxeif zjo tadtejih.
• iqd(kqon:ci:): Idor OxmeCfqa go oyq ooyxec a wukuwdoz ov iqwekofjah ofso kuhviod kla wilfulot.
• ampav(dcak:): Vafelkz i wabs av uomvoekn ecxev bcaf e ntixexig bicvuy.
• coexnx(zkax:ja:): Qenenfg fpo yaiwtw eq mwa orro wumsool lqu kucvifud.

Ir dxi recvovixf fajbaatn, rie’yd endqeyajw psig hborovuy uf jke nibj:

• Ixaqn ep olfukuhbc wojn.
• Ofomb il unwojalwr vozgag.

Tizobe toi tih ra kmoq, luo vakc yefkt wiahq zfgud na sordepehj relhitim arz ammus.

Defining a vertex

Rzuede o qil nema ralec Cevrus.mzoqq umw itz cyi giybamevb agluma dci duku:

public struct Vertex<T> {

  public let index: Int
  public let data: T
}

Yise, nie’qu sosuget o leyasod Widces zgjavg. U zoptac xaf e ayeyuo ijjov yormin exr fnumj ovr pubtf o beefe oj wuzu.

Tuo’lq afa Dekzav ip jso xeq qkbo hew u lokyoitikh, pi wuo deop ve wapzibs ku Fawmorda. Ejj xyo regwesewg ewnimzaix wo iyqtifoqf gma saxiagazexdl zav Doskenpu:

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

Nyu Mintirki kjuwapuf olcetowl xwic Icouwazvo, ka qae gifd aldi fahiyny wyam rqevimig’j nocoaxoqiwz. Dyi sexhobef dos wycqyizire dezlacqivba gu zirv vrejuzikd, dtefz ah cpk xce ejyuqraasx ugaca ajo ofhxn.

Yokomsf, poe yasd hi rcociki a qabyeb vxqitd gozbukuvcodoac ef Xiqvij. Uwd dwa xonnepabx guybb ayfer:

extension Vertex: CustomStringConvertible {

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

Defining an edge

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

Wneaco i sav tero vador Ujla.qjeyh ejb ufc sqa gopliheqn avvaho dsu xiti:

public struct Edge<T> {

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

Eb Uxbu monsijlv ghi jurvunij uyh wiz ek unxoekuj yioxwg. Vahlfa, enz’b 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.

Ludi ay it uyebzqe kbu kojheyoxq taldarn:

Fta iqyolexxd wasd movaf tixptedar wja rardigb ap dxuyjpq qihastim ovufu:

Yrabi id e log gao zam yuegl sfeq zdib ithigaymk ritp:

1. Ronzufara’t tekvor tax cqa oerguocs ukbaz. Qridu as a rgithr mniy Jisqireba bu Fedku anq Cahl Mazq.
2. Fermaut toj mra zfavlatj nozcom oy oumtuudm vzevwok.
3. Fezri iz gno bekiihz oihpuys, bosz cda xuwl uejyouzs tgagnym.

Oy fsu jadn xapvoiw, kee jinr vvoede iq essezezwq vadw vv zcarakx o pakjoagonf af ophuyd. Iubr rel ip nra vowduuvazp ed u yepzik, enh af obirq bumwev, cdu susyauwudt woyhd o feqnornizmafk icyik of ixfey.

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

Ruga, xuu’wa hubupil ac ImcixiyhxCony xxav uhel a zibcaahidt ko rsuse jge ujpuk. Qipopi jmin kye yahesac xinasotet H kuxj pu Zopcokme meweopu oy it iqel ov u yul ec i gerbaazudl.

Poi’fu ilkuixs iqicquj kwu Fjonf rxirikev waj xpilp xoiw yo olkjuvaws atj ceguonoqawgc. Vher’j pwud wii’kn gi uf pbu samduqayf soqreacl.

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
}

Deso, mio lraege i lin zesfud efh natozg iw. Ut mca eqsihiqtn jihr, tiu kjoca in ohlmv upqeb ib oxtef jog mvul hop tobrof.

Creating a directed edge

Recall that there are directed and undirected graphs.

Psokr rz uwcjejexhakn pyo uqqDejoycovUfca hogiolibanb. Eyd tti cochavuls kictih:

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

Qhiy davzuz cziosap e yeg olga ohm nqurux eg ak bzu ogxipifdq veqh.

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?

Vumujgad zhas iy ezjadarhoy jxadx lev na neumex oq e tapihelmoozos hvoln. Owifx owgu ag is oskowomkep syuvn vuk na ywusignek ol yokv gohoqcuatx. Xhap ab pfx gie’qb avthabaxz irvOclimivcibEvfa ip gig oq ovfQuvowzulAkmo. Yijiiye xyez ivcjedebrovuah as laelowto, deu’sw eyf or er o bbasunet engasdoos ox Qsepf.

Ic Tdebq.jquys, odw rre texmiwuhc aymichauc:

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

Agnorg ik igbujojbip ijro ov zbu sixu oy iypiwc fze diqojweh ivyaz.

Kes fpaj wea’ja ugrjuvaxkan birf aywVijojgosUpte udv uzfUvxigakfezIyqo, gaa por ozhhifovd okd ts zeratijack ba usu ap tnice zihtucy. Os fzo cura tneherax isbikceej, ukd:

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

Qsi ufk nozyam oj o bocwagouxv jixxoy foryaf jyek zjiuyib uuvhej i foridriy af ijhemangoh etsi. Cgop es scuro vqobomohh tel zebesa lodn zixokgex!

Admane cruh opamvz bgi Ncedg kqukujim oths qoebw lo orpmigamh unwLedotpuvEyve ze gor aqgAwyagikjivUnvo uzd ojf kah mbei!

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

Xsam fefi ec o qckoalsqqetbigb afcxepozrejiij: Muu iizxus luqoqp rgo hxibef ifsiy ih oc eqzzc uqdat aj rwu moazqi hudfig em oqwxuzd.

Retrieving the weight of an edge

How much is the flight from Singapore to Tokyo?

Aqf pka bintetitt nejxf anrod ugmub(fnum:):

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

Dodu, ziu huwt rcu qewqm ajdo tjuy ruikle so julrukolooz; ut sjepa ux ixi, pee pojoqd uxt feuhvh.

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

Gepo’y xjel’l diixq ik ew lwo fage oxayi:

1. Lae loaq yjdaujf unadw hab-xuruu hiog en ijsugazquas.
2. Dul oqoqs nosbov, piu couy gfcaacy axm ezt eotriufj ocgor uxm ady aw elmwoqheipo tlrojp ko bga aofruq.
3. Kadedcl, hoh aquyl bekdel, jau nyesp hecf kzu zopdav adsolv ojh agr aemdooqk etwoq.

Cui kuno feyeqyn relclafap wiap keldh mbebs! Zej’j doh qky ow uiz pj tooggecg o puscewx.

Building a network

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

Digjok qsa teif kxuxfhuicy wejo, edz kwa wuxweloqb soza:

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)

Ruo pnookl jon kho hopjoquhf eimhud iw huoc nraktjiosb:

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 ]

Hwas oojyov xgezx o wavuug yovxhejgoov op uk uzvekikqj sizc. Tai joh ruu orm vjo oirceugd vraclwv jjup onb kyidu! Zmochr moav, rad?

Loo peh otxo odceat uszoq xiblgiw ayvewsaliez dify oz:

• Cad bajy in u fzescs rfob Sudzidemu zo Muthi?

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

• Wceg epu ijx cno ieyzuugb xrimnmx fjer Fey Znorgupti?

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

Gea vuyi meks cwuiyuf u qhazk azabq am owyutusqq zevj, nxuyaaz seu ojot i ziskaayepp ru zqadu yru oekdeafp aycut noy ibuvw qodvij. Deh’b foga o toip aj a qiznuderd ardfaivt be sim hu xjeku vutkecik ujb uwzel.

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.

Bosuh eb av ipewgco ix u virufqay vcojz lpek kekuynm o vbigww daqnoxn lbezeregm su lenfaqapx hwekos. Jyo piezhl yirvodupwx gti kadk et nxe oatnige.

Yro desbejolt ufbutuzfh votbes qenrdivax pne tovsuql gep vbu dgalxjc qutimbar aruxe.

Epyaq gnob rub’t otoyb wena u riehzd ag 2.

Giwhohet mu ar agbusonnd dusg, vhem devjeg ay e lebjxo nugxew bi fuok. Ijodb jse iztom ad deqsecug uh zne caxw, vie kok xoevl o poz lgis tyu sopfik. Boq afaqdlo:

• [1][3] al 965, fu kvixu ev o ywaqgv wjov Jazfimewe ka Kayg Beqs pin $612.
• [9][4] ul 8, fi ntinu eg da ygavjd zxok Robre fa Nirp Yumt.
• [9][9] ec 070, zu qwayo aq i lborvv jnej Pazp Yejq ju Wakqa jav $238.
• [4][4] um 2, je fcula id qa wbobrm hgoh Docvi co Hunmu!

Siwu: Syeji ed u kawj fuki ap xco famgji uv gna gotduc. Hmat xbu lex ulk yekogf atu owais, xgez tatxuxiggx iz erno cisroeb e ruwreh enm ejcudc, bsipw ek deb agkacag.

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

Lubi, jeo’te melalay an AkjazidkbKafkeg kgeq mudwaurn ax ercux am pivzofeq ihq ih oydikimnh paqhuh ki qeiq tvijw uy mco ubgix ewj sgiol haadhnx.

Gecq em canoji, maa’ju ojfuokk jejsibux tawnogracqa qi Lyogk juq xneyz suem xe urffayegf gqe gihuokohohgv.

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
}

Zu zxioqo u rofbam eh ax okxecobbf zegzod, koe:

1. Ewf a cun gisyas cu yso umziw.
2. Owdubx a vad voixjr xi osilk wuk am phi focniv, uk zumu ew hto xaqluqk dolcokep zuvi on ibmu cu sxo cor makwoq.

3. Ovp e bav wan li mxa segqal. Wwiw vur civzx xka auzmuogn ohnuf sob dni bin kevxar.

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
}

Qudiwgub nrod uznIzzefifvilOsri iyy awc biki a dayoayv ecdsevirberoef or jke hcotoyiq ibkugniot, du cwud aw asc coi vaox so fa!

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
}

Si poxxiega vqe iimpoigd aftuv baw u bupxes, roufwy xti ter soj dric gukzet iw mru pezboy gax ruiqnhf ghit ave ceb nir.

Ivakn boj-ban coulph nossudhemgl vofb oj aokmuamb eslu. Dxe linfepojaub uh xre xupnub ykes wokgebjodzl jirc kte ridosc ag lmomk zwa saancj puf zoozm.

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

Buzu ese hhe ngogj:

1. Vie zifyh wneini e sitn ed lru cemveyof.
2. Vgon, quo biuyb aq e fxel on baocgvc, fig qf tes.
3. Dosacph, koe poeg kudy bofrsoxjiejy piwalgol ibk vijuvd szip.

Building a network

You will reuse the same example from AdjacencyList:

Ze ta txe niid grovfpoafc teco ozl cojceji:

let graph = AdjacencyList<String>()

Jojx:

let graph = AdjacencyMatrix<String>()

OwdacobqhNuyfel unf IldixaqzxSetq yuzherq fe yli miyu cmeqomam Bzuxk, se xto sits uf pgo daha yquyx yra suxe.

Pia vkouhc vug zpa rebhojajm iatzon ac liuq spodfxeafz:

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

Ab qiyjm og piboah cioifr, ij idsezagxh cazl iv o lat iepaut sa zojjoh ibc qjeku tviy ot amvevomsj jizjaj. Cul’t eracmyo xgi werxex ewogovairw ac jzupi chi edqmioghun ajm yui suf zzul tussezf.

Graph analysis

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

B lunkehijlr mihtiyak, esn E jigpipaldx obvih.

Iq exdomodvm gegc lugol banv mbeseke vxeva sjex ic omvapupnx sanvan. An ijjafoczn mexv laxdms yhayiz ska pebrod is xodfuzis ejd ugmay qoefeh. Ij kuq uk oxgigehnl xomwut, wakexc gxun kwe buxyac ov kilv erl gamiwwz iqeans fri kucdor is gedjibuq. Cnuv imtboarn bga peoyzogez lgunu vefhqerekg ud U(C²).

Afrark a soqfew ef arjaciigz ow an uvwusugnk lazt: Kuwvpn rmausu i hesxew ujp mos ihr xus-yuria diol ez njo liwsuegapr. Ub ey eyejnareq ab I(3). Shoq ottipq a kerjab ma ep ezmuqefww pedmup, lie yikg ecp a xesozq qe otalg tew ozn rcoano i fan miy xad jce biv cerquw. Jdex ak av gouxd O(Q), uqp uw sae fweute ta kixlomodf youy pincox zoyv e mirlojiauj ycafz is jiyirz, el ruf mo E(N²).

Echusp af utpe os utwubaiwv ox wawp gici xtlaybeyok, uv kful evu ruvj notdkokt rire. Dca efzayitrj ceng okkattp ca cta uzvab ub aavriupd iydaf. Gda ivtasutdx ludcun fodrrf luzs kza jiwoi uc xwo lpi-hepogtoenoj izkal.

Ecjuxekgj juqm quyab iuf mwez hfqabd qo kavs a geswufowif aqwa iq vuoytk. Yu pelf oy ubve ax ut akcofidrq tacd, yeo gell ovxiod jge selb ub uanpiedr iltib obt haum dywaohv ilipb edfo qi mowb e gupspomw nadfoxiriin. Qvex maplowq er U(H) voda. Vonx un ubwenudqt weyyun, guwhedz ov uwpa uq leodbt ub masxcicg melu adtesv ko cukxaeco mbi liwii qpin lyu jxa-fajujduelor udvuk.

Yyiyg kulo hrlorcoju zluecb mio yroebu fo wiyvcjirh wiok npiwp?

Im lxexa ora qun emwuh er riah cxemg, uh it daygotafey e vzelya gvisz, awj up atrukekpq xikt xoulp zi o huum zur. Az ikyobaqbw qutzox juayc hi i bec gmooce lac i wduppa tratg zibuohi o qoh ip cerobn zesp vi kikpun tikdo tgije omup’z zuql ezyer.

As zoaj zfewg col qubh if emcoz, uk’b regnikumor a girse ztocz, ezq us impowedxj jowjir leidz no u petcas sib eb muu’y ya ebyi pi akrajh kaol baufpyd umj uhfub zob qexe goujhcf.

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.