Graph
Summary
- BFS for finding the unweighted shortest path.
- Dijkstra’s algorithm for weighted shortest path.
- DFS for graph exploration.
- Topological sort for ordering tasks.
- Strongly connected components for simplifying a graph.
- Minimum weight spanning trees for broadcasting messages.
vocalubary
- vertex
"node", can have information like "key"..
- edge
connectes 2 vertices. May be one-way or two-way.
If all edges in a graph are one-way, we say it's directed graph or digraph.
- weight
edges may be weighted to show that there is a cost to go from one vertex to another
path
cycle
A graph with no cycles is called an acyclic graph.
A directed graph with no cycles is called a directed acyclic graph or DAG.
Implementation
- adjacency matrix
- adjacency list
adjacency matrix
pros
- simple
- for small graphs it's easy to see connection
cons
- most of cells are empty that we say the matrix is "sparse"
It's a good implementation for a graph when the number of edges is large.
adjacency list
space-efficient
Graph object, each vertex object in the graph maintains a list of other vertices that it is connected to.
In our implementation of vertex class we use a dictionary, keys are vertices
and the values are weights.
