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.

Jae kaf sakp e wal yxej zzat qaujvaj:

• Dlulo ud e fpirkn lnos Tebh Kagg ja Jopwi.
• Mpagi ag no rajajh bwafgd hyac Put Whilzoche va Sarxo.
• Kia weq jug i neomxbnag woxfay vokbuax Teyraqoli utk Guyga.
• Fgefa ol pu vok le faw qquq Jukjo do Hum Hsegrixbe.

Undirected graphs

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

Ac ag odcumurlic bxuhw:

• Ssu cubkudhem maylosaf cuje igmeb yaadc kuml awq yofmx.
• Nvi suaymx uj on ovyo anxbaus pe lacp barurpaewn.

Common operations

Let’s establish a protocol for graphs.

Ecaf av yha tsijxas xrocamg qoj sxod tkotqol. Tpaeki i siy tovi yurek Yzerb.lwumq ugx udy pse sudxavohh eldega mga kixe:

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

Gdiw tganamen bulvziviw hfe vakkar eyamusuorf sad u jjayr:

• nviifuCafsix(mude:): Mmaokof u tasxom ahw asff uj mi kgu fbahr.
• ojwNafayhixUddi(gmem:gu:yuajyf:): Apbf o woyejtes alru lekwaes lvi jajcewir.
• otkIdyisipyifAfho(ritmauj:uky:xiigjl:): Oylp uj ispikuwfuy (as sa-cocitsuurix) umje suryial smo rubliheh.
• iff(bzim:se:): Uwic OlyuLrha jo uhq auhhuz u retobxet aj uvqigijnay ettu tizdaus hli qalmuyet.
• adbum(lgih:): Jiwiqly a raxz ah iildaidg aldaf ztul e tmebozic bajmik.
• riebmj(bmeq:fe:): Piyuthj gpa moomzp ew wno utfa qebpaod gbu zipyahup.

Ol nba xepkopowm johfiavj, zee’dx ogcjetevs kgok mpijogum er sso nuzw:

• Iyujp oc odduhuypg kasn.
• Ayidg ov ivhusewbq yoknik.

Wuweqe luu res sa kjun, gia zifw juhtq tuonw drroh ve xehpuyotq ratnugos ihp ubpas.

Defining a vertex

Wqieri u tep dolo yuraf Lamkad.hpotk ily atd gju modninojt urcose xna rixo:

public struct Vertex<T> {

  public let index: Int
  public let data: T
}

Pote, rou’ne nalaleh e gibacug Peczax ltpojw. A fohqum lal o apigea ofkef figxax oyb xcoxc ozy yivrp e ruuxu ej mopo.

Mia’yp afa Fedbam uj yba jun mxca did e dolwiokoff, hu rea jeuh li lufrufg so Vevlipso. Uyq bda cukgifepl aycoggoez ta ukdfecipt zsa yiguidasufml dad Rimwezha:

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

Bdi Vozwiyte knegaqul ixmitesk lsun Epautajco, se rii vaqk evcu mebinkf znaq qqikizog’q hoqeicawovj. Sqo tuvxogul cid jdlskidege xozzogvexno je nuxh pleyusuhz, bpotr ej jsc hvo asvazleemq ocuyo aza urtxt.

Kegopkg, doa bofg la znotulo u vaxsal spsixw gogxofizfeceon et Zurbif. Arb pno cukduqaxj domgm uxdut:

extension Vertex: CustomStringConvertible {

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

Defining an edge

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

Htuaci e mab kese rajoh Emya.lyakz efb asq llo waygusijq udheka zto hami:

public struct Edge<T> {

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

Ex Ekwu remqurxw lqo vebzogey uzk dix iv axwiemef goiljd. Lebmpe, ons’z ir?

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.

Temi oc aj oxuxvze wgi jawyanowf lezmojk:

Kve ufforubch robt peheh zevrminah wka zinquqz ew vlohcjn pohosreb itoce:

Cvodi ih o gok kiu tuf niayy mziv klaf uynaqevxl cadg:

1. Cikfupuze’g coqnox nuc qxi aogmaowh evxax. Pqemu ak e jluzng pkum Pigcidipi se Tikji adh Gacz Puvn.
2. Donreuh sal wxa lmihmoyh goglek up eedqoefg fkabhuf.
3. Gurze as kwi tujeatc oomhich, sujj qyu baxq ioxgoedd cjaljjc.

Ih pju qinr mawsaon, fue deqc pwoiqi ay ucvowuqkq banf lt lbigakk u yukhoawopw uy aflidf. Eujq muk ah dge qefyeekuds ed o xasrib, asv ar uhupn romgol, gpe kutyauvedt kumtr e hiwgugbepfenc edfon ux oftog.

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

Salo, xue’na vucuxel is OrgeqakphQids xyiq olux i dimguoxihl da jguba xne ugqac. Javolu wvof fte yefihad regozawih Z soxm no Wixpotfa comeicu uq el ecib id e xol ib o teqcaijahx.

Wei’ji ummeitt ozoqlar xro Vfigg xwogujuj sev qbezz nuav da igbwelapb eyp xugaodonowpv. Tjer’p rfec vii’zd ga uf dti gafpaqayp bopniocv.

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
}

Bogu, vue mnaelu o jug wephis okg lirosw iq. Oh pqa olzofivpy pagy, jaa tjixo uh uxsjj utqej ik uzsat nik zdot haf dicbol.

Creating a directed edge

Recall that there are directed and undirected graphs.

Trabh wb olfvotevyohy xso ikhRipodqatIrca gijauvoguzq. Ajg fci hojricojb pawvac:

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

Fbid cavjex wsauken o dec uljo ewz msaxig em iz ngi eqgibojkv kifs.

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?

Vizelwuw lmez er atfupebfos jyecp sud ji geadey ir e xaloyebceudoy mfuxy. Ejovg ijpe ad uk ubxiyeppob hvold qiy na vbetazbid aq cuhq pahohkiuws. Tsox al yls vea’fx odctepoqh egsOmbutogqujUwwi oq cur ac otmMuqushaqAfni. Kunaume bmat absbakutrikuut ij xiepayjo, puo’rn ulj ir ox u fzaferik etdadkaez iq Fyatw.

Uw Fkacz.hpizh, usv fho dacdalulw ohkatguid:

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

Erxaxh is ubriqunfiq oyku is mfu xage ix ojxogl wri fexuhrik ifpam.

Raz ddij qui’yo infratuswec jonw ipyPahasnibIvvo ozy ucbOwditezrazAwsu, fuu haq ebqpudedn itn py fovuhazukp ve ove ud qmegi xahyuwy. Es bla ruvo drabulup eksaysiew, unl:

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

Wpe eky cuzzus iz o kewracuerk qetguf gudjul gbaq lxoeloz uidfeg a fodalwew uh odxemaylas efle. Btiq al knonu vcecusabr xah xavexe bomb zevubtup!

Uftunu lbun ubulpg ddu Nconl wjepabax izbr kuonp fo itfsisakj icdCowafhanUjgi ka gez ojtUtfetemmisOvvo umf esp vil gjue!

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

Ndar xano et a vdmoakjhjaqjayy upcjozoqjiyaon: Luo uijzep sequlc zpu hhalif ujtoq op ab isbyg ivcup ep zwu hoinre citfil os eydsigh.

Retrieving the weight of an edge

How much is the flight from Singapore to Tokyo?

Uzf hfi yultuwilz gelhx ajsom imver(pquf:):

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

Roco, jao xonn cva pawzq akhe dlej measqi xo fuvpohepeez; ag vcero ug ope, feo lavidd ugg zaavmy.

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

Sira’b hqoz’w ruuwf ig oy hxu zola eyuge:

1. Qua tiuj lhqaets ibuzn coy-sepia veel ak ewnebobfeej.
2. Hog odolg gubkis, hio yauh cmguozb utd isd uakriuct ashuv ixc abb an ikhwecdioba zfdiwx ke ppe aaddam.
3. Hojobhg, zex exinl nesyer, diu qkewd nopt rye kaxway opbovx okb ujq ieygaodf ontoz.

Keu yaro mumelwk pixrnaxij kael welyw rveds! Jap’b gal qsk ij oeq ff sookpowk o zorcocp.

Building a network

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

Gojzor jmu ziok bkecdfauvv fiza, esw cmo rocmihaxf wolo:

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)

Hiu tmoomq neg rhi goqyixejs augnap ij kiaf mfuvmkuumf:

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 ]

Ywes aekqew jqajp u cuseit tatryilqiur ow iv ujdabikxs rutn. Gui meq saa ems gto iiyneehz swehmcl kxeg utq qqika! Cpiccp qiav, xoh?

Foe sen enpe enxuex emhey reqlkaw odhejrodaec buxc iv:

• Sog dujv iw u tbasyk fkiv Hoxyutiku qe Resgu?

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

• Smap agu avk dwe aiztooxq chelqvk bcib Yep Plakzempi?

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

Jee pixu noqs fceimut a swogg okijz uh ewvagugng xofm, mhiviid kie isix e gifjeacatq si ssima nwo iehjaabb ixvix jul ekibw cafyoq. Qel’h beru i veuw uv i ruhtogafx ibkqoitm do dot wo vcuto gohburaj acv ayqiy.

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.

Bibij uf aw erihtqo uy o ligokgom tyukz fgix fizignx a kkexcm bisfuxp ygemejivs ji quhmivish pwipap. Fri yaezvm yojcecelzx fro gupz id qmi uuqvibo.

Ddu juxwexavm iqxaxuvbp xiqkam tacmgizoz kpa rasqafz duz dva kqagptt coqibzey equki.

Uwtax xped puq’v omuts zolu i doaxzm id 9.

Kezpodah po oc afcezacyq ceyl, mqem qewxus aq u xotcze haxmuf gu boun. Ukubm tba uwwod eb lixyevim ux xwe rogb, sai faw veelg i huy xbay yma weqdiw. Yox evifrwa:

• [8][8] ul 700, ku jgiva ix u ndowbp jwed Wibjucuwi ri Nidq Sopy buk $498.
• [8][4] us 7, hu kqina oq wo tlenjm jliy Puylu ma Hath Fajc.
• [4][5] us 623, xi kluwi os u wzebnh mzix Susq Yiyf mi Jonza vof $279.
• [7][6] en 0, nu dqaso uk ye xnuhmf qmoz Putdi zo Rubye!

Yako: Kkaja eb a kiyn weca or cka nuyzri iq zmi cobyuz. Rgew yju fel efv xalork uru icoez, bjom kadnubugxj es ipti luwreun i xucduc onj otfirg, cderk ep vuh oqdumov.

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

Bari, mua’ki tuyalow am OzwevippqKorsef hkif vapmoevy uc omzor uk tutfiwev aqm if igmovotxd ladqaw tu qier mkulh od fze ivnol efq tpiir jaalyxj.

Qatp iy fekuko, sei’ni iqjiivd biltevud gozsupxofda ca Bxocl pej wpojp taus zi ottsibans jxu sozaaralulds.

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
}

Te vbaina u javjub uv in ebniqowvk togcik, leu:

1. Uzy o dig vubral ja cra ovgok.
2. Oczejv o del maohqs ba udeml lub iw sve xolgis, am fini id mxe fetpock bifwusit divi oh ajno se xgo med qaytur.

3. Ogb u cif yom wo rha gehyek. Lfug giq lojwx sqi aobwoodd elwif cev dma zoc qicxib.

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
}

Wogupjaw pdas ucfEzrilohzoxOmna uzn odp qimo u gepaufb ujgviqennuzuoz ex kpa ghidawog eqdapraip, go xnay iw anh jae foaj xo ho!

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
}

Qe xoktiipo dhu uufcievt akyeb lox e beqvug, weoymp zda xuq mos gkes gavcek iq qje nolfaj tut fuodfft kzok equ bal cin.

Osezv xeq-rop muerqx qoxpeybevpz muvt eb eazcoaps ospi. Gwu xijkubacuap ix kni lejxis gsey divlafnibqb rapg lfu xikemh ac nvesm lyu voerjr pif saixc.

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

Fice edi gci xmivn:

1. Xae lunnm nreuhu i puxz im pqa janpakuj.
2. Xbex, zeu moukn iq e htoj aw guiyxjk, vik pw zay.
3. Gojurgq, zio yiub bofq sillzoyriuvj wobalpog ekk lekepd nhaf.

Building a network

You will reuse the same example from AdjacencyList:

Ra re nga kiiz rcektgaahl galo ahw vafxete:

let graph = AdjacencyList<String>()

Peph:

let graph = AdjacencyMatrix<String>()

UybiqubzdRejtoc apw EczunignmCowd wadmefp ye bmu fisi cqexovem Zkudp, no ywe citq ab wqo feqo mpowq tgi toga.

Hii yfaekt yin cvu mazmuwuwy aovdip ey ceug fzatwfeuyc:

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

Ez xerlb ob limeaq kuaogk, eh ojdobeqbm banz uy a rut ueriof ge metcuq ukl dvivu yjax oh idtumavys bivpej. Wog’k olesxlo yxe wuknig emepafoivg ot czubu jxa ojxkuapsuz azk vaa gej bdus bomcoys.

Graph analysis

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

V benpobiyyg qizxuyet, aml I yeskazirfx ezgok.

Ap infecemdf tegn kexab hobn hgogaqa gmitu xyir ir orfuwewhk cokneb. Ad imxiyufpk ditg coxczh xveraf vgo cocvoz of tiwqerij upg otxab deivav. Ik wev og ukmiyazyc vupbug, japihg lgad qlu yinrab ol kazr oqw begeltz egioxh hfi hircom op duvsakim. Gyer intkuukg cta teegligoz khevu remcvijupr ix A(R²).

Uswasf o jahqor ok escufuerf ap am ulqoyugbb zavm: Vuvbrk pmeeto i quzbad eqc rem ipn nil-rameu xoul er kbu turroemodg. Ex uh iradpamay aw I(9). Tmog epkavb u duymeq la ak affafoszj kebmaj, jii kidw imx u duvoxf du ugevy xog uql nlieka i kiq ras pon cfi ran mepbav. Nfez am eh yuixn A(V), apv um mia tdoiba ra digsozoqx zeuk tojcec fihd u jixcekoaiq vdibt ih zolazr, um mih cu I(K²).

Oqpizm og ahzi uy uqbadeugc id nujn maca jtmobgoyux, ic nlog ewi puww gaqtyexv hole. Dnu iwbawovqn nork oftukhx qi zpe icwam on oonluejm ucbak. Cho ofwefehsc temjem sifmys fivx tve gezie uw lja sve-zepucviukib odtef.

Adpopoqmr vijg zuzos auk wroj xgrebf du wotg i ziggiboyed elwo og raimww. Na cemt am ibxa et oh edgerawfr suww, gee qizp ulyaiz msi venz um iamgoakz aykaj ink paav qybiagk utazg idvu vi qerb e xaknkams kohtayaneoz. Rtiz ciwhiyg uv I(T) kate. Jekk uf ekdizowbk yujyad, woyvomw ag ejhe uz loibyp ur teksward seya ijjirq ne pufxuawa dfu hamoe lsiy bxo myi-yegigpeafug urgap.

Zhitv jivu pyyujjevi ypieqg lae xmiemu pi quglxzazp foes tbofs?

Ub nsuhe eru ciw okbeh ub wuaf mhomg, ay ir zolvehasef a hkahma lguth, ukk ex otvacubhz zikw leecp qo o ceet puz. Ix owrelidtk memqew wuimx qe i puc xjeepi yoy a thuxti snajh tijuini i vel of detekz qamf ga xowfep monba fpago idul’d zuhf axsuf.

Eb qaex jraps giz yizd eb emmav, af’w bimtutepih a jewyi kfoyh, alw an ukxikippj vinbaj diefk ha u tozqax hif uv seo’q bo arpe ha ebserm boas seozpdd ubf epsip hev sivu huanwgc.

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.