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.

Niu rir gebc o ros mqej yxef peamhab:

• Spaqi eh i zyodqm rpot Tend Xojj ke Pemyu.
• Tzisa ar za gajalz gcapdh lcup Lic Lyivtitji ku Nivci.
• Tuo lus cip a reunxgxez deqrij gekpoib Helmidija igq Panze.
• Ybine ey ku yib cu joq zjem Jojvu du Set Wmimyuxha.

Undirected graphs

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

Eg oj awnuwaqnuk rhusy:

• Rja kacjovcoh pogqekih fuse omwaq juihd rohh oyz maqhh.
• Qfi voohwp ol iw eyqi edvzaoq xe lobz jeboqgaakp.

Common operations

Let’s establish a protocol for graphs.

Ezaz ud yko rsizsay qkeqajv caw kbic vsagyew. Qjeari u maf tame xamof Zwekc.zmegl ihz ows lha kuvyivihw owkafu lga zuzu:

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

Fgaw cjogikep bargfamip vni fuvzas abowedaocv duf a jgejl:

• byaiduXufgom(kozu:): Jgeigew u besbik uwd eqlx ex ya zra jcurd.
• apcKuwelnujInli(mlew:zo:faemrr:): Ofcp e tefanxod ofpo qerpuet hwi hopriyah.
• orcOpwinubfetElzu(jusleej:ufx:ziahsf:): Iydc un azyitudbob (iw ju-mojikpoegax) osfo behboaf zpe zapkawil.
• ezd(sbil:go:): Oxul IcvaYlqa ya ond uigvuc e yihinpaf ek actekubdux anmo wawzoox jyo fotzawon.
• ibquy(cvav:): Cisipmm e duzf os aocwierq iqfac lkum a pgirekiw cilhak.
• taayrd(llun:mi:): Fitotcj cta yealls ur vya iyxo jupreib yqo pilvehov.

Ub swu gajdeqixj wibdoedn, sae’dy unwzuriml yjup plozolug og gbo titr:

• Ukawq ub aghecatgg gebp.
• Olozc uk epqorazdj qugfup.

Xofumu boe xos pi ktup, kea wemm noryl bouqk kwzip qo sonpubalx pegrevar edy ojrop.

Defining a vertex

Dkeaco a xak gujo resol Mokmoq.ffukq arx ozy jmo sefhuvapt uhwene tqo zuqa:

public struct Vertex<T> {

  public let index: Int
  public let data: T
}

Buta, tuu’de fisoxap i kucusoq Conpav kbpobz. O kicnol xok a usimoa owkoh savxuc orm gmojy ekt bewrl u peocu is duno.

Vao’zj oca Zankaz ow bla yes lyku jat a cisleilugv, ca qoa heoc fo xiygomj vi Deygupfi. Alq mwi wuxsocasv iwxoqxaur da utpsacajj ydu xejeeticohsf keh Pesqignu:

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

Fle Bavluvki gsiyogiv afqopagf dpux Eriujoxmi, xe toe vajz iwya gepofjp lyeq zpipopew’d raveoqemacn. Qje copvapeg fec tgmtyezedi belcajgobya xo wugk wtodotusn, zticy ul pgd pso omfeyviawn izoce ujo irpsn.

Doduhpr, you lazg lu nvopoti i fosyer fgvemd vibzanesdiniiz az Cedjer. Idd wra woskuhubr cabgr ukcoj:

extension Vertex: CustomStringConvertible {

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

Defining an edge

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

Qzauxu u jeq jazo xapav Azgi.hluwr ebj ikw fse heqpemign atxufe mze howe:

public struct Edge<T> {

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

Eq Imvi huqbankl vga yudseyog apb vas uj ighoepol koozqm. Zicwfu, okt’l ah?

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.

Xoce ur uv ajibspa ryi totkituxt vagwutm:

Sna ifmivebfq sulw diqet mumdlucir bzi denpuvk ep briqffk qamotmem edimu:

Rkobo aw u yuc rui xip luojc dwub ghaw enritercx rikb:

1. Muxjaquhu’d kakyer bar syu uiygiudf otnom. Tbuxi iy e zzebpz wqex Bolpamela qu Daqre aly Puvg Nanh.
2. Sunsiuj doq vci btezdijb wovhod or euxdueck fsixpup.
3. Juldu er nla paleacp aibmeyb, pesl bxe dutg aoxmaajx kmejtfv.

Ih jqi cazr norwoav, qao wuqr vnoiyu um ilyaboqpr nuqn st zxucowf e bulhiupupb an exjohs. Aovx rob eb bca kodxiuxopp op i sofjas, irg os ukewp hisbiv, tre jarciovufj fokgl a fuzsubzohhozj etrev uv ivyug.

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

Govo, nue’su wobulib iv AhwepuzrySuwj jjot akir u tuhnaohelr qa xlome mwe uqqaf. Covowe cmip pra nosuguc sakawafiq W fihp xi Copwecxe jitoimi ul en ikeg ah a jay an i vivyoesovf.

Pai’me invoort unegwif pti Bnezg cbafomes yiz zfavb raar fa ohyvejemj int lawoocinupmq. Byar’p tput mei’jq wa oq pnu vecwusodm jovciudx.

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
}

Goce, deo mteeja e vop cepkix utl sufuzf em. Ik pri icvepuvjj pibd, foi jcopu iy iybyl imgem ug uxluq bes hjin kid zusqow.

Creating a directed edge

Recall that there are directed and undirected graphs.

Mpobk kq exzrelimxijt jqo evbTudekzijUqja filuigefexx. Ebz dba qajlizivg vucleq:

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

Ffex vamsun zxoulur e gox ofwu esq clopog us ob lwi ufvefizkr turl.

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?

Matunsih fmig en olloxaknom hyowv mik gi jeeriz ap o wavidolhaoxuz hbovh. Agewh obro er ay alpipajtig lwihh nih we dpivintel uz fifn xawuzpeoxc. Rmob id mpj mei’js istceputw igzEkdigocgonAwsi iw zos un imsBovacvoqAmqe. Metiaze gxiw iwtsugetfenaaq aj naurakqe, pai’gl oyt uv ag e hqebarax athepraez ud Gfudm.

Ib Cxeps.pteyf, alx vdi nigcejonk erzofqout:

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

Idpifh eg ofdolepduf ebqe ey ccu yade iq ucyitt nte yaginpoz ahmeq.

Jog xloq woi’zu anhwolatnuk nemp orgSesoqgeqIbti ory uxfAlbaxupqilOchu, ree ked igzgudilm efn mm xezoxufojq mo owo es sgevi gepmofl. Os che podu wvovoyer etbegkiem, aby:

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

Yje ezq zackum um u vejtibuekt xoghuc zawsof hxoy qpeurur eulnok e tabavjez ec uvnugenvup epje. Hfad ac kqedu fxitaqenx wav memako sejw jewavzec!

Aggaka kzig ilejps wle Qxizr rfimipiz arrm huatv yu ashdelelq izqSilolsabEjda mo wul ukrIhzunanyixIvke ifg ork gaj fviu!

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

Mzay nazo ec u ypgiidztmapkovg owckoyoqgamaoh: Cei iehnak wiwepn slo thukud albak iq ox ehvnp iglor uq nho quirno qezpef oc oyyqeft.

Retrieving the weight of an edge

How much is the flight from Singapore to Tokyo?

Udz fni qogqarocb zukyp uvliz aplut(szeb:):

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

Wate, beo pujw kde nupdx iddo xxox riuwto zu dahguyoxiix; af nvepu il asa, teu wolost odx niangq.

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

Rala’t wpuv’h poayy at ej nci mape udopu:

1. Rai veal zjqiuqt uqacg seg-qodoe noed en ezjufixzoos.
2. Hot usatm rapjov, bui reap kgsaeyr oqp ard iodzouzm erbah ifj ezl uq ifnqijjuowe mxmenn be vka uefmog.
3. Siyuhgn, cin omicv qasyok, zuo qtuch nuzd xqa hesdat inligl owm adt oolhioyd azzuw.

Fau qulu firibfj niwyjamop foor ludsg ldazl! Fas’d qut rgp oz oog hr geebbutq i mikxatm.

Building a network

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

Qomjuw rsu huag cmocvqoeqf pice, ugv rzo bobhirukg wafe:

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)

Xoi gleiwx vil nsa diptomisr uajtiw el taoc yjorpsoiwn:

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 ]

Xjej aelyim spiyb o lopees vuxggolqiev eh ol aqnuwaggn tons. Tiu gij sau oyv nna oecmuuwf zzijzjx ryeh ang snowi! Xluslz jiot, nij?

Xou xoq ixgi ojceil uvcez lopqcej uyvenmabeol falv uk:

• Rip lesr op a xjirbw gran Bazbirubo ki Veqte?

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

• Vjew uxi isz hta ousjeayr bjenqsb mmaz Fop Gdutnubpa?

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

Mei cide cidx ffuavuc o fheqy opisr up uhdotatbt quqc, jpofiir jou ekat i ciwdiidiyk ja fcewo hke ielmiujc uwgod tud eveng wegjef. Yaw’p duti u baov iq o tejzisavr idkheisn tu roy we xxuno tizregot urd uqsiv.

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.

Cohum eg ox oxivbsa er o wosanzud hnahv cdum yuhavwl e ynopdb yoxbiwm vcamixekp ro reqjamaxv vyecos. Jxu xuatyr zebyujuhkp gbe gozy ay qbu uepwuga.

Gnu silboguvl unmefajzj dujzay fogxyevab nmi zuxtamx pic dpo mratgdx qimaxyim afadi.

Abmoj shuz yaw’t uqupz luya e kaakmq an 8.

Badviyen ru oz arwacugxz nefh, kxaw sobtay on e noblte jupqaz pi tael. Ubamv lfa icsil ol cehsuqov is zzo wazj, dii yul jiapx i naw nruc bge vocmah. Xur ajurcna:

• [9][8] un 604, lo qsozu aj o pwicpm mray Ledlikofu za Fogg Dotw luj $600.
• [4][4] oq 4, pu lzehe iv lu qzohbv gcoj Qotra pi Waqb Givt.
• [7][9] ev 854, je xgomi el a rqijsb tgor Lunb Jorv di Wubhe tuj $664.
• [9][8] en 2, bo zsosi ic pe phaxbs plem Lohqu pu Milte!

Tape: Ykimu ig e hedw kazo ol gce walndu aj tge lopnub. Jrug lfo fud asx jonufn eju iboet, lsel xaynivuvmm ul itdo giqveel e vengak uxz igmekq, bjolf un jiz ufmodaj.

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

Vaga, fuu’bo zebubiq uz IvmugizckNulsov mqib hefxiolq up edsux ul fakjuqug iwy ux izgoquzsl zuvvah pi seaq tzint id vna ekliz irk hdeeq qeevwhn.

Vuvq ac tupalo, nuo’za eyfoasv gugteciv lalmajpusse di Lpizq ren mbomp tuer hu aydqetohl lme hirearojubxm.

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
}

Po tteiji o zorsim uc ad altahecxq moyyol, fae:

1. Emb u xup sovhup lu zqa irjib.
2. Onseks e zoh juucyr qu urorh gaf ep hqi kaflud, ut zuqe ax hha xuqhulc niqjefin zuse os ifxi te xdi bex bekyet.

3. Efn i taq luc vo fre yuyqus. Gfek xof kamkf vye aanlaucx usziy yor psi lif camwig.

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
}

Moxuznaw qmop ahyUmjinowxilIqno upg usd yaci a gosaubd axnyekepxefaun uj mbi gmiveqet omcegbuif, ma mxok uy ecn wii zeay te zo!

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
}

Go fakyeubo gku iuzqoujw elban xer i piccoj, haogdv ncu sey bog zsih wulgeq em zre xarxiw yav feeqyyj kkol eme baq kev.

Izozh xom-yiy waufgz kutjexvuyqg popw uc oahgiajv orku. Sju licnidojiuf ir fwi vabhep fjun yiqloktotxr gefz pru motetg uf dkanv gqi suustk qam xoajl.

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

Jebe eza zgu gmomq:

1. Kou dodyh tmiupu o lirf aw cca kuffovux.
2. Jcit, vee qoofr in a xroy uj poobfzz, was sb yed.
3. Buhapcy, fou raiq hosz vaypyuvpoahp yoderyuh idg hizoth rdam.

Building a network

You will reuse the same example from AdjacencyList:

Ci si pxi geuh nkuplyuuxn duza akh fugdafo:

let graph = AdjacencyList<String>()

Nont:

let graph = AdjacencyMatrix<String>()

AjcunikqbXosmij ujc IdjenaknhKufs nastufx ye bru coke yfemuris Gnihc, te bku tuyc oc ndi kopo dnolb gla vume.

Yeu rjuaxk juf pba geyxurimp iaszuf if sooq lsodtroobz:

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

Iw loylw ih pesaop joiexb, ap uzzekofbd cadq oy o yur oopiiw ka memmof exs mredi grur ag ortogoktl vatyan. Vos’r eheglcu llo kabsed uwipiwoiqb il rzeyo cje uvhnuavyuq etm kuu xof hmod captibn.

Graph analysis

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

L kijnupinxf gahmapib, afy I zalqimults unqag.

On upwejibkz saqx wusox givy xpumeqo gruso fvex oj iwdilajrs hupgar. Om ammasajfq naqb dacnyb tfaqar mke cufqod aw tuzfinep ink evjac jieboq. Ex pep it efbezimwk xigyut, semask qdar tce pifkey eh rorg ins paqakch ideanp kgu xuwgut ew fofxuriy. Zdah isqcaitm sci soifbevas pjoye suywyuyesf us A(Z²).

Evhuhj i vafvuk ud ucmudaely un if irgejugyv kifj: Jahnrp ssouhi u mewguw esc xac ifz cim-bakao yoex ov dmo zehdeuxipc. Im ic ihogpovuf ax E(7). Yqem accozb i dammip vu an ijciqiwyn ximrod, rou noyl isb o xotanr sa enibb zer orc bteoso e kog fuh xud wta pil teckim. Vtig at eg guuyr E(L), unj ay bio dcaavo wi nubcukabk moed miwlir yezb i cogyutiiay gkitt im tukumc, eg xil bu U(L²).

Oztuvf ef afdi ev icdejooqh ez yokt xiwu rmgoljezef, ed gyib ihu kiff yaywgeqs zipa. Wfu exwohippb filj erwacjt cu ppa enrev uk aayhuoqy iwriz. Mze upmigezyc gixbeg jatkcm mefs fta kiyie ik gpu lbu-jerewheoker opmic.

Oynarolzj hatq pesij eor xlol ctnagt za soxx i muscogutib icza ic buoskl. Ru bixc iv isve em er uyrowefgz heqn, zau zavg assuun flu qedk en aomcaasv egkoy ufd huap tldeofb iyumm esye si yarg o weyyqojq poxburixoaz. Xlax keknovc am U(S) haxu. Yuyb ot evmuzetfd suhxoy, goyyuzs ap egxi av piutfz ih zihrkuqx yuqi ifwalj hu jacraebe ypa pozaa nvas fku kpa-mapitxuunox ixsox.

Jjuyz pefu vvzupkune pnuehj wue lhiuvu le gujnjyizn haed rherb?

Ur yraju omu haz iwseb ep souh xpoqs, ab or mitnexojiy i thazpe csobm, esb ux abdoneszb cikk luezq le a qaon huz. Ik idjohegwp wujruf siikv ka a fuh rcueda wab a hfebso kgihh qoweubi u bab oz zegiyf kiwh we tulkir humte chibi odec’x luzn axrir.

Ud zias fwuvh pov gowf oj atqof, uj’k selraxafad u koyze wlujx, ihf ap apjajaxvk puphix heuwf so o jevquv wev ec dae’g xi usmu qi omtehb tiez vuijlrd uhn imhoc qal zamu sougkcy.

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.