Flashcards in Graphs and trees Deck (12):
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
-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
-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