CSE 331 Lecture Notes - Lecture 8: Dense Graph, Interdata, Pure Data
Inter-Data Relationships
• Arrays:
o Categorically associated
o Sometimes ordered
o Typically independent
o Elements only store pure data, no connection info
• Trees
o Directional relationships
o Ordered for easy access
o Limited connections
o Elements store data and connection info
• Graphs
o Multiple relationship connections
o Relationships dictate structure
o Connection freedom
o Both elements and connections can store data
Graph
• A graph is defined by a pair of sets G = (V,E) where V is a set of vertices (or nodes) and
E is a set of edges
o Edge is connection between nodes
• Undirected graph: edges have no direction and are two-way
• Directed graph: edges have direction and are thus one-way. There would be arrows
indicating which direction
• Degree: the degree of a vertex is the number of edges containing that vertex
o In degree: number of edges pointing to a vertex
o Out degree: number of edges pointing out of vertex
• Self loop: an edge that starts and end at the same vertex
• Parallel edges: two edges with same start and end vertices (only for direct graphs)
• Simple graph: a graph with no self loop and no parallel edges
• A graph can have a degree of 0 (no edges)
• Dense graph: a graph with a lot of edges (if number of edges is within set of V2)
• Sparse graph: a graph with few edges (if number of edges iss within set of just V)
o Usually, graphs are sparse rather than dense
