A graph is a representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices (also called nodes or points), and the links that connect some pairs of vertices are called edges (also called arcs or lines).[1] Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.
-
Skiena Lectures - great intro:
- CSE373 2012 - Lecture 11 - Graph Data Structures (video)
- CSE373 2012 - Lecture 12 - Breadth-First Search (video)
- CSE373 2012 - Lecture 13 - Graph Algorithms (video)
- CSE373 2012 - Lecture 14 - Graph Algorithms (con't) (video)
- CSE373 2012 - Lecture 15 - Graph Algorithms (con't 2) (video)
- CSE373 2012 - Lecture 16 - Graph Algorithms (con't 3) (video)
-
Graphs (review and more):
- 6.006 Single-Source Shortest Paths Problem (video)
- 6.006 Dijkstra (video)
- 6.006 Bellman-Ford (video)
- 6.006 Speeding Up Dijkstra (video)
- Aduni: Graph Algorithms I - Topological Sorting, Minimum Spanning Trees, Prim's Algorithm - Lecture 6 (video)
- Aduni: Graph Algorithms II - DFS, BFS, Kruskal's Algorithm, Union Find Data Structure - Lecture 7 (video)
- Aduni: Graph Algorithms III: Shortest Path - Lecture 8 (video)
- Aduni: Graph Alg. IV: Intro to geometric algorithms - Lecture 9 (video)
- CS 61B 2014 (starting at 58:09) (video)
- CS 61B 2014: Weighted graphs (video)
- Greedy Algorithms: Minimum Spanning Tree (video)
- Strongly Connected Components Kosaraju's Algorithm Graph Algorithm (video)
-
Full Coursera Course:
-
Yegge: If you get a chance, try to study up on fancier algorithms:
- Dijkstra's algorithm - see above - 6.006
- A*
#Tree (Graph Theory)
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree. A forest is a disjoint union of trees.