graphs
2.7. graphs#
Some notes on computer science graphs.
Edges are of the form (v1, v2)
Can be ordered pair or unordered pair
Definitions
A weight or cost can be associated with each edge - this is determined by the application
w is adjacent to v iff (v, w) \(\in\) E
path: sequence of vertices w1, w2, w3, âŚ, wn such that (wi, wi+1) â E for 1 ⤠i < n
length of a path: number of edges in the path
simple path: all vertices are distinct
cycle:
directed graph: path of length \(\geq\) 1 such that w1 = wn
undirected graph: same, except all edges are distinct
connected: there is a path from every vertex to every other vertex
loop: (v, v) \(\in\) E
complete graph: there is an edge between every pair of vertices
digraph
directed acyclic graph: no cycles; often called a âDAGâ
strongly connected: there is a path from every vertex to every other vertex
weakly connected: the underlying undirected graph is connected
For Google Maps, an adjacency matrix would be infeasible - almost all zeros (sparse)
an adjacency list would work much better
an adjacency matrix would work for airline routes
detect cycle
dfs from every vertex and keep track of visited, if repeat then cycle
Topological Sort
Given a directed acyclic graph, construct an ordering of the vertices such that if there is a path from vi to vj, then vj appears after vi in the ordering
The result is a linear list of vertices
indegree of v: number of edges (u, v) â meaning the number of incoming edges
Algorithm
start with something of indegree 0
take it out, and take out the edges that start from it
keep doing this as we take out more and more edges
can have multiple possible topological sorts
Shortest Path
single-source - start somewhere, get shortest path to everywhere
unweighted shortest path - breadth first search
Weighted Shortest Path
We assume no negative weight edges
Djikstraâs algorithm: uses similar ideas as the unweighted case
Greedy algorithms: do what seems to be best at every decision point
Djikstra: v^2
Initialize each vertexâs distance as infinity
Start at a given vertex s
Update sâs distance to be 0
Repeat
Pick the next unknown vertex with the shortest distance to be the next v
If no more vertices are unknown, terminate loop
Mark v as known
For each edge from v to adjacent unknown vertices w
If the total distance to w is less than the current distance to w
Update wâs distance and the path to w
It picks the unvisited vertex with the lowest-distance, calculates the distance through it to each unvisited neighbor, and updates the neighborâs distance if smaller. Mark visited (set to red) when done with neighbors.
Shortest path from a start node to a finish node
We can just run Djikstra until we get to the finish node
Have different kinds of nodes
Assume you are starting on a âside roadâ
Transition to a âmain roadâ
Transition to a âhighwayâ
Get as close as you can to your destination via the highway system
Transition to a âmain roadâ, and get as close as you can to your destination
Transition to a âside roadâ, and go to your destination
Traveling Salesman
Given a number of cities and the costs of traveling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?
Hamiltonian path: a path in a connected graph that visits each vertex exactly once
Hamiltonian cycle: a Hamiltonian path that ends where it started
The traveling salesperson problem is thus to find the least weight Hamiltonian path (cycle) in a connected, weighted graph
Minimum Spanning Tree
Want fully connected
Want to minimize number of links used
We wonât have cycles
Any solution is a tree
Slow algorithm: Construct a spanning tree:
Start with the graph
Remove an edge from each cycle
What remains has the same set of vertices but is a tree
Spanning Trees
Minimal-weight spanning tree: spanning tree with the minimal total weight
Generic Minimum Spanning Tree Algorithm
KnownVertices <- {}
while KnownVertices does not form a spanning tree, loop:
find edge (u,v) that is âsafeâ for KnownVertices
KnownVertices <- KnownVertices U {(u,v)}
end loop
Primâs algorithm
Idea: Grow a tree by adding an edge to the âknownâ vertices from the âunknownâ vertices. Pick the edge with the smallest weight.
Pick one node as the root,
Incrementally add edges that connect a ânewâ vertex to the tree.
Pick the edge (u,v) where:
u is in the tree, v is not, AND
where the edge weight is the smallest of all edges (where u is in the tree and v is not)
Running time: Same as Dijkstraâs: Î(e log v)
Kruskalâs algorithm
Idea: Grow a forest out of edges that do not create a cycle. Pick an edge with the smallest weight.
When optimized, it has the same running time as Primâs and Dijkstraâs: Î(e log v)
unoptomized: v^2