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 19: | Line 19: | ||
:DFS: Depth first search. | :DFS: Depth first search. | ||
:Component; A set of connected vertices within a graph, the islands. | |||
We can mark each vertex with a number when we arrive and a number when we leave. So a parent with one child is 1/4 and the child is 2/3. This gives us useful data about the order and structure of the spanning tree. | |||
[[Category:Notes]] | [[Category:Notes]] | ||
[[Category:Course Work]] | [[Category:Course Work]] | ||
Revision as of 12:28, 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.
- Component; A set of connected vertices within a graph, the islands.
We can mark each vertex with a number when we arrive and a number when we leave. So a parent with one child is 1/4 and the child is 2/3. This gives us useful data about the order and structure of the spanning tree.