Fichas
Week 3: Data Structures & Decomposition
Fichas del conjunto (9)
- 1Storing data- Clarity, simplicity, easy to access, easy to modify
- E.g. tables, lists, graphs - 2Graphs- Abstraction of relational data
- Useful for representing relationships between things
- Made up of vertices (things) and edges (relationships) - 3Directed graph- For ordered relations
- Edge relation is asymmetric i.e. v can be reachable from w but not the other way around
- Path - a sequence of edges which join a set of unique vertices - 4Simple graphs, cycles and connectivity- Simple graph - no loops or parallel edges
- Cycle - path (non-self-intersecting) with same start and end vertex
- Connected graph - every vertex can be reached from every other vertex - 5Representation of graphs in Python1. Adjacency matrix - table with one column and one row per vertex; each cell represents existence of edge (1 or 0)
2. Adjacency list - list of lists, with one inner list per vertex containing its neighbours
3. Edge list - list of list/tuple pairs holding the source and destination vertices for each edge - 6Simple treeT = (V, E) is connected and has no cycles
Properties:
1. Minimally connected (removing any edge renders disconnected)
2. Unique path between any 2 vertices - 7Spanning tree of a graph- Assume G = (V, E) is a simple and connected graph
- Spanning tree of G is a subgraph T = (V, F) of G that:
1. Contains all vertices of G
2. Is a tree (connected and cycle-free) - 8Prim's algorithm with decomposition
- 9Decomposition- Breaking down programs/problems into sub-programs/problems
- Leads to re-usable components
- Main tool for decomposition = functions
Información
- Descripción
- (FIT1045: Algorithms & Programming Fundamentals in Python) Computer Science Fichas sobre Week 3: Data Structures & Decomposition, creado por Melina Mackey el 02/09/2019.
- Creado por
- Melina Mackey
- Visitas
- 0
- Historial
-
- Creado por Melina Mackey · 2 sep 2019
- Copiado por Melina Mackey · 2 sep 2019
- Valoración