[Lecture Summary] 08 Algorithm and Data Structure : Graph

This contents is based on Lecture of link

Overview for Graph

Assumption is that we cover simple graph!

• edges are distinct(No multi-edges)
• edge for distinct vertices(No slef loops)

Notation

• V: set of vertices
• E$\subseteq V\times V$: set of pairs of vertices
• Direction : Directed/Undirected! We can distinguish them wheter edge are in parenthessis or curly bracket. curly bracket is for set notation which does not has order(undirected!)
• Neighbor
  • outgoing neighbor set : $Adg^+$
  • ingoing neighbor set : $Adg^-$
• degree: cardinality for neighbor

Graph Representation

We can store graph as a set data structure which maps vertex to (outgoing) neighbors or adjacency list.
Adjacency list is based on DAA or hash table when it requires fast mapping as possible.
Or we can use array or linked list for iteration.
As a result we store domain and codomain! that’s why it requires linear time $\Theta(\mid V \mid+ \mid E \mid)$. The reason why we distinguish vertices set and edges set is that it depends on circumstances. For sparse environment, cardinality of edges set is much less than quadratic

Connectivity

We consider undirected graph for connectivity in this course.

Connected (undirected) graph is a graph whose paths are connecting every vertices.

Unweighted Graph

Path

For vertex without path from source vertex $s$, we define infinite distance of path.

Shortest Paths Tree

For source vertex $s$, we’d like to know shortest path for each vertex in graph. To do so, it may takes quadratic if we search whole vertices for every vertex. Then we use “parent” concept so that trace the path. If we arrive at the leaf with respect to the source vertex, then look back the parent vertex which takes $O(\mid V \mid)$.

Weighted Graph

Weighted graph is a graph $G=(V,E)$ with weight function $w:E\to \mathrm{Z}$.

To implement weight graph, two methodologies exist with constant time

• With graph representation: store weight with each vertex in adj list
• Set DS: mapping each edge to its weight.(Hash table or DAA)

Weighted Path

Weight function maps edge to integer and we can calculate weight of “path” as follows:

$w(\pi) = \sum_{e\in\pi}w(e)$

Therefore we can say about weighted shortest path from $s \in V$ to $t \in V$ as path with minimum weight. The thing is that weight can be infinite so we define weight of shortest path as follows:

$\delta(s,t) = \inf$ {$w(\pi)\mid$ path $\pi$ from $s$ to $t\rbrace$

Negative weight cycle

We define negative-weight cycle as a path starting and ending at the smae vertex with negative weight, $w(\pi)$ For that cycle, weight becomes negative inifinite by repeatedly switching vertices.

Moreover, there does not exist parent pointers!

Directed Acyclic Graph : DAG

To solve graph problem, frequently used type of graph is DAG! You can see more details following posts.

Shortest Path Tree

This comprised of reachable vertex except negative weighted cycles.

Because it is comprised of reachable vertex except negative weighted cycles, we can construct with BFS which takes linear input time.

Detailed description will be covered in Graph Problems articles.