data structures 2 Flashcards
graph
set of vertices or nodes connected by weighted or unweighted edges or arcs which are one or two way
undirected graph
set of vertices or nodes connected by weighted/unweighted edges or arcs which are bidirectional
directed/ digraph
set of vertices or nodes connected by weighted/unweighted edges or arcs which are all one way
weighted edges
there is a cost to go from one to another node eg distance
computer needs to represent connections and weighting in a ___ representation
structured and numerical
ways of implementing a graph
adjacency matrix and adjacency list
adjacency matrix
uses a 2D array, each row/column represents a node. A value in the intersection of (i,j) indicates edge connecting node i and node j.
Value stored in the cell is the weighting. If graph is unweighted then a 1 is stored in the cell.
Undirected graphs are symmetric and v.v
adv/disadv adjacency matrix
ADV: convenient, easy to add an edge
DISADV: if many nodes but sparse graph with few edges means most cells are empty: larger the graph the more memory wasted
if using a static 2D array, it is harder to add or delete nodes
adjacency list
a list of all the nodes is created, with all the nodes pointing to a list of all adjacent nodes (adjacency lists) to which it is directly linked. If weighted, adjacency list can be implemented as a dictionary: key= node being linked to, value= edge weight. If unweighted, dictionary data structure not necessary
adv adjacency list
uses much less memory to represent a sparsely connected graph: space efficient
depth first traversal
go as far down one route as possible before backtracking and taking next route
breadth first search/traversal
visit all the neighbours of a node then all the neighbours of the nodes just visited, before moving further away from the start node
applications of graphs
- computer networks: node representing computers and weighted edges representing bandwidth between them
- web pages and links eg Google PageRank
- roads eg nodes: towns edges: distance, fare, time
- states in a finite state machine
- tasks in a project where some have to be completed before others
tree
non linear data structure for storing hierarchical data, made of a number of nodes and outgoing edges
uses of trees
storing hierarchical data eg game moves/folder structure
to make info easy to search
manipulating sorted lists of data