# 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

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

我有數學符號障礙 要先舉點例子再歸納回來 抱歉

### 舉個例子
余有一有向圖

其表達式 曰

沿題幹所述 所為 transpose 表達式 是謂

極言 所述 transpose 即為矢之反向

故 Adjacency-matrix 及 Adjacency-list 為

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

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

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 存進結果的陣列

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 我文組的耶

### 舉個粒子

Wonder zone

### 來吧 為演算法而戰
一樣依錦文所好，以下稱 $n = V 的數量$、$m = E 的數量$
#### Adjacency-matrix

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

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