Chapter 38 - Graphs

» An abstract data structure which are representing a complex relationship » A set of vertices or nodes connected by adges or arcs

» It is essentially the ‘cost’ of movement around the graph

» Consists of nodes » All edges are bidirectional - meaning they can go any direction

» Represents a path/link between 2 nodes

» Another name for an edge

» Each data item within a graph

» Another name for a vertex

» Edges that have some value, attached to them » Shows the cost of traversing

» Shows direction - can be bidirectional » Consists of nodes

» Adjacency matrix » Adjacency list

» A node

» Row then column

» A table showing which nodes in a graph are connected and if the edges are weighted » Elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph

» Symmetric

» May be represented with 1s instead of weights

» Instead of 1s, there can be the value of the weight

» Very convenient to work with » Adding edges is very simple

» A sparse graph with not many connections will leave most of the cells empty, therefore wasting space » Using a static 2D array for it, it is harder to add or delete nodes

» A collection of unordered lists used to represent a finite graph » Each list describes the set of neighbours of a vertex in a graph

» A list of all the nodes are created » Each node points to a list where all the adjacent nodes to which is directly linked

» When it is weighted, with each key in the dictionary being the node and the value, the edge weight

» Good way of representing a sparsely connected graph » More memory efficient

» In the adjacency list, you need to list all the nodes that the node is connected to, in order to find the other node of the edge required. » Not time efficient

» An algorithm used by Google search to rank website in their search engine results