4.2.4 Graphs Flashcards
(13 cards)
Define Graphs.
An abstract data structure consisting of a set of values/nodes connected by a set of edges.
Define Abstraction.
The removal of unnecessary detail, reducing the problem to essential features.
What is the vertex/node in graph?
The representation of an object on a graph that is capable of being related to other such objects.
What is the edge in graph?
A connection that represents a relationship between two nodes.
What are the 4 types of graphs?
- weighted
- unweighted
- directed
- undirected
What is a weighted graph?
A graph where each edge/arc has an associated value (weight).
What is an unweighted graph?
A graph where edges have no values.
What is a directed graph?
A graph where the order of the vertices paired in an edge matter. The edges are one way.
What is an undirected graph?
A graph where the order of the vertices paired in an edge does not matter. The edges are bidirectional.
What are some examples of graphs in real life?
- human networks
- transport networks
- internet and the web
- computer science
- medical research
- project management
- game theory
What is an Adjacency List?
A representation of a graph by storing a list of connected nodes to each node.
What is an Adjacency Matrix?
A matrix representation of a graph that stores the edges connecting all possible nodes.
Where 1 is connected, and 0 is not connected.
Adjacency List VS Adjacency Matrix
List:
- suitable for sparse graphs (little edges)
- less memory required (as only stores data when there is an edge)
- increases processing time (has to be analyzed before adjacencies can be identified)
Matrix:
- suitable for dense graphs (lots of edges)
- more memory required (as stores value for every combination)
- faster processing time (adjacencies can be identified more quickly, matrix is used as a lookup)
