1. Introduction• A graph is a set of values that are related in a pairwise fashion.• Graphs have many applications where one would want to model real life (e.g. real world relationships or the internet or how roads are connected to each other).• In graphs, each item is called a node (or a vertex), and nodes are connected with edges. • Facebook uses it for social network, Amazon uses it for recommendation engine, Google Maps uses it for determining the shortest path to where you want to go.• Graphs encompass trees and linked lists (trees encompass linked list).• Graphs are great for capturing relationships.• Because graphs can get complicated, they're much harder to scale.2. Types of Graphs• Directed/Undirected (ex. Twitter)– Directed graphs are useful for describing traffic flow of some kind of system in which movement is not bidirectional.– Ex. of Directed: Twitter, Ex. of Undirected: Facebook• Weighted/Unweighted– With graphs you can also have information on the edges.– Ex. Google Maps• Cyclic/Acyclic– Cyclic graphs are very common in weighted graphs such as Google Maps (most of the time there's a way to get back).– Note: Only having one cycle in the graph would make it cyclic.• Map of internet as a huge graph.3. Graph Implementation• There are two common ways to capture which nodes are connected to each other:– Adjacency list* Memory efficient in case of sparse relationship (e.g. Facebook)* Lookup is slow.– Adjacency matrix* Lookup is fast.* It can capture edge weights more easily.*