Flashcards
Week 3: Data Structures & Decomposition
Cards in this deck (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
Information
- Description
- Computer Science (FIT1045: Algorithms & Programming Fundamentals in Python) Flashcards on Week 3: Data Structures & Decomposition, created by Melina Mackey on 02/09/2019.
- Created by
- Melina Mackey
- Views
- 0
- History
-
- Created by Melina Mackey · Sep 2, 2019
- Copied by Melina Mackey · Sep 2, 2019
- Rating