33857633
Description
Flashcards by Malachy Moran-Tun, updated more than 1 year ago
More
| Question | Answer |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| What are the 2 ways of Traversing a Graph? | 1. Depth-first 2. Breadth-first |
| What 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 |
| What 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 |
| What 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 |
Want to create your own Flashcards for free with GoConqr? Learn more.