4.2.4 - FoDS (Graphs) Flashcards
When are graphs used
To represent more complex relationships than stacks and queues
What are the typical uses of graphs
- Social Networking
- Data Transmission
- Navigation systems
Is a graph dynamic or static and why
Dynamic as its size can be modified
What is a graph
A set of vertices and edges
What is a vertex
A point on a graph where edges intersect
What is an edge
A line on a graph that connects a pair of edges
What are synonyms for vertices and edges
Nodes and arcs
What is a sparse graph
A graph that has more vertices than edges
What is a dense graph
A graph with more edges than vertices
What is a weighted graph
A network with a cost to traverse from one vertex to another
What is a directional graph
A graph that restricts traversal to one direction
What are the two ways that graphs can be represented
- Adjacency matrices
- Adjacency lists
What are the advantages of matrices
- Time efficient as they are easy to directly locate connections between vertices
- Adding new edges is easy
What are the advantages of lists
- They are memory efficient as they don’t include connections between unconnected vertices
When would you use a list instead of a matrix and vice versa
List - sparse graphs
Matrix - dense graphs
What is the disadvantage of lists
- There are time inefficient as you have to iterate through the list to find an edge between vertices
When are the disadvantages of lists negligible
When there is no checking for presence of edges meaning that there will be no iteration
What is the disadvantage of matrices
- Using it to store a sparse graph will waste memory as there will be a lot of unconnected vertices
- If a 2D array is used to store, it can be hard to add and remove nodes
