Algorithms On Graphs: Difference between revisions
Jump to navigation
Jump to search
Adamcolton (talk | contribs) No edit summary |
Adamcolton (talk | contribs) No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 23: | Line 23: | ||
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. | 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. | ||
== Week 2 | == Week 2 == | ||
=== Directed Graphs === | === Directed Graphs === | ||
| Line 32: | Line 32: | ||
;Source: Vertex with to incoming links | ;Source: Vertex with to incoming links | ||
;Sink: Vertex with no outgoing links | ;Sink: Vertex with no outgoing links | ||
== Week 3 == | |||
=== Distances === | |||
;BFS: Breadth first search | |||
This is how to find distance. You can also build a minimum-spanning tree this way. | |||
== Week 4 == | |||
=== Fastest path === | |||
[[Category:Notes]] | [[Category:Notes]] | ||
[[Category:Course Work]] | [[Category:Course Work]] | ||
Latest revision as of 14:26, 10 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.
Week 2
Directed Graphs
- DAG
- directed acyclic graph.
Any DAG can be linearly ordered.
- Source
- Vertex with to incoming links
- Sink
- Vertex with no outgoing links
Week 3
Distances
- BFS
- Breadth first search
This is how to find distance. You can also build a minimum-spanning tree this way.