Longest Path

发表于 更新于

最近遇到了一道算法题，求有向无环图（DAG）的最长路径，在这里记录下我的思路和解法。

首先是图的定义，这里根据严蔚敏的《数据结构》来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define MAX_VERTEX_NUM 10
typedef char VertexType;

typedef struct ArcNode{     // 边表结点
    int adjvex;
    struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode{      // 顶点表结点
    VertexType data;
    ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct{           // 邻接表
    AdjList Vertices;
    int vexnum, arcnum;
}ALGraph;

再来大致阐述一下整体的算法思想：

由于拓扑排序序列中的结点前后有序，不会出现后面结点有指向前面结点的路径这类问题。那么利用拓扑序列，检查两两结点之间的路径长度，若用 maxPath(i) 表示最长路径，weight(i,j)表示结点间的权值，则有

1
maxPath(v) = max{maxPath(v), weight(k,v)+maxPath(k)}

最后比较 maxPath(i) 取最大值即可得解。

于是相应写出代码。首先是拓扑排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int indegree[MAX_VERTEX_SIZE];

bool TopologicalSort(ALGraph G) { // 若图形成环，则无拓扑序列，输出false
    ArcNode *p;
    for (int i = 0; i < G.vexnum; i++) {
        for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
            indegree[p->adjvex]++; // 入度数组初始化
        }
    }

    Stack s;
    InitStack(s);
    for (int i = 0; i < G.vexnum; i++) {
        if (indegree[i] == 0) Push(s, i); // 选择入度为零的顶点
    }
    int count = 0; // 记录已输出数目
    int res[G.vexnum];
    while (!StackEmpty(s)) {
        Pop(s, i);
        res[count++] = i;
        for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
            int v = p->adjvex;
            indegree[v]--; // 邻接顶点的入度相应减一
            if (indegree[v] == 0) Push(s, v); // 录入入度为零的顶点
        }
    }
    return count == G.vexnum - 1; // 确认全部顶点是否进入序列中
}

在上面的代码中可得到拓扑序列res[]，之后再获得最大路径如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int GetMaxPath(ALGraph G) {
    int MaxPath[G.vexnum];
    for (int i = 1; i < G.vexnum; i++) {
        int v2 = res[i];
        for (int j = 0; j < i; j++) {
            int v1 = res[j];
            for (ArcNode *p = G.vertices[v1].firstarc; p; p = p->nextarc) {
                if (p->adjvex == v2) { // v1和v2相连
                    int m = MaxPath[v1] + p->weight;
                    MaxPath[v2] = m > MaxPath[v2] ? m : MaxPath[v2]; // 取较大路径
                }
            }
        }
    }

    int max = -1;
    for (int i = 0; i < G.vexnum; i++) {
        if (MaxPath[i] > max) max = MaxPath[i];
    }
    return max;
}