---
# System prepended metadata

title: 吐司寫筆記：資料結構筆記
tags: [note, course, university course]

---

# 吐司寫筆記：資料結構筆記  

[![hackmd-github-sync-badge](https://hackmd.io/iGPiM7jrQUiX1mMdvMS1mA/badge)](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$  
![image](https://hackmd.io/_uploads/SJDywIoG1x.png)  

### 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.  
![image](https://hackmd.io/_uploads/rJnOnIof1l.png)  
```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;
            }
        }
    }
}
```
![image](https://hackmd.io/_uploads/BJisVdoGkg.png)

## Addition Linked List Operation  
### Free Nodes  
- Free nodes of linked lists can be **reused**  
    - Instead of using **malloc** and **free**  
    - Use **getNode** and **retNode**  
![image](https://hackmd.io/_uploads/HJLHSOjfyg.png)  

#### 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;
}
```
![image](https://hackmd.io/_uploads/SkAwU_jfJg.png)  

#### 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;
}
```
![image](https://hackmd.io/_uploads/BJtlD_sz1e.png)  

#### 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; 
    }
}
```
![image](https://hackmd.io/_uploads/BJ19jjoGJx.png)  

### 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;
}
```
![image](https://hackmd.io/_uploads/BJCUktofkx.png)  

## Tree  
![image](https://hackmd.io/_uploads/rkMP7mUzyg.png)
### 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  
![image](https://hackmd.io/_uploads/rkUmNQIGJx.png)

- **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  

![image](https://hackmd.io/_uploads/H1WtGNUGJg.png)

- List Representation  

![image](https://hackmd.io/_uploads/H1TDfELGkl.png)


### 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  

![image](https://hackmd.io/_uploads/Syye8VLzJl.png)

## 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**  

![image](https://hackmd.io/_uploads/BJAKP4Iz1g.png)

### Special Binary Trees  
#### Skewed tree  
- Tree is slanted to one side, only one leaf node  
- Like a linked list  
- Have worse complexity  

![image](https://hackmd.io/_uploads/H1VJFELMJg.png)

#### 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  

![image](https://hackmd.io/_uploads/Bkpyn4UMkg.png)

#### Full Binary Tree  
- Let binary tree $depth = k$  
- A full binary tree has $2^k-1$ nodes  

![image](https://hackmd.io/_uploads/rJ9xTN8Gye.png)

### 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*}$
    
![image](https://hackmd.io/_uploads/HJVdZHIf1l.png)

### 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$  

![image](https://hackmd.io/_uploads/B17mVH8zyg.png)  
![image](https://hackmd.io/_uploads/B1bV4S8GJg.png)  

#### 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  

![image](https://hackmd.io/_uploads/rkolBBIGyl.png)  

### Linked List Representation  
#### Format  
```c!=
typedef struct _treePointer{
    int data;
    treePointer leftChild, rightChild;
}treePointer;
```
![image](https://hackmd.io/_uploads/B1seDHUG1l.png)
![image](https://hackmd.io/_uploads/SyfzPB8zkg.png)

### Binary Tree Traversals  
#### Depth first traversals  
- **V**LR(preorder)  
- L**V**R(inorder)  
- LR**V**(postorder)  
![image](https://hackmd.io/_uploads/ryDNRSIzye.png)

#### Breadth first traversal  
- Level order travelsal  

#### Example : arithmetic expression  
![image](https://hackmd.io/_uploads/HyxsAH8M1g.png)
- **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)  

![image](https://hackmd.io/_uploads/HyHw0LIMkl.png)

#### Structure  
![image](https://hackmd.io/_uploads/H1VQVPUGkg.png)
```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  

![image](https://hackmd.io/_uploads/ryrltvIGye.png)

```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  

![image](https://hackmd.io/_uploads/HyIvcv8M1g.png)  

<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  

![image](https://hackmd.io/_uploads/Hk7FnPIMkl.png)

```c= !
typedef struct _threadPointer{
    boolean leftThread, rightThread;
    threadPointer leftChild, rightChild;
    char data;
}threadPointer;
```

#### Example  
![image](https://hackmd.io/_uploads/SyS40vUMkg.png)

### Virtual Root Node  
- Create a **virtual root node**  
- assign (2) **dangling pointers** to point to this root node  

![image](https://hackmd.io/_uploads/ryV3l_8zkl.png)

### 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  
![image](https://hackmd.io/_uploads/rJKm5d8zJl.png)

- 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 : 
![image](https://hackmd.io/_uploads/HJCu7R8f1e.png)
    - Min heap : 
![image](https://hackmd.io/_uploads/S1_cX0UMke.png)

### 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;
}
```
![image](https://hackmd.io/_uploads/HyEnuCUzyx.png)

#### 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;
}
```
![image](https://hackmd.io/_uploads/H1j5zywM1e.png)

### 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  

![image](https://hackmd.io/_uploads/H1CN5bwGye.png)

### 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);
}
```

![image](https://hackmd.io/_uploads/HyWaqWDGyg.png)

### Insertion  
- Use `rSearch()` to find the positions insert the new node  
![image](https://hackmd.io/_uploads/rJxXTrDfyg.png)

### Deletion  
- **Case 1. delete leaf node** : delete directly 

![image](https://hackmd.io/_uploads/rJ1teIvM1e.png)

- **Case 2. delete a node with one child** :  
    - Delete and **make the child the root of new subtree**  

![image](https://hackmd.io/_uploads/HJDteLwG1l.png)

- **Case 3. delete a node with two children**:  
    - Delete node  
    - Make **the largest element in the left subtreet** the root node of the subtree  

    ![image](https://hackmd.io/_uploads/Byx2xUwfkg.png)

    - Or make or **the smallest element in the right subtree** the root node of the subtree  

    ![image](https://hackmd.io/_uploads/BJanxUPM1l.png)

### Merge  
- **Three way join** :
    - Time Complexity : **O(1)**  
    - Height(mid) = 1 + max{height(small), height(big)} 
    ![image](https://hackmd.io/_uploads/B1o3Z8wM1e.png)
- **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  
    ![image](https://hackmd.io/_uploads/B1Qw78PM1e.png)

### Split  
![image](https://hackmd.io/_uploads/BJwgEIwGyl.png)  

### Balanced Search Trees  
- **Worst case** : skewed BST  
- On the average, the height is $log_2 n$ when random insertion/deletion are made  

![image](https://hackmd.io/_uploads/ryZASLDfJg.png)

- Search trees with a worst-case height of $log_2 n$ are called **balanced search trees**  

![image](https://hackmd.io/_uploads/HJonSIvGJg.png)
 
- 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  

![image](https://hackmd.io/_uploads/H1ByTivG1e.png)  

### Mering Ordered Sequences  
- Merge k **ordered sequences**, call **run** into a single sequences  

![image](https://hackmd.io/_uploads/rkuhTjvf1l.png)

- Solution :  
    - strightforward : $k-1$ comparisons per round  
    - selection tree : $O(log_2 k)$ comparisons per round  
    ![image](https://hackmd.io/_uploads/S1sWAoPMyl.png)

### Winner Tree  
- Copy **winner** to parent  
- Push **winner** to compare upper level  

![image](https://hackmd.io/_uploads/By5_73Pz1l.png)

### Loser Tree   
- Copy **Loser** in parent  
- Push **Winner** to compare upper level  

![image](https://hackmd.io/_uploads/rJvUL2wM1l.png)

## 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  

![image](https://hackmd.io/_uploads/rkGtD3DzJe.png)

### 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  
    ![image](https://hackmd.io/_uploads/SyMQYnPzye.png)

- **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  
    ![image](https://hackmd.io/_uploads/H1rN32wG1l.png)

- **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  
    ![image](https://hackmd.io/_uploads/SJSPh2PGkg.png)
    
## 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)$  
![image](https://hackmd.io/_uploads/SJVssBuG1g.png)

- **Directed graph** :  
    - Each edge is a directed pair of vertices  
    - $(v_0,v_1)\not =(v_1,v_0)$  
![image](https://hackmd.io/_uploads/ByTThBOzJl.png)

- **Complete graph** : 
    - Complete **undirected graph** : $n(n-1)/2$ edges  
    - Complete **directed graph** : $n(n-1)$ edges  
    ![image](https://hackmd.io/_uploads/Bk_i6HuGJl.png)

- **Self loops** : 
    - An edge from a vertex i, back to itself  
    ![image](https://hackmd.io/_uploads/rJkjxUuMke.png)

- **Multigraph** : 
    - Multiple occurences of the same edge  
    ![image](https://hackmd.io/_uploads/rkoslLuGyl.png)

### 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$  
    ![image](https://hackmd.io/_uploads/HyL-GLuGyl.png)

- **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$  
    ![image](https://hackmd.io/_uploads/HJx8mLOGyl.png)

### 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  
![image](https://hackmd.io/_uploads/HJ98ewOGke.png)

### 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  
![image](https://hackmd.io/_uploads/HJjsVP_z1l.png)

### 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  

![image](https://hackmd.io/_uploads/H1XewP_Myx.png)

### Degree of a Vertex  
- For **undirected graph** :  
    - The **degree** of a vertex is the number of edges incident to that vertex  
    ![image](https://hackmd.io/_uploads/HJrNDwdfkl.png)  
- 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**  
    ![image](https://hackmd.io/_uploads/SkIZOP_Myg.png)  
- 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  

![image](https://hackmd.io/_uploads/S1uF5nKG1e.png)  

- 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]$  

![image](https://hackmd.io/_uploads/SysVo3tzJe.png)
- For an **directed graph**, **out-degree** is **row sum**, **in-degree** is **column sum**  
![image](https://hackmd.io/_uploads/HJtFj3Yfye.png)  
    - $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  
![image](https://hackmd.io/_uploads/Hy_EeqqfJl.png)  

- 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;
```
![image](https://hackmd.io/_uploads/S1FgZs9Gkg.png)


- **Degree** of a vertex in an **undirected graph** = the number of nodes in adjacency list  
![image](https://hackmd.io/_uploads/SyKte5qGkx.png)  

- **Out-degree** of a vertex in a **directed graph** = the number of nodes in adjacency list  
![image](https://hackmd.io/_uploads/BJV3xqcz1e.png)  

- **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  
    ![image](https://hackmd.io/_uploads/SyT_mq5Gyl.png)

### Adjacency Multilists  
- Each edge/arc is represented by one node  
![image](https://hackmd.io/_uploads/rk4smqqzyg.png)  

```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  
![image](https://hackmd.io/_uploads/HJsXh9qM1x.png)  

### 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  
![image](https://hackmd.io/_uploads/BynscT9GJx.png)

### 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  
    ![image](https://hackmd.io/_uploads/BkTWCTcGJg.png)  
    - **Breadth first spanning tree** : use BFS  
    ![image](https://hackmd.io/_uploads/rkP6CacGJl.png)  

### 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  
    ![image](https://hackmd.io/_uploads/S15QxA9GJx.png)  

## 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  
 ![image](https://hackmd.io/_uploads/Bku4rCqMyl.png)  

### 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$  
 ![image](https://hackmd.io/_uploads/Syn4wAqfkx.png)  
- 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  
![image](https://hackmd.io/_uploads/SJJTo05Myg.png)  
<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)$  
    ![image](https://hackmd.io/_uploads/S1R_C05zJx.png)  
    
    2. Compute $low(u)$ for all nodes  
        - $low(u)$ : the lowest $dfn$ that can be reached from $u$ by a **path of descendants**  
    ![image](https://hackmd.io/_uploads/HkvgxJjzye.png)  
        - $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)$  
    ![image](https://hackmd.io/_uploads/ryo-W1iMke.png)  