Graphs and trees Flashcards Preview

Computing > Graphs and trees > Flashcards

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

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