Graph traversal
No description yet. This curated deck is ready for daily study.
Card preview (12)
What are the 2 components of graphs?
Nodes and Edges
Define a graph
An abstract data type used to represent complex, non linear relationships between objects
What is a neighbour?
2 nodes connected by an edge
What is the degree of a node?
The number of other nodes it’s connected too
What is a loop?
An edge that connects a node to itself
What is a path?
A sequence of nodes connected by edges
What is a cycle?
A closed path- starts and ends at the same nodes and no node is visited more than once
Examples of what a graph can represent
Social network, Transport network. the internet
What is an undirected graph?
A graph that allows you to move in either direction between nodes
How to tell if a graph is undirected?
The edges have no arrows
What is a directed grah?
The edges have directions so you can only move between nodes in specified directions
What is a weighted graph?
The edges have values used to record information