圖論初體驗

發布日期

2024年4月17日

圖論是一門談「圖」的理論，先等等……，不是照片或圖片喔！這裡的圖代表的是由點 （vertex）和邊（edge）所構成的物件，一個邊連接兩個點，或同一個點。 透過圖論，我們可以解決許多看似難以分析的問題，所以請繼續讀下去。

正式定義

一個圖是一個集合，這個集合$G=V+E$，$V$為點集合，$E$為邊集合。 接下來定義一些術語：

• 邊：一個邊有起始點$u$至$v$被寫為$e(u,v)$，若為有向邊，$u \neq v \implies e(u,v) \neq e(v, u)$。
• 自環：一個自環便是$e(n,n)$。
• 循環：一個圖的循環是可以透過路徑從一點出發回到同點的路徑。
• 權重：點和邊都可以有特定數值或資訊。

圖由一些特質可以細分為許多種， 最簡單的圖是簡單圖，一種沒有自環（連同樣點的邊）也沒有方向的圖。 第二簡單的便是 DAG（Directed Acyclic Graph），又稱為有向無環圖。

拓樸性質

由於圖是代表元素關係的方式，圖的形狀並不是我們關心的， 因此會出現同構（isomorphism）現象。一個圖的點可以隨意放置；邊可以彎曲亂繞， 不會影響到圖的架構，這是圖的特性。

圖的實作

圖的實作方法有很多種，不過複雜度各有不同。

1. 第一種是使用相鄰矩陣

#include <stdio.h>
#define MAX_NODES 100

size_t nodes = 0;
int adj[MAX_NODES][MAX_NODES] = {0};
/**
 * adj[x][y] = adj[y][x] = 是否連接
 */

int main()
{
    printf("nodes: ");
    scanf("%u", &nodes);
    printf("input edges x y (until -1):\n");
    while(1)
    {
        int x,y;
        scanf("%d %d", &x, &y);
        if(x < 0 || y < 0) break;
        adj[x][y] = adj[y][x] = 1;
    }
    for(size_t i = 0; i < nodes; i++)
    {
        printf("adjs of %d are: ", i);
        // 線性搜尋O(mn)
        for(size_t j = 0; j < nodes; j++)
        {
            if(i == j || !adj[i][j]) continue;
            printf("%d ", j);
        }
        printf("\n");
    }
    return 0;
}

2. 第二種是使用相鄰存點

#include <stdio.h>

#define MAX_NODES 100

size_t nodes = 0;
size_t adj[MAX_NODES][MAX_NODES + 1] = {0};

int main()
{
    printf("nodes: ");
    scanf("%u", &nodes);
    printf("input edges x y (until -1):\n");
    while(1)
    {
        int x,y;
        scanf("%d %d", &x, &y);
        if(x < 0 || y < 0) break;
        adj[x][adj[x][MAX_NODES]++] = y;
        adj[y][adj[y][MAX_NODES]++] = x;
    }
    for(size_t i = 0; i < nodes; i++)
    {
        printf("adjs of %d are: ", i);
        // 線性列舉O(m)
        for(size_t j = 0; j < adj[i][MAX_NODES]; j++)
        {
            printf("%u ", adj[i][j]);
        }
        printf("\n");
    }
    return 0;
}

在讀取上，相鄰矩陣最糟情況為$O(n^2)$，而相鄰存點是$O(n)$， 不過在檢測是否有邊的時候，相鄰矩陣是$O(1)$，而相鄰存點是$O(n)$， 時間差異非常大。

特殊圖

以下將介紹一些有特殊應用的圖。

二分圖

一個二分圖由兩個只有點的圖所組成的，因此$G=(E_1 + E_2, V)$， 因為可以用來表達多種問題，像是配對組隊問題，因此被廣泛應用。

網路流

一個符合網路流的圖中，邊上都有權重且都有方向，圖上所有點的入邊的權重相加和出邊的權重相加一樣大。 網路流可以用來解決優化排程問題，搭配特定演算法可以大幅加速。一個網路流有源頭（source）與終點（sink）， 分別代表流入總流量與流出總流量，需要互相抵銷。

圖的相關演算法

深度／廣度優先搜尋／走訪

談到圖的演算法，絕對要先講到經典的 DFS 與 BFS。其中 DFS 指的是在走訪時，直到窮盡某一狀態結束， 且此走訪模式可以被表示為一種堆疊，因此 DFS 可以使用遞迴製作。相對的， BFS 是走訪時盡可能先拜訪相鄰點，通常使用佇列實作。DFS 與 BFS 的通用版本（Generalized Version） 的時間複雜度都是非多項式時間，因此需要再透過資料結構優化。

最大匹配問題

在一張圖中，一個匹配是邊集合的子集合，匹配中的邊與點集合所組成的圖中， 每個點最多只能連接一個點，這件事看起來像是把點兩兩匹配，因此被稱為匹配。 最大匹配即在探討如何得到最多個倆倆匹配的點，時間複雜度非常可觀，媲美 DFS 的複雜度， 不過，有些演算法使這件事簡單化許多。

1. 柯尼西定理：由 Dénes Kőnig 於 1931 提出，使用交錯路（alternating path，即由非匹配邊出發， 交錯走匹配與非匹配邊的道路）證明此定理（證明略），他提出以下論點，擷取自維基百科： 「在任意二部圖中，最大匹配的邊數等於最小頂點覆蓋的頂點數。」透過此定理， 我們可以透過找到最小點覆蓋找到最大匹配，最簡單的實作方法便是 DFS。

2. 埃特蒙德-卡普演算法：將二分圖的$U$向與$V$向各自接上源頭與終點，然後將每個邊的權重設為一， 則尋找最大流的時候便是在尋找最大匹配了。因為要找到網路流，勢必要將一個點連向的其他點刪去，剩下一點， 這樣的剪裁步驟最大化，找到的便是最小點覆蓋，由柯尼西定理可知推得最大匹配。虛擬碼如下：

from = ∅
algorithm search_aug(res_graph, source, sink) returns boolean:
	visited := {source}, queue q
	append source to q
	while q ≠ ∅:
		c := front of q
		pop q
		for edge in edges that start from c:
			u := edge.from
			v := edge.to
			if v in visited or res_graph[edge] ≤ 0:
				continue
			if v == sink:
				from[v] := u // 找到終端點
				return true
			append v to q
			from[v] := u
			append v to visited
	return false

algorithm edmonds_karp(flow_network, src, sink) returns number:
	res_graph := flow_network, max_flow := 0 // 初始容量圖
	while search_aug(res_graph, src, sink):
		path_flow := INT_MAX
		v := sink
		repeat // 找到目前擴增路徑的邊集合之最小容量
			u := from[v]
			path_flow := min(path_flow, res_graph[edge(u, v)])
			v := u
		until v == src
		v := sink
		repeat // 新增反向的可能
			u := from[v]
			res_graph[edge(u, v)] -= path_flow
			res_graph[edge(v, u)] += path_flow
			v := u
		until v == src
		max_flow += path_flow
	return max_flow

3. 福特-富爾克森演算法：埃特蒙德-卡普演算法的 DFS 版，速度其實沒有差很多，理論值很大罷了。 實作上如下：

visited := ∅
algorithm find_path(u_node) returns boolean:
	if u_node ∈ visited:
		return false
	for v_node in u_node.edges:
		if v_node.match == null:
			v_node.match := u_node
			return true
		if v_node.match != u_node and find_path(v_node.match):
			v_node.match := u_node // 反轉匹配（匹配換人）
			return true
		// 若v_node.match == u_node代表這個位子不能找到增廣路徑
	return false
algorithm max_matching(U, V, E) returns number:
	matches := 0
	for u_node in U:
		visited := ∅
		if find_path(u_node):
			matches := matches + 1
	return matche

最短路徑問題

最短路徑在許多區域都有應用，像是最直覺的便是找到地圖上兩點最短路徑。這種問題看似簡單， 但是如果是使用廣度優先搜尋法，時間複雜度超乎想像， 因此，許多運用動態程式設計的演算法如雨後春筍般冒出。

1. 傳統 BFS 演算法：透過擴散找到觸及節點的瞬間，效率非常低。

2. Djikstra 演算法：有透過動態程式設計的方式儲存現在的狀態，複雜度降低至$O(n \log{n})$。 Djikstra 演算法的優點在於當給定一個起始點時，可以找到圖中所有點到起始點的最短路徑， 在有如此需求的問題中非常強大。在實際設計上，Djikstra 與 BFS 最大的不同在於：BFS 使用 FIFO 佇列， 而 Djikstra 使用優先程度，Priority 越小的（即離出發點最近的），最先被搜尋， 即$p(v)=d(v)$，因為最有機會找到最短路徑。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 100

size_t nodes;
int adjweight[MAX_NODES][MAX_NODES];
int adjlist[MAX_NODES][MAX_NODES + 1] = {0};
size_t previous[MAX_NODES];
int mindist[MAX_NODES];
int visited[MAX_NODES] = {0};

size_t from, to;

/**
 * 定義優先佇列
 * Define Priority Queue
 */
struct PriorityData {
    size_t node;
    int priority;
};

struct PriorityQueue {
    struct PriorityData data[MAX_NODES];
    size_t size;
};

int _priority_queue_cmp(struct PriorityData const *const a,
                        struct PriorityData const *const b) {
    return a->priority - b->priority;
}

//  是否空的
int empty(struct PriorityQueue *const pq) { return !pq->size; }

// 加入佇列並排序
void enqueue(struct PriorityQueue *const pq, struct PriorityData val) {
    pq->data[pq->size++] = val;
    qsort(pq->data, pq->size, sizeof(struct PriorityData),
          (int (*)(const void *, const void *))_priority_queue_cmp);
}

// 砍頭
struct PriorityData dequeue(struct PriorityQueue *const pq) {
    struct PriorityData x = pq->data[0];
    for (size_t i = 1; i < pq->size--; i++) {
        pq->data[i - 1] = pq->data[i];
    }
    return x;
}

struct PriorityQueue traverse_queue = {.size = 0};

int main() {
    memset(mindist, -1, sizeof(mindist));
    printf("Node Count: ");
    scanf("%zu", &nodes);
    printf("Edges x y w until 0 0 0: \n");

    while (1) {
        size_t x, y;
        int w;
        scanf("%zu %zu %d", &x, &y, &w);
        if (x == 0 && y == 0 && w == 0)
            break;
        if (x == y)
            continue;

        adjweight[x][y] = adjweight[y][x] = w;
        adjlist[x][adjlist[x][MAX_NODES]++] = y;
        adjlist[y][adjlist[y][MAX_NODES]++] = x;
        /**
         * 這次結合了相鄰矩陣的快速取值優點與陣列的列舉速度
         * This combines the fast det. of adj matrices
         * and the speed of array traversal
         */
    }

    printf("From: ");
    scanf("%u", &from);
    printf("To: ");
    scanf("%u", &to);

    mindist[from] = 0; // 設定起點到起點的最短距離為0

    enqueue(&traverse_queue,
            (struct PriorityData){.node = from, .priority = 0});

    // BFS開始
    while (!empty(&traverse_queue)) {
        size_t node = dequeue(&traverse_queue).node; // 目前BFS的位置
        visited[node] = 1;
        for (size_t i = 0; i < adjlist[node][MAX_NODES]; i++) {
            size_t adjnode = adjlist[node][i];
            if (visited[adjnode])
                continue;

            // 未走訪的鄰邊
            int thisdist = mindist[node] + adjweight[node][adjnode];
            if (mindist[adjnode] < 0 || (mindist[adjnode] > thisdist)) {
                // 如果沒有最短距離，或者最短距離大於用這種方法走的距離時
                mindist[adjnode] = thisdist;
                previous[adjnode] = node;
            }
            enqueue(&traverse_queue,
                    (struct PriorityData){.node = adjnode,
                                          .priority = mindist[adjnode]});
        }
    }

    printf("best: ");
    size_t current = to;
    // 由最後一路走到前面
    while (current != from) {
        printf("%d<-", current);
        current = previous[current];
    }
    printf("%d", current);

    return 0;
}

3. A*演算法：A*演算法（A Star）與 Djikstra 的邏輯幾乎一模一樣，除了 A*演算法是一個已知演算法（Informed Algorithm）， 使用已知的情況調整優先順序，其中$p(v)=d(v)+h(v)$，$h(v)$通常為一個節點到終點的直線距離，因為在此優先順序越小越前面。 由上述可知，A*演算法對於圖的構造有相當依賴性，因此不是拓樸同構友善的。