Graph

Definition

• a mathematical non-linear data structure
• capable of representing many kinds of physical structures
• A graph G(V,E) is defined as a set of vertices (V) and a set of edges(E)
  - Vertices : collection of nodes, represented as points or circles
  • Edges: connect a pair of vertices and can have weights attached

Adjacency Matrix Representation

1. Create a Matrix(e.g. use a 2-dimensional array)
2. Any index i represents a node
3. Any entry (i, j) in the matrix represents connectivity between two nodes i, j
1. entry (i, j) = 1 => an edge exists
2. entry (i, j) = 0 => no edge exists

Adjacency List Representation

1. Create an array of Lists (e.g. use a linked-list)
2. The headers of the lists represents the nodes
3. Every list represents the nodes, connected from the header node

Adjacency Matrix for Directed Graph

Adjacency List for Directed Graph

Breadth-First Search (BFS Traversal)

• Start from the starting node (this will be given to you)
• Generate a traversal tree while traversing the graph
• A node is traversed when its all successor nodes are generated
• use queue
  

  

• Traversed List : PQRSTVUWX

Depth-First Search (DFS Traversal)

• Same as with tree traversal using DFS
• Use a stack
• use Boolean visited arrary

Five components of Greedy Algorithms

• candidate set : From which a solution is created
• selection function : chooses the best candidate to be added to the solution
• Feasibility function : Determines if a candidate can be used to contribute to a solution
• Objective function : Assigns a value to a solution, or a partial solution
• Solution function : indicates when we have discovered a complete solution

Shortest path algorithms : Major components

Initialize-Single-Source (G, s)
for each vertex v ε G
	v.dist ← ∞
	v.π ← NULL
	s.dist ← 0

Relax (u, v, w)
if v.dist > (u.dist + w(u, v))
	v.dist ← u.dist + w(u, v)
	v.π ← u

Dijkstra's Algorithm

1. Set 1: S = ∅
2. Set 2: Q = V[G]
3. While Q != ∅
  u = extractMin(Q)
  S = S U {u}
	for each 𝑣 ∈ 𝐴𝑑𝑗 𝑢 & Not in Q 
    if (d[v] > d[u] + w)
	d[v] = d[u] + w 
    Parent[v] = u

Spanning Tree

• sub-graph that connects all the vertices together using the minimum number of edges required
• There should be no cycles
• for n number of vertices, (n-1) edges are needed

Minimum Spanning Tree(MST)

• cost of any spanning tree : add weights of all the edges
• MST : a tree with minimum weights is MST
• Time complexity : Exponential

Prim's Algorithm : at a glance

• two sets
• MST set: vertices that are included in the spanning tree
• set2 : vertices that are not yet included in the spanning tree

1. Create an array of size V and initialize it with NIL
2. Create a Priority Queue(min Heap) of size V. Let the min Heap be Q
3. Inser all vertices into Q. Assign cost of starting vertex to 0 and the costs of other vertices to infinite.

MST-PRIM(G, w, source)
for each u Є V [G] do // for all vertices 
	cost[u] ← ∞
	π[u] ← NULL
cost[source]<;-0
Q←V[G]//set2
while Q ≠ Ø do
	u ← EXTRACT-MIN(Q) 
    for each v Є Adj[u] do
		if v Є Q and w(u, v) < cost[v] 
        	π[v] ← u
			cost[v] ← w(u, v)

application

• reducing copper to connect multiple nodes in a electrical/electronic circuit
• minimizing network length (cable cost) to connect multiple routers/computers etc.