YEAR 2 WEEK 9 GRAPHS Flashcards
What are graphs?
Graphs are for modelling connections and relationships between data items
What are connected items or nodes called?
They are called vertex (plural:vertices)
What are the lines that connect vertices?
This is called edge.
-Each vertex has a degree which describes how many connections that vertex has.
What is a cycle?
A vertex connecting to itself to form a cycle / loop
- a path where the first and last nodes are the same
Why do we use graphs?
They are used to visualise a problem in this way they benefit humans by presenting info about a complex situation in a way that is simpler to under stand
They can be used for;
-Network connections-as used in a router whose paths change by the second
-Social connections-Define friends on social media platforms
etc
-GPS- to decide the most effective journey
What is an Undirected graph?
This is the most simplest kind of graphs where edges have no particular direction or flow associated with them
There is no format for how the nodes are set out.
What is a Labelled or weighted Graph?
In weighted graphs, movement from one vertex to another has a cost (labelled as a number) This type of graph is used along side programs written to maximise efficiency.
What are directed Graphs?
Movement between vertices is restricted and we have to follows the arrows which will be edge which show the flow of the Graph indicating where you can or cant go.
What is Breadth first Graph traversal?
-Designated one vertex as the root
-Visit each vertex connected to the root
-Once all directly connected vertices are visited,visit vertexes one step farther away
How do we do Breadth first Traversal (for Graphs) using queues?
-Place the first vertex into the queue,
-Mark it as explored (eg change its colour)
-Repeat
-Visit every vertex it is connected to.
-Add each vertex to the queue
Until all its vertices have been visited
-Repeat
-Pop front vertex from queue
-Mark the new front vertex as explored
-Repeat
-Visit every vertex the new front vertex is connected to
-Add each vertex to the queue
-Until every vertex has been visited
-Until queue is empty
What is Depth first Graph traversal?
POST ORDER
Picks one path and follows it to the end
Then backtracks and flows the next path to the end and then will continue until or vertices have been visited.
How do we do Depth first Traversal (for Graphs) using Stacks?
-Repeat
-PUSH the vertex onto the stack ,Mark the vertex as explored
-PUSH a child vertex onto the stack
-IF there is no child vertex
-POP vertex off the stack
-UNTIL the stack is empty
