頂點(Vertex)

有向邊、無向邊

簡單圖形(Simple Graph)：沒有從頂點連到自己的邊，或同一條邊不重複出現

無向完全圖：任意兩頂點都存在著一條邊，共n(n-1)/2條邊

有向完全圖：任意兩頂點都存在方向互為相反的兩條邊，共n(n-1)條邊

權 -> 加權的圖形通常稱為網

度(內分支度、外分支度)

連通：兩頂點之間存在路徑；若任意兩頂點皆為連通的 -> 連通圖；有向稱為強連通圖

展開樹：無向圖形連通且n個頂點n-1條邊；有向圖中一頂點內分支度為0，其餘頂點內分支度為1 -> 有向樹

儲存結構：

• 鄰接矩陣(Adjacency Matrix)：一維陣列儲存圖形中的頂點；二維陣列儲存圖形中邊的資訊；無向圖是一個對稱矩陣

typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100
#define INFINITY 65535
typedef struct MGraph {
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numVertexes, numEdges;
} MGraph;

對於邊數較少的圖形，浪費空間

• 鄰接串列(Adjacency List)：一維陣列儲存圖形中的頂點，串列儲存頂點的第一個鄰接點(無向圖)；有向圖為外邊集合和內邊集合

typedef char VertexType;
typedef int EdgeType;

typedef struct EdgeNode {
    int adjvex;
    EdgeType weight;
    struct EdgeNode *next;
} EdgeNode;

typedef struct VertexNode {
    VertexType data;
    EdgeNode *firstedge;
} VertexNode, AdjList[MAXVEX]

typedef struct GraphAdjList {
    AdjList adjList;
    int numVertexes, numEdges;
} GraphAdjList;

對於有向圖，只能了解內分支度或外分支度

• 十字鏈結串列(有向圖應用中優秀的儲存結構)：一維陣列儲存圖形中的頂點，其他如下

// |data|firstin|firstout|
// firstin: 內邊集合的首指標
// firstout: 外邊集合的首指標

// |tailvex|headvex|headlink|taillink|
// tailvex: 邊起點編號
// headvex: 邊終點編號
// headlink: 內邊集合，指向與終點相同的下一條邊
// taillink: 外邊集合，指向與起點相同的下一條邊

鄰接串列要刪除邊，要操作兩個邊集合節點

• 鄰接多重鏈結串列(無向圖應用中優秀的儲存結構)：

// |ivex|ilink|jvex|jlink|
// ivex和jvex構成一條邊
// ilink指向依附頂點ivex的下一條邊、jlink指向依附頂點jvex的下一條邊

• 邊集陣列：一維陣列儲存圖形中的頂點，一維陣列儲存邊的資訊

適合對邊依次進行處理，不適合對頂點做操作

// |begin|end|weight|
// begin: 邊起點編號
// end: 邊終點編號
// weight: 權值

• 深度優先走訪(Depth-First Search)

typedef int Boolean;
Boolean visited[MAX];

// ********** 鄰接矩陣 **********
void DFS(MGraph G, int i) {
    ing j;
    visited[i] = True;
    printf("%c ", G.vex[i]);
    for (j = 0; j < G.numVertexes; j++)
        if (G.arc[i][j] == 1 && !visited[j])
            DFS(G, j);
}

void DFSTraverse(MGraph G) {
    int i;
    for (i = 0; i < G.numVertexes; i++)
        visited[i] = False;
    for (i = 0; i < G.numVertexes; i++)
        if (!visited[i])
            DFS(G, i);
}
// ******************************

// ********** 鄰接串列 **********
void DFS(GraphAdkList GL, int i) {
    EdgeNode *p;
    visited[i] = True;
    printf("%c ", GL->adjList[i].data);
    p = GL->adjList[i].firstedge;
    while (p) {
        if (!visited[p->adjvex])
            DFS(GL, p->adjvex);
        p = p->next;
    }
}

void DFSTraverse(GraphAdkList GL) {
    int i;
    for (i = 0; i < GL->numVertexes; i++)
        visited[i] = False;
    for (i = 0; i < GL->numVertexes; i++)
        if (!visited[i])
            DFS(GL, i);
}
// ******************************

• 廣度優先走訪(Breadth-First Search)

// ********** 鄰接矩陣 **********
void BFSTraverse(MGraph G) {
    int i, j;
    Queue Q;
    for (i = 0; i < G.numVertexes; i++)
        visited[i] = False;
    InitQueue(&Q);
    for (i = 0; i < G.numVertexes; i++) {
        if (!visited[i]) {
            visited[i] = True;
            printf("%c ", G.vexs[i]);
            EnQueue(&Q, i);
            while (!QueueEmpty(Q)) {
                DeQueue(&Q, &i);
                for (j = 0; j < G.numVertexes; j++) {
                    if (G.arc[i][j] && !visited[j]) {
                        visited[j] = True;
                        printf("%c ", G.vexs[j]);
                        EnQueue(&Q, j);
                    }
                }
            }
        }
    }
}
// ******************************

// ********** 鄰接串列 **********
void BFSTraverse(GraphAdkList GL) {
    int i;
    EdgeNode *p;
    Queue Q;
    for (i = 0; i < GL->numVertexes; i++)
        visited[i] = False;
    InitQueue(&Q);
    for (i = 0; i < GL->numVertexes; i++) {
        if (!visited[i]) {
            visited[i] = True;
            printf("%c ", GL->adjList[i].data);
            EnQueue(&Q, i);
            while (!QueueEmpty(Q)) {
                DeQueue(&Q, &i);
                p = GL->adjList[i].firstedge;
                while (p) {
                    if (!visited[p->adjvex]) {
                        visited[p->adjvex] = True;
                        printf("%c ", GL->adjList[p->adjvex].data);
                        EnQueue(&Q, p->adjvex);
                    }
                    p = p->next;
                }
            }
        }
    }
}
// ******************************

• 最小展開樹(Minimum Cost Spanning Tree)

普裡姆(Prim)演算法

void MiniSpantree_Prim(MGraph G) {
    int min, i, j, k;
    int adjvex[MAXVEX];
    int lowcost[MAXVEX];

    for (i = 1; i < G.numVertexes; i++) {
        lowcost[i] = G.arc[0][i];
        adjvex[i] = 0;
    }

    for (i = 1; i < G.numVertexes; i++) {
        min = INFINITY;
        j = 1; k = 0;
        while (j < G.numVertexes) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
            j++;
        }
        printf("(%d, %d)", adjvex[k], k);
        lowcost[k] = 0;
        for (j = 1; j < G.numVertexes; j++) {
            if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;
            }
        }
    }
}

克魯斯卡爾(Kruskal)演算法

// 要有由小排到大的邊集合陣列
int Find(int *parent, int f) {
    while (parent[f] > 0)
        f = parent[f];
    return f;
}

void MiniSpantree_Kruskal(MGraph G) {
    int i, n, m;
    Edge edges[MAXEDGE];
    int parent[MAXVEX];
    for (i = 0; i < G.numVertexes; i++)
        parent[i] = 0;
    for (i = 0; i < G.numEdge; i++) {
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        if (n != m) {
            parent[n] = m;
            printf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
}

• 最短路徑

迪傑斯特拉(Dijkstra)演算法

void ShortestPath_Dijkstra(MGraph G, int v0, Pathmatrix *P, ShortPathTable *D) {
    // D用來以目前找到的最短路徑對其他頂點進行計算 (最後為v0到各頂點的最短路徑)
    // P紀錄前驅者
    int v, w, k, min;
    int final[MAXVEX];
    for (v = 0; v < G.numVertexes; v++) {
        final[v] = 0;
        (*D)[v] = G.matrix[v0][v];
        (*p)[v] = 0;
    }
    (*D)[v0] = 0;
    final[v0] = 1;
    for (v = 1; v < G.numVertexes; v++) {
        min = INFINITY; // 尋找離v0最近的頂點
        for (w = 0; w < G.numVertexes; w++) {
            if (!final[w] && (*D)[w] < min) {
                k = w;
                min = (*D)[w];
                }
        }
        final[k] = 1; // 修正當前最短路徑及距離
        for (w = 0; w < G.numVertexes; w++) {
            if (!final[w] && (min + G.matrix[k][w] < (*D)[w])) {
                (*D)[w] = min + G.matrix[k][w];
                (*P)[w] = k;
            }
        }
    }
}

佛洛德(Floyd)演算法

// D^-1: 網圖的鄰接矩陣
// P^-1: 儲存路徑

void ShortestPath_Floyd(MGraph G, Pathmatrix *P, ShortPathTable) {
    int v, w, k;
    for (v = 0;v < G.numVertexes; ++v) {
        for (w = 0; w < G.numVertexes; ++w) {
            (*D)[v][w] = G.matrix[v][w];
            (*P)[v][w] = w;
        }
    }
    for (k = 0; k < G.numVertexes; ++k) {
        for (v = 0; v < G.numVertexes; ++v) {
            for (w = 0; w < G.numVertexes; ++w) {
                if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {
                    (*D)[v][w] = (*D)[v][k] + (*D)[k][w];
                    (*P)[v][w] = (*P)[v][k];
                }
            }
        }
    }
}

// 最短路徑顯示
for (v = 0; v < G.numVertexes; ++v) {
    for (w = v + 1; w < G.numVertexes; w++) {
        printf("v%d-v%d weight: %d ", v, w, D[v][w]);
        k = P[v][w];
        printf(" path: %d", v);
        while(k != w) {
            printf(" -> %d", k);
            k = P[k][w];
        }
        printf(" -> %d\n", w);
    }
    printf("\n");
}

• 拓樸排序(Topological Sorting)：對一個有向圖架構拓樸序列過程

AOV網路(Activity On Vertex Network)：圖中的邊表示活動之間存在某種制約關係

設G=(V, E)是一個具有n個頂點的有向圖，若Vi到Vj有一條路徑，則在頂點序列，頂點Vi必定在頂點Vj之前，這樣的頂點序列稱為拓樸序列；若頂點輸出數少了，則代表這個網圖有環路存在

typedef struct EdgeNode {
    int adjvex;
    int weight;
    struct EdgeNode *next;
} EdgeNode;

// |in|data|firstedge|
typedef struct VertexNode {
    int in;
    int data;
    EdgeNode *firstedge;
} VertexNode, AdjList[MAXVEX];

typedef struct {
    AdjList adjList;
    int numVertexes, numEdge;
} graphAdjList, *GraphAdjList;

Status TopologicalSort(GraphAdjList GL) {
    EdgeNode *e;
    int i = 0, gettop, k;
    int top = 0;
    int count = 0;
    int *stack;
    stack = (int *)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++)
        if (GL->adjList[i].in == 0)
            stack[++top] = i;
    while (top != 0) {
        gettop = stack[top--];
        printf("%d -> ", GL->adjList[gettop].data);
        count++;
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
             k = e->adjvex;
             if (!(--GL->adjList[k].in))
                 stack[++top] = k;
        }
    }
    if (count < GL->numVertexes)
        return ERROR;
    else
        return OK;
}

• 關鍵路徑

AOE網路(Activity On Edge Network)：沒有內邊的頂點稱為起點，沒有外邊的頂點稱為終點(只有一個起點一個終點)

從起點到終點具有最大長度的路徑稱為關鍵路徑

int *etv, *ltv; // 事件最早發生和最晚發生的時間陣列 
int *stack2; // 拓樸序列堆疊
int top2; // stack2的指標

Status TopologicalSort(GraphAdjList GL) {
    EdgeNode *e;
    int i = 0, gettop, k;
    int top = 0;
    int count = 0;
    int *stack;
    stack = (int *)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++)
        if (GL->adjList[i].in == 0)
            stack[++top] = i;
    top2 = 0;
    etv = (int *)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++)
        etv[i] = 0;
    stack2 = (int *)malloc(GL->numVertexes * sizeof(int));
    while (top != 0) {
        gettop = stack[top--];
        count++;
        stack2[++top2] = gettop;
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
             k = e->adjvex;
             if (!(--GL->adjList[k].in))
                 stack[++top] = k;
             if ((etv[gettop] + e->weight) > etv[k])
                 etv[k] = etv[gettop] + e->weight;
        }
    }
    if (count < GL->numVertexes)
        return ERROR;
    else
        return OK;

}

void CriticalPath(GraphAdjList GL) {
    EdgeNode *e;
    int i, gettop, k, j;
    int ete, lte;
    TopologicalSort(GL);
    ltv = (int *)malloc(GL->numVertexes * sizeof(int));
    for (i = 0; i < GL->numVertexes; i++)
        ltv[i] = etv[GL->numVertexes - 1];
    while (top2 != 0) {
        gettop = stack2[top2--];
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            k = e->adjList;
            if(ltv[k] - e->weight < ltv[gettop])
                ltv[gettop] = ltv[k] - e->weight;
        }
    }
    for (j = 0; j < GL->numVertexes; j++) {
        for (e = GL->adjList[gettop].firstedge; e; e = e->next) {
            k = e->adjvex;
            ete = etv[j];
            lte = ltv[k] - e->weight;
            if (ete == lte)
                printf("<v%d, v%d> length: %d, ",
                    GL->adjList[j].data,
                    GL->adjList[k].data,
                    e->weight);
        }
    }
}