---
# System prepended metadata

title: 'HW8 - Q2, Q3'
tags: [109-2, 演算法]

---

# HW8 - Q2, Q3
###### tags: `演算法`, `109-2`


:::success
https://hackmd.io/xy4A31t6Qc2-yNeB-piAVg
:::

[TOC]

# Q2
## Question
Exercise 22.1-3
The **transpose** of a directed graph $G = (V, E)$ is the graph $G^T = (V, E^T)$, where $E^T ={ (v, u) ∈ V x V : (u,v) ∈ E }$. Thus, $G^T$ is $G$ with all its edges reversed. Describe efficient algorithms for computing $G^T$ from $G$, for both the adjacency-list and adjacencymatrix representations of $G$. Analyze the running times of your algorithms.

## Mein Answer

:::warning
```diff
- 抱歉 我寫錯題了 但還是放出來給大家笑笑
```

我有數學符號障礙 要先舉點例子再歸納回來 抱歉
![](https://i.imgur.com/RhbT0bu.png)

### 舉個例子
余有一有向圖
![](https://i.imgur.com/HhA6RJU.png)

其表達式 曰
![](https://i.imgur.com/U45q5Wh.png)

沿題幹所述 所為 transpose 表達式 是謂
![](https://i.imgur.com/KWTqice.png)

極言 所述 transpose 即為矢之反向
![](https://i.imgur.com/78Dk29E.png)

故 Adjacency-matrix 及 Adjacency-list 為
![](https://i.imgur.com/SN5hFV6.png)
![](https://i.imgur.com/rSPwtmj.png)

### 設計演算法
依錦文所好，以下稱 $n = V 的數量$、$m = E 的數量$

#### Adjacency-matrix 
由於輸入即是一 $n^2$ 大小的表格，我們也沒辦法把它壓的更小，只能爬每一格，有 1 的就把其位置的 transpose 存進結果的陣列

```c=
let G_t = new int[n][n] with values of 0
for u in (0 to n):
    for v in (0 to n):
        if G[u][v] == 1:
            G_t[v][u] = 1
```
時間複雜度 $O(n^2)$

#### Adjacency-list
概念跟上面一樣 把讀到有值的格子 位置的 transpose 存進結果的陣列
```c=
let G_t = new adjacency list 
for u in G:
    for v in G[u]:
        G_t[v].insert(u)
```
時間複雜度 $O(n+m)$
:::

# Q3

## Question
**Exercises 22.1-5**
The square of a directed graph $G = (V, E)$ is the graph $G^2 = (V, E^2)$ such that $(u, v) ∈ E^2$ if and only if $G$ contains a path with at most two edges between $u$ and $v$.
Describe efficient algorithms for computing $G^2$ from G for both the adjacency-list and adjacency-matrix representations of $G$. Analyze the running times of your algorithms.

## Mein Answer
// TODO 我文組的耶
![](https://i.imgur.com/SQm4AUn.png)

### 舉個粒子
![](https://i.imgur.com/Nyhhbmm.png)

Wonder zone
![](https://i.imgur.com/1Ywl2Qk.png)
![](https://i.imgur.com/WPlqR72.png)


### 來吧 為演算法而戰
一樣依錦文所好，以下稱 $n = V 的數量$、$m = E 的數量$
#### Adjacency-matrix 
```c=
let G_t = new int[v][v] with values of 0
for u in (0 to n):
    for v in (0 to n):
        if G[v][u] == 1:
            G_t[u][v] = 1
            for w in (0 to n):
                if G[v][w] == 1:
                    G_t[u][w] = 1;
```
時間複雜度 $O(n^3)$
> 附註：可以使用 Strassen's algorithm 把效率更加提升，但是在本題寫出來獲得的分數 與付出的心力將不成比例。

#### Adjacency-list
```c=
let G_t = new adjacency list with values as same as G
for u in G:
    for v in G[u]:
        for w in G[w]:
            G_t[v].insert(w)
```
時間複雜度 $O(nm)$