# 吐司寫筆記：資料結構筆記
[](https://hackmd.io/iGPiM7jrQUiX1mMdvMS1mA)
**topic: `大學課程` `筆記`**
一段期中的內容難易度無須製作筆記，所以我沒做。
## Equivalence Relations
### Definition
- A relation over a set $S$, is said to be an **equivalence relation** over $S$ iff it is **reflexive**, symmetric, and transitive over $S$
- **Reflexive** : $x \equiv x$
- **Symmetric** : if $x \equiv y$, then $y \equiv x$
- **Transitive** : if $x \equiv y$ and $y \equiv z$, then $x \equiv z$
### Findeing Equivalent Classes
Two phase approach
- **Phase 1** :
- Read the equivalence pairs $(i, j)$
- Organize in a **linked list** (seq)
- New pointer will insert linked list in front of old pointers. By this way, new pointer only need to know where the head of linked list is.
```c= !
printf("Enter ... :");
scanf("%d%d", &i, &j);
while(i >= 0){
// store (i, j)
malloc(x, sizeof(*x));
x->data = j;
x->link = seq[i];
seq[i] = x;
// store (j, i)
malloc(x, sizeof(*x));
x->data = i;
x->link = seq[j];
seq[i] = x;
printf("Enter ... :");
scanf("%d%d", &i, &j);
}
```
- **Phase 2** :
- Begin at 0 and find all pairs of the form $(0,j)$ and $(j,0)$, then all pair of $(j,*)$ and $(*,j)$
- Find another object not yet output, and **repeat** the above process
```c= !
#include <stdio.h>
#define MAX_SIZE 24
#define FALSE 0
#define TRUE 1
typedef struct _nodePointer{
int data;
nodePointer link;
}nodePointer;
void main(old){
short int out[MAX_SIZE];
nodePointer seq[MAX_SIZE];
nodePointer x, y, top;
int i, j, n;
printf(“Enter the size (<=%d) ”, MAX_SIZE);
scanf(“%d”, &n);
for(i=0; i<n; i++){
/*initialize seq and out */
out[i] = TRUE; seq[i] = NULL;
}
// Phase 1
// Phase 2
for(i = 0;i < n;i++){
// has not visited
if(out[i]){
printf("\nNew class: %5d", i);
out[i] = FALSE; // set class to false
x = seq[i]; // init stack
top = NULL;
// find rest of class
for(;;){
while(x){
j = x->data;
if(out[j]){
printf("%5d", j);
out[j] = FALSE;
y = x->link;
x->link = top;
top = x;
x = y;
}else{
x = x->link;
}
}
if(!top)break;
x = seq[top->data];
top = top->link;
}
}
}
}
```
## Addition Linked List Operation
### Free Nodes
- Free nodes of linked lists can be **reused**
- Instead of using **malloc** and **free**
- Use **getNode** and **retNode**
#### getNode()
- Exam the list of free nodes headed by **avail**
- If the list is not empty, then use one of its nodes
- Else **malloc** to create a new node
```c= !
polyPointer getNode(void){
polyPointer node;
if(avail){
// borrow a node from avail
node = avail;
avail = avail->link;
}else{
malloc(node, sizeof(*node));
}
return node;
}
```
#### retNode()
- Returning a node(node) to the list of free nodes
- Insert **node** to the front of the list headed by **avail**
- Initially, we set **avail** to NULL
```c= !
void retNode(polyPointer node){
node->link = avail;
avail = node;
}
```
#### cerase()
- Erase a **circular list** in a fixed amount (constant) of time : $O(1)$
- Independent of the number of nodes in list
```c= !
void cerase(polyPointer *ptr){
polyPointer temp;
if(*ptr){
temp = (*ptr)->link;
(*ptr)->link = avail;
avail = temp;
*ptr = NULL;
}
}
```
### Inverting a Chain
- For a list of $length\le 1\ nodes$
- The **while** loop is executed $length$ times
- the computing time is linear $O(length)$
```c= !
listPointer invert(listPointer lead){
listPointer middle, trail;
middle = NULL;
while(lead){
trail = middle;
middle = lead;
lead = lead->link;
middle->link = trail; // inverse link
}
return middle;
}
```
## Tree
### Formal Definition of Trees
- A tree is a **final set of one or more nodes**
- There is a specially designated node: the **root node**
- Every node in the tree is the root node of some **subtree**
### Terminology Definitions
- **Edge** : the side connect node and node
- **Root** : the top node of the tree
- **Parent** : X is parent of its children
- **Children** : the nodes in subtree which root node is X and connect X directly.
- **Terminal nodes(leaf node, external node)** : nodes that have degree zero
- **Nonterminal nodes(internal node)** : nodes that don't belog to terminal nodes
- **Sliblings** : children of the same parent are said to be siblings
- **Ancestors** : all the nodes along the path from the root to that node
- **Descendants** : all the nodes in the subtree which root is the node.
- **Depth(height)** : the maximum level of any node in the tree
- **Degree** : the number of substree of a node
- **Degree of a tree** : the maximum degree of the nodes in the tree
### Tree Representations
- Graph Representaion
- List Representation
### Left Child-Right Sibling Representation
- **Target** : reduce degree of tree
- **Method** : connect the **right siblings** of the node and cut the edges connecting siblings to parent off
- **Result** : all trees can became **binary trees** by this method
## Binary Tree
### Definition
- Any node can have **at most 2 branches**
- Every substree in binary tree is also binary tree
- call **left subtree** and **right subtree**
### Special Binary Trees
#### Skewed tree
- Tree is slanted to one side, only one leaf node
- Like a linked list
- Have worse complexity
#### Complete binary tree
- Let binary tree have $n level$
- Nodes up to level $n-1$ all exist ($2^n-1$ nodes)
- Nodes at level $n$ exist in order from left to right
#### Full Binary Tree
- Let binary tree $depth = k$
- A full binary tree has $2^k-1$ nodes
### Properties of Binary Tree
- Maximum number of nodes on **level i** : $2^{i-1}$
- Maximum number of nodes in a **binary tree of depth k** : $2^k-1$
- **the number of leaf nodes and the number of degree-2 nodes**
- let $n_0$ is number of leaf nodes, $n_2$ is number of number of degree 2
- then $n_0=n_2+1$
- prove :
$\begin{align*}
edge &= node - 1 \\
1 \times n_1 + 2 \times n_2 &= n_0 + n_1 + n_2 + 1 \\
n_2 &= n_0 - 1
\end{align*}$
### Array Representation
#### Format
We can represent a complete binary tree sequentially, than for any node with index $i$, $1 <= i <= n$, we have :
- Parent(i) has index $\lfloor i/2 \rfloor$, if $i \ge 2$
- LeftChild(i) has index $2i$, if $2i \le n$
- RightChild(i) has index $2i + 1$, if $2i + 1 \le n$
#### Problem
- **Worse case** : a **skewed tree** of depth $k$ requires $2^k-1$ space but only use $k$ spaces
- It is hard to visualize
- Insertion or deletion of nodes from the middle of a tree have large time complexity
### Linked List Representation
#### Format
```c!=
typedef struct _treePointer{
int data;
treePointer leftChild, rightChild;
}treePointer;
```
### Binary Tree Traversals
#### Depth first traversals
- **V**LR(preorder)
- L**V**R(inorder)
- LR**V**(postorder)
#### Breadth first traversal
- Level order travelsal
#### Example : arithmetic expression
- **Inorder travel (infix expression)** : A / B * C * D + E
```c= !
void inorder(treePointer ptr){
if(ptr){
inorder(ptr->leftChild); // L
printf("%d", ptr->data); // V
inorder(ptr->rightChild); // R
}
return;
}
```
- **preorder travel (prefix expression)** : + * * / A B C D E
```c= !
void preorder(treePointer ptr){
if(ptr){
printf("%d", ptr->data); // V
preorder(ptr->leftChild); // L
preorder(ptr->rightChild); // R
}
return;
}
```
- **postorder traversal (postfix expression)** : A B / C * D * E +
```c= !
void postorder(treePointer ptr){
if(ptr){
postorder(ptr->leftChild); // L
postorder(ptr->rightChild); // R
printf("%d", ptr->data); // V
}
return;
}
```
- **level order traversal** : + * E * D / C A B
```cpp= !
void levelOrder(treePointer ptr){
int front = rear = 0;
treePointer queue[MAX_QUEUE_SIZE]; // queue
if(!ptr) return;
pushq(front, &rear, ptr);
while(1){
// FIFO
ptr = popq(&front, rear);
if(ptr){
printf("%d", ptr->data);
if(ptr->leftChild){
pushq(front, &rear, ptr->leftChild);
}
if(ptr->rightChild){
pushq(front, &rear, ptr->rightChild);
}
}else{
break;
}
}
}
```
### Copying Binary Tree
```c= !
treePointer copy(treePointer original){
treePointer temp;
if(original){
malloc(temp * sizeof(*temp));
temp->leftChild = copy(original->leftChild);
temp->rightChild = copy(original->rightChild);
temp->data = original->data;
return temp;
}
return NULL;
}
```
### Testing for Equivalent Trees
```c= !
int equal(treePointer first, treePointer second){
// both of first and second are NULL
if(!first && !second)return 1;
// both of first and second are not NULL
if(first->data == second->data &&
equal(first->left, second->left) &&
equal(first->right, second->right))return 1;
// else
return 0;
}
```
### Propositional Calculus Expression
- **Boolean Variable** : **true** or **false** only
- **Logical Operators** : $\land$(and), $\lor$(or), $\lnot$(not)
#### Structure
```c= !
typedef enum {not, and, or, true, false} logical;
typedef struct _treePointer{
logical data;
short int value;
treePointer leftChild, rightChild;
}treePointer;
```
#### Evaluation
- Use **postorder traversal** to evaluate expression
```c= !
void postOrderEval(treePointer node){
if(node){
postOrderEval(node->leftChild); // L
postOrderEval(node->rightChild); // R
switch(node->data){ // V
case not: // not's child must be its right child
node->value = !node->rightChild->value;
break;
case and:
node->value = node->rightChild->value && node->leftChild->value;
break;
case or:
node->value = node->rightChild->value || node->leftChild->value;
break;
case true:
node->value = true;
break;
case false:
node->value = false;
break;
}
}
return;
}
```
## Threaded Binary Trees
- **Target** : replace null pointers with useful **threads**
*(不要用 threads, 那是什麼智障玩意兒)*
### Definition
- Make **null left child pointer** points to the **inorder predecessor** of the node
- Make **null right child pointer** points to the **inorder successor** of the node
<p class="text-center">(Inorder : A B C D E F G H I)</p>
- It make it possible to traverse the values in the binary tree via a **linear traversal**
- more rapid than a recursive inorder traversal
### Implementation Considerations
- Two additional boolean fields in the node structure
- if **true** : contain a thread
- if **false** : points to the child
```c= !
typedef struct _threadPointer{
boolean leftThread, rightThread;
threadPointer leftChild, rightChild;
char data;
}threadPointer;
```
#### Example
### Virtual Root Node
- Create a **virtual root node**
- assign (2) **dangling pointers** to point to this root node
### Inorder Traversal of Threaded Binary Tree
- Time Complexity : **O(n)**
- Without **stack** to store nodes
```c= !
threadPointer insucc(threadedPointer tree){
threadedPointer temp;
temp = tree->rightChild;
if(!tree->rightThread){ // 先向右，然後一路向左
while(!temp->leftThread){
temp = temp->leftChild;
}
}
return temp
}
void tinorder(threadedPointer tree){
/* traverse the threaded binary tree inorder */
threadedPointer temp = tree;
while(1){
temp = insucc(temp);
if(temp == tree)break;
printf("%3c", temp->data)
}
return;
}
```
### Insertion
- Insert new node r as a right child of node s
```c= !
void insert_right(threadPointer s, threadedPointer r){
threadedPointer temp;
r->rightChild = s->rightChild;
r->rightThread = s->rightThread;
r->leftChild = s;
r->leftThread = true;
s->rightChild = r;
s->rightThread = false;
if(r->rightThread){
temp = insucc(r);
temp->leftChild = r;
}
return;
}
```
## Heap
### Definition
- **Max (min) tree** : a tree in which the key value in each node is **no smaller (larger) than** the key value of children
- **Max (min) heap** : a **complete binary tree** that is also a max (min) tree
- The root of **max (min) heap** contains the **largest (smallest) element**
- Max heap :
- Min heap :
### Basic Operation
#### Insertion
- Insertion into a max heap
- Time complexity : **O(logn)**
```c= !
void push(element item, int *n){
int i;
// Judge if heap is full
if(HEAP_FULL(*n)){
fprintf(stderr, "The heap is full, \n");
exit(1);
}
// Add a space
i = ++(*n);
// modify position
while((i != 1) && (item.key > heap[i/2].key)){
heap[i] = heap[i/2];
i /= 2;
}
heap[i] = item;
return;
}
```
#### Deletion
- Deletion from a max heap
- Time complexity : **O(logn)**
```c= !
element pop(int *n){
int parent, child;
element item, temp;
// Judge if heap is empty
if(HEAP_EMPTY(*n)){
fprintf(stderr, "The heap is empty\n");
exit(1);
}
item = heap[1];
temp = heap[(*n)--];
parent = 1;
child = 2;
while(child <= *n){
if(child < *n && heap[child].key < heap[child + 1].key){
child++;
}
if(temp.key >= heap[child].key)break;
parent = child;
child *= 2;
}
heap[parent] = temp;
return temp;
}
```
### Priority Queues
- **Definition** : entries in queue are ordered according to priority
- Use **heaps** to implement priority queue
- **Delete** element with **highest (lowest) priority**
- **Insert** the element with **arbitrary priority**
- Compare time complexity
| Representation | Insertion | Deletion |
| --------------------- | --------- | -------- |
| Unordered array | O(1) | O(N) |
| Unordered linked list | O(1) | O(N) |
| Sorted array | O(N) | O(1) |
| Sorted linked list | O(N) | O(1) |
| Max heap | O(logN) | O(logN) |
### Problem
Heaps have bad complexity on **deletion** and **search** :
- Deletion : **O(n)**
- Search : **O(n)**
Solution : **Binary Search Tree**
## Binary Search Tree (BST)
### Definition
- Every element has **unique key**
- The keys in a nonempty **left substree** is **smaller** than the key in the root of the subtree
- The keys in a nonempty **right substree** is **larger** than the key in the root of the subtree
- The subtrees in BST are also BSTs
### Searching
```c= !
element* rSearch(treePointer root, int k){
if(!root)return NULL;
if(k == root->data.key)return &(root->data);
if(k < root->data.key)return rSearch(root->leftChild, k);
return rSearch(root->rightChild, k);
}
```
### Insertion
- Use `rSearch()` to find the positions insert the new node
### Deletion
- **Case 1. delete leaf node** : delete directly
- **Case 2. delete a node with one child** :
- Delete and **make the child the root of new subtree**
- **Case 3. delete a node with two children**:
- Delete node
- Make **the largest element in the left subtreet** the root node of the subtree
- Or make or **the smallest element in the right subtree** the root node of the subtree
### Merge
- **Three way join** :
- Time Complexity : **O(1)**
- Height(mid) = 1 + max{height(small), height(big)}
- **Two way join** :
- Make **the largest element in small tree** or **the smallest element in the big tree** the root node of the new tree
### Split
### Balanced Search Trees
- **Worst case** : skewed BST
- On the average, the height is $log_2 n$ when random insertion/deletion are made
- Search trees with a worst-case height of $log_2 n$ are called **balanced search trees**
- Time Complexity :
| Operation | Average | Skewed Tree |
| --------- | ------- | ----------- |
| Searching | O(logn) | O(n) |
| Insertion | O(logn) | O(n) |
| Removal | O(logn) | O(n) |
- How to **prevent worst case?** :
- **Rebalancing** scheme
- AVL, 2-3, and **Red-black tree**
## Selection Trees
- **Winner (Loser) tree** is a binary tree where each node is the smaller (lager) of its two children
- root node is the smallest (largest) node in the tree
- a winner is the record with smaller (larger) key
- Application :
- Tournaments
- Merge sequences
### Mering Ordered Sequences
- Merge k **ordered sequences**, call **run** into a single sequences
- Solution :
- strightforward : $k-1$ comparisons per round
- selection tree : $O(log_2 k)$ comparisons per round
### Winner Tree
- Copy **winner** to parent
- Push **winner** to compare upper level
### Loser Tree
- Copy **Loser** in parent
- Push **Winner** to compare upper level
## Forests
### Definition
A forest is a set of n >= 0 **disjoint trees**
### Transforming
- Convert to **Left-child-right-sibling** tree first
- Then convert to a **BST** before attaching
### Traversing
- **Preorder traversal** :
1. If F is empty, then return
2. Visit the root of the **first** tree of F
3. Traverse the subtrees of first tree in forest preorder
4. Traverse the **remaining trees** of F in forest preorder
- **Inorder traversal** :
1. If F is empty, then return
2. Traverse the subtrees of first tree in forest preorder
3. Visit the root of the **first** tree of F
4. Traverse the **remaining trees** of F in forest preorder
- **Inorder traversal** :
1. If F is empty, then return
2. Traverse the subtrees of first tree in forest preorder
3. Traverse the **remaining trees** of F in forest preorder
4. Visit the root of the **first** tree of F
## Graphs
### Definition
- A graph G consists of two sets
- **Vertices V(G)** : a finite, nonempty set
- **Edge E(G)** : a finite, possible empty set
- **G(V,E)** represents a graph
### Terminology
- **Undirected graph** :
- The pair of vertices in a edge is **unordered**
- $(v_0,v_1)=(v_1,v_0)$
- **Directed graph** :
- Each edge is a directed pair of vertices
- $(v_0,v_1)\not =(v_1,v_0)$
- **Complete graph** :
- Complete **undirected graph** : $n(n-1)/2$ edges
- Complete **directed graph** : $n(n-1)$ edges
- **Self loops** :
- An edge from a vertex i, back to itself
- **Multigraph** :
- Multiple occurences of the same edge
### Adjacency
- **Unordered graph** :
- $v_0$ and $v_1$ are **adjacent**
- The edge $(v_0,v_1)$ is **incident** on vertices $v_0$ and $v_1$
- **Directed graph** :
- $v_0$ is **adjacent to** $v_1$, and $v_1$ is **adjacent from** $v_0$
- The edge $<v_0,v_1>$ is incident on $v_0$ and $v_1$
### Subgraphs
- A **subgraph** of $G$ is a graph $G_1$ such that $V(G_1)\subseteq V(G)$ and $E(G_1)\subseteq E(G)$
### Path
- A path from vertex $v_p$ to vertex $v_q$ in a graph G
- The **length of a path** is the number of edges on it
### Simple path and cycle
- **Simple path** : a path in which all vertices, except possibly the first and the last, are distinct
- A **cycle (circuit)** is a simple path in which the first and the last vertices are the same
### Connected Component
- For **undirected graph**
- A **connected component** is a maximal connected subgraph
- A tree is a graph that is connected and **acyclic (without cycle)**
### Strongly Connected Component
- A directed graph is **strongly connected** if there is a **directed path** from $v_i$ and $v_j$ and from $v_j$ to $v_i$
- A **strongly connected component** is a maximal subgraph that is strongly connected
### Degree of a Vertex
- For **undirected graph** :
- The **degree** of a vertex is the number of edges incident to that vertex
- For **directed graph** :
- **In-degree** : the number of edges that have $v$ as the **head**
- **Out-degree** : the number of edges that have $v$ as the **tail**
- Relation between **edges** and **degree** :
- $e=(\sum_{i=0}^{n-1}d_i)/2$
## Graph Representations
### Adjacency Matrix
Let $G=(V,E)$ be a graph with $n$ vertices
- The **adjacency matrix** of $G$ is a two-dimensional $n \times n$ array
- If the edge $(v_i,v_j)$ is in $E(G)$, then $adj\_mat[i][j] = 1$
- If the edge $(v_i,v_j)$ is **not** in $E(G)$, then $adj\_mat[i][j] = 0$
- The adjacency matrix for an **undirected graph** is **symmetric**
- The adjacency matrix for an **directed graph** may not be summetric
- For an **undirected graph**, **the degree of any vertex i** is its **row sum**
- $deg_i = \sum_{j=0}^{n-1}adj\_mat[i][j]$
- For an **directed graph**, **out-degree** is **row sum**, **in-degree** is **column sum**
- $in\_deg_i = \sum_{i=0}^{n-1}adj\_mat[i][j]$
- $out\_deg_i = \sum_{j=0}^{n-1}adj\_mat[i][j]$
### Adjacency Lists
- Vertices can be in any order
- Order is of no significance
- The nodes in list i
- The vertices that are **adjacent** from vertex i
- Code :
```c= !
#define MAX_VERTICES 50
typedef struct node *node_pointer;
typedef struct node{
int vertex;
struct node *link;
};
node_pointer graph[MAX_VERTICES];
int n = 0;
```
- **Degree** of a vertex in an **undirected graph** = the number of nodes in adjacency list
- **Out-degree** of a vertex in a **directed graph** = the number of nodes in adjacency list
- **In-degree** of a vertex in a **directed graph**
- Need to traverse the whole data structure
- The number of nodes in the **inverse** adjacency list
### Adjacency Multilists
- Each edge/arc is represented by one node
```c= !
typedef struct edge *edge_pointer;
typedef struct edge{
short int marked;
int vertex1, vertex2;
edge_pointer path1, path2;
};
edge_pointer graph[MAX_VERTICES];
```
- Each node is linked to another node that is incident to one of two vertices
- Follow path 1 link to the next node containing vertex 1
- Follow path 2 link to the next node containing vertex 2
### Network
- The edges of a graph may have **weights** assigned to them.
- e.g distance, time...etc.
- To store the weights
- **Adjacency matrix** : store in $adj\_mat[i][j]$
- **Adjacency lists** : add a weight field
- A graph with weighted eedges is call a **network**
## Traversals
### Depth first search (DFS)
- Save them in a stack or recursive function
```c= !
void dfs(int v){
node_pointer w;
visited[v] = true;
printf("%5d", v);
for(w = graph[v]; w; w = w->link){
if(!visted[w->vertex]){
dfs(w->vertex);
}
}
}
```
### Breadth first search (BFS)
- Explore all nodes that are same "distance" away from the starting node
- **Queue** is a natural data structure fir BFS
- Nodes at incremental distance away are placed in queue in order
```c= !
node_pointer w;
queue_pointer front, rear;
front = NULL;
rear = NULL;
printf("%d", v);
visited[v] = TRUE;
addq(&front, &rear, v); // queue.push
while(front){ // check if queue is empty
v = deleteq(&front); // queue.pop
for(w = graph[v]; w; w = w->link){
if(!visted[w->vertex]){
printf("%5d", w->vertex);
addq(&front, &rear, w->vertex); // queue.push
visited[w->vertex] = true;
}
}
}
```
### Connected components
If G is an undirected graph, To determine whether or not it is connected
- Simply **dfs** or **bfs**
- Then determining if there is any unvisited vertex
```c= !
void connected (void){
int i;
for(i = 0;i < n;i++){
if(!visited[i]){
dfs(i);
printf("\n");
}
}
return;
}
```
## Spanning Trees
### Definition
- If a tree T is a **subgraph** of G, and **T contains all vertices of G**, then tree T is a **spanning tree** of G
- $E(G) = T(tree\ edges) + N(nontree\ edges)$
- T: set of edges used during search
- N: set of remaining edges
### Create Spanning Tree
- When we traversal a tree, we also create a spanning tree
- We can use **DFS** and **BFS** to build a spanning tree
- **Depth first spanning tree** : use DFS
- **Breadth first spanning tree** : use BFS
### Properties of Spanning Trees
- A **spanning tree** $T$ has $n-1$ edges ($n$ nodes in the graph)
- If a nontree edge $(v,w)$ is inserted into any spanning tree $T$ than **a cycle** is formed
- A spanning tree $T$ is a minimal subgraph $G_1$ of G
- Minimal subgraph: $V(G_1)\subseteq V(G)$ and $G_1$ is **connected** with fewest number edges
## Biconnected Graph
### Articulation Point
Let $G$ be an **undirected connected graph**
- A vertex $v$ of $G$ an **articulation point**
- Deleteing $v$ and all edges incident to $v$
- will divide the graph $G$ into 2 or more connected components
### Biconnected Component
- A **biconnected graph** is a connected graph that has no articulation points
- A **biconnected component** of a connected graph $G$ is a maximal biconnected subgraph $H$ of $G$
- A biconnected component $H$ of a graph $G$ is a **maximal biconnected subgraph** if
- G contains no other subgraph that is both biconnected and properly contain H
### Find Biconnected Components
Spanning tree generated dy **DFS** on graph
- A nontree edge $(u,v)$ is a **back edge**
- Iff either $u$ is an ancestor of $v$ or $v$ is an ancestor of $u4$
- All nontree edges are back edges
<p class="text-center">(Red lines is back edges)</p>
- **Articulation point**
1. **Root** : iff it has at least 2 children
2. Any other vertex $u$ has at least one child $w$ cannot reach an ancestor of $u$ if we removed $u$
- **Find biconnected components**
1. Finding the depth first spanning tree of $G$
- Define the depth first number $(dfn)$ as the DFS visit sequence
- Note : If u is an **ancestor** of $v$ then $dfn(u) < dfn(v)$
2. Compute $low(u)$ for all nodes
- $low(u)$ : the lowest $dfn$ that can be reached from $u$ by a **path of descendants**
- $low(u) = min\{dfs(u),min\{low(w)|w\ is\ a\ child\ of\ u\}, min\{dfn(w) | (u,w)\ is\ a\ back\ edge\}\}$
3. Determining articulation points
- If $u$ is the **root** of the spanning tree and **has two or more children**
- If $u$ has at least one child $w$ such that $low(w)\ge dfn(u)$
Sign in with Wallet
Connect another wallet