Graphs Flashcards
(42 cards)
Directed Edges
An edge (u,v) is from u to v, not v to u
Undirected Edges
An edge (u,v) is from u to v AND from v to u
Weighted Edges
Each edge has a “weight” (“cost”) associated with it (i.e. magnitude associated with relationship)
Unweighted Edges
Edges do not have weights
Cycle
A valid path starting and ending at the same node
Class: Unstructured
A disconnected collection of nodes
Class: Sequential
An ordered collection of connected nodes (i.e. Linked List)
Class: Hierarchical
A ranked collection of connected nodes
Class: Structured
A collection of both connected and disconnected nodes
Multigraph
A given pair of nodes may have multiple distinct edges (i.e. cites and flights, different prices between same cities)
Adjacency Matrix
O(|V|^2) Good for dense graphs. Not good for sparse graph. Must iterate through all indices Access constant time for searching.
From is rows, To is columns.
For undirected graph, it will be symmetric matrix.
Diagonals will be self directed path.
Adjacency List
Hash tables or has maps, or linked list. Has very fast look up and saves space without reference null connections unlike matrix. O(|V| + |E|)
Breadth First Search (BFS) Algorithm
- Add (0, start) to queue
- While the queue is not empty:
a. pop (d, curr) from the queue
b. if curr has not been visited:- mark curr as visited with distance d
- for all edges (curr, w):
if w has not been visited add (d+1, w) to queue
Depth First Search (DFS) Algorithm
- Add start to stack
- While the stack is not empty:
a. pop curr from stack
b. if curr has not been visited- mark curr as visited
- for all edges (curr, w):
- if w has not been visited, add w to stack
Dijkstra’s Algorithm
1. know prerequisite condition)
2. valid by proof by contradiction. No future path will be less than the current path using algorithms
3. keep track of the shortest path coming from
4.
Fundamentally the same as BFS (Queue and DFS (stack), but Dijkstra’s is a (min) heap where lowest distance is highest priority
Set all nodes to infinite distance. 1. add (0,start-inital node/source) to PQ/heap. Set others to -1 or infinity 2. while PQ !=empty: - A. Pop the (d,curr) from PQ - B. if curr is not done: - 1. mark curr as done - 2. (curr, w, e): only works for graphs with positive edge weights. No negative weights
Dijkstra’s Algorithm Time Complexity
Overall: O(|V| + |E| log |E|) P. Initialization of infinity = O(|V|) 1. Add (0,Start) to PQ = O(1) 2. while PQ not empty: A. Pop (d, curr) from PQ = O(log |E|) , since using a heap (perfectly balanced) number of pops is log of the number of edges
BFS Search Algorithm (Min-Path)
Debashis (11/25)
P. Initialize all nodes (other than source) with infinity distance and previous=-1
- Point CURR to source. Add CURR to PQ. Then enter while loop of (while PQ not empty).
- Pop from PQ (min heap). Start with (source) node and add to PQ all neighboring nodes (technically edges). If distance is infinity update neighbors with distance between +1. Once all neighbors pushed to PQ, then exit.
- Pop queue and update dist of curr to 2, prev to prev node, pop queue and update distance to 2 and prev prev node
For directed and connected graph what is expected
Each node is only enqueued once
At any time the queue holds at most 2 distinct DISTANCE VALUE from all nodes in it.
It can work for a graph with a cycle
Dijsktra’s Algorithm Properties
Properties (using PQ holding pairs (pointer to vertex, path cost ) )
Path Cost is the priority (low is higher priority)
The PAIR is maintaining a path cost to vertex.
Multiple pairs with the same “pointer-to-vertex” part can exist in the priority queue at the same time. These will usually differ in the “path cost”
Dijkstra’s Algorithm: Data Structures
no negative vertex weight
Maintain a sequence (array, vector, etc) of vertex objects, indexed by vertex number
- vertex objects contain 3 fields (and others):
1. Dist: cost of teh best (least cost) path discovered so far from start vertex to “this” (curr) vertex
2. Prev: the vertex number (index) of the rpevious node to the best path
3. Done: a boolean indicating whether the Dist and Prev fields contain the final best values for this vertex
Disjoint Sets is ADT or DS
Abstract Data Type
ADT optimized for Union and Find
Union: Given two elements, merge the sets to which they belong
Find: Given an element e, return the set to which it belongs
Purpose of union operation
Join two sets. Once two sets have been unioned , they should have the same sentinel node. (there are a lot of freedom around the concept of union, since there is many ways to merge two sets of vertices.)
Union by size
Union by weight
Queue
Array List Enqueue O(1)/O(n) O(1) Dequeue O(1) O(1) Peek O(1) O(1)
Disjoint Set is an ADT
Commonly referred to as Union-Find data type
Interface supports:
Union: given two elements u and v, merge the sets to which they belong
Find: Given an element e, return the set to which it belongs.
Efficiently implemented using Up-Tree DATA STRUCTURE. Simply a graph which all nodes have. ainge “parent” pointer. Those that do not have a parent pointer are the SENTINEL NODES. Sentinel Nodes represent a single set.
