Algorithms On Graphs: Difference between revisions
Jump to navigation
Jump to search
Adamcolton (talk | contribs) Created page with ";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 lo..." |
Adamcolton (talk | contribs) No edit summary |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Week 1 == | |||
=== Graph Basics === | |||
;Graph: A graph is a set of vertices and a set of edges, each of which connects two vertices. | ;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 | ;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. | ;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 / 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. | |||
: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. | |||
== 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.