Algorithms On Graphs: Difference between revisions
Jump to navigation
Jump to search
Adamcolton (talk | contribs) No edit summary |
Adamcolton (talk | contribs) No edit summary |
||
| Line 10: | Line 10: | ||
;Density: Edges / vertices<sup>2</sup> | ;Density: Edges / vertices<sup>2</sup> | ||
=== Exploring Graphs === | |||
Finding routes, ensuring connectivity, solving mazes. | |||
;Path: A sequence of vertices such that each vertex is connected to the next by an edge. | |||
Goes through algorithm to find all connected nodes. | |||
:DFS: Depth first search. | |||
[[Category:Notes]] | [[Category:Notes]] | ||
[[Category:Course Work]] | [[Category:Course Work]] | ||
Revision as of 03:14, 8 June 2016
Week 1
Graph Basics
- Graph
- A graph is a set of vertices and a set of edges, each of which connects two vertices.
- Loop
- An edge that connects a vertex to itself
- Simple Graph
- A graph with no loops and no more than one connection between any set of vertices.
Representing Graphs
We can store a graph as a list of edges. It can also be stored as a matrix. Or a list of lists, the top list being all the vertices and each sub list being the vertices it's connected to.
- Density
- Edges / vertices2
Exploring Graphs
Finding routes, ensuring connectivity, solving mazes.
- Path
- A sequence of vertices such that each vertex is connected to the next by an edge.
Goes through algorithm to find all connected nodes.
- DFS: Depth first search.