Fichas
Graphs | Data Structures - OCR Computer Science A Level
Fichas del conjunto (11)
- 1What are Graphs?> Form of abstract data structure (in the data structure topic‽ wow!)
> Used to represent complex relationships
> Set of vertices or nodes connected by edges or arcs - 2What is the Difference between Directed and Undirected Graphs?> Directed graphs (digraphs) have at least one one-way edge
> Undirected graphs all have two-way edges - 3What is the Difference between Weighted and Unweighted Graphs?> Weighted graphs show a sort of cost from one vertex to another - e.g.: a distance
> Unweighted graphs do not show this - 4What is the Adjacency Matrix?> Two dimensional array used to implement and represent a graph
> Rows and columns represent nodes
> Values in cells represents connecting edges
> Undirected graphs have symmetrical adjacency matrices - 5What is the Adjacency List?> List used to implement and represent a graph
> Each node points to a list of adjacent nodes
> If weighted, is implemented using a list of dictionaries, with the key being the node, and the value being the weight: {node : weight}
> If unweighted, an array is used to represent all adjacent nodes - 6What are the Advantages and Disadvantages of the Adjacency Matrix?> Convenient to work with and simple to understand
> Sparse graphs leave most elements empty
> The 2D array is static: it cannot grow or shrink, so the graph is limited to the size defined at the beginning of the program - 7What are the Advantages and Disadvantages of the Adjacency List?> More space efficient than adjacency matrix - no empty spaces
> Can be dynamic (i.e.: not use an array), allowing the graph to grow or shrink while the program is running
> Less convenient to work with and therefore harder to understand
> If dynamic, could potentially cause under / overflow errors - 8What are the 2 ways of Traversing a Graph?1. Depth-first
2. Breadth-first - 9What is Depth-First Traversal in Graphs?> Type of traversal that goes as far down one route as possible before backtracking
> Changes route at each intersection
> Follows the graph alphabetically / numerically
> Begins at the first letter / number
> Finishes once all nodes have been visited - 10What is Breadth-First Traversal in Graphs?> Type of traversal that visits all neighbouring nodes
> Visits the first visited node after all neighbouring nodes, then repeats the process
> Follows the graph alphabetically / numerically
> Begins at the first letter / number
> Finishes once all nodes have been visited - 11What are some Examples of Graphs being Used?> Computer networks - nodes being computers, weighted edges being the bandwidth
> Roads between towns, with weighted edges representing distance, journey time, fares etc.
> Tasks in a project, some of which have to be completed before others
> Webpages and links
Información
- Descripción
- A level (Data Structures) Computer Science Fichas sobre Graphs | Data Structures - OCR Computer Science A Level, creado por Malachy Moran-Tun el 11/10/2021.
- Creado por
- Malachy Moran-Tun
- Visitas
- 5
- Historial
-
- Creado por Malachy Moran-Tun · 6 oct 2021
- Copiado por Malachy Moran-Tun · 11 oct 2021
- Valoración