ch 9 graph algorithms Flashcards
directed
if pair of vertices is ordered, edge has a direction
DAG
directed acyclic graph, no cycles
connected
every vertice is directly connected to each other
strongly connected
directed graph with every vertice connected to each other
weakly connected
no direction
complete graph
edge between every vertice
adjacency matrix vs adjacency graph
adjacency matrix when graph is dense each edge (u,v) set A[u] [v] to true
sparse: adjacency list
for each vertex, keep a list of adjacent vertices
memory requirement is larger
topological sort
ordering of vertices in a directed acyclic graph, such that if there is a path from vi to vj, then vj appears after vi in the ordering
not possible if there is a cycle
decrease indegree every time you traverse the vertex within a vertex’s adjacency list
negative cost cycle
cannot be found when present
running time of unweighted shortest path problem
O(E +V)
running time of weighted shortest path problem
O(E log v)
breadth first search
processing vertices in layers
vertices closest to the start are evaluated first , most distant vertices are calculated last
minimum spanning tree
tree because a cyclic
spanning because it covers every vertex
prims algorithm
essentially dijkstras start with a node see which adjacent node has the shortest path mark that as known now see which has the shortest path mark them as known etc good example in the book runs on undirected graphs runtime V^2 without heaps, or ElogV with heaps
kruskals
selected edges in order of the smallest weight and accept an edge if it does not cause a cycle
if u and v are in the same set, they are rejected
for example, you have u v w in a triangle
join u and v, they are in a set
join v and w they are in a set
when you see w and v, they are both already in the same set
on paper
see which weights are the smallest
create an edge between them if it doesnt create a cycle
good example on page 398
