Graphs and trees Flashcards
Define an undirected graph
A graph where the relationship between vertices is two way
Define a directed graph
A graph where the relationship between vertices i one way
What are the important parts of graphs and trees?
Vertex/vertices - an object in a graph (also know as a node)
Arc - the join/relationship between two nodes
What is the difference between a weighted and an unweighted graph?
A weighted graph has values between/for the node.
An unweighted graph has no values for each arc.
List some uses for graphs
Human networks - Each node is a person and each arc is the relationship between them
Transport networks - All locations on the networks are nodes on the graph and the arcs the routes between them
Define adjacency list
A data structure that stores a list of nodes with their adjacent nodes
Define adjacency matrix
A data structure set up as a two dimensional array or grid that shows whether there is an edge between each pair of nodes
Adjacency list VS adjacency matrix
Adjacency list;
-Only stores data where there is an edge. less storage space
-It has to be tested every time to see if two nodes connect. Increases processing time
Adjacency matrix;
-Stores values for every combination. Takes up a lot of space
-Adjacencies can be identified more quickly
Define tree in relation to computing
a data structure similar to a graph but with no loops
What are the parts of a tree in relation to computing?
Node - An object on the graph
Edge - A join or relationship between two nodes
Root - The starting node from which the whole data structure stems off
Parent - A type of node on the tree with further nodes below it
Child - A node on the tree that has more node above it
Leaf - A node that doesn’t have any node beneath it
What is a binary search tree?
A type of tree where each parent node can only have two children
How would you store a binary search tree in a three dimensional array?
The first layer would store the data in the node.
The second layer would store the left connecting node.
The third layer would store the right connecting node
