数据结构学习笔记（八）图

---

1. 前言

本系列笔记基于 清华大学出版社的《数据结构：用面向对象方法与C++语言描述》第二版进行学习。

2. 概念

图分为有向图和无向图。顶点对<x,y>，有序图<x,y>和<y,x>是两条边，无序图<x,y>和<y,x>是一条边

3 图的存储结构

抽象类：

const int maxWeight = 100;
const int DefaultVertices = 30;

class Graph {
public:
    Graph(int sz = DefaultVertices);
    ~Graph();
    bool GraphEmpty()const {

        if (numEdges == 0) return true;
        else return false;
    }
    bool GraphFull()const {
        if (numVertices == maxVertices ||
            numEdges == maxVertices * (maxVertices - 1) / 2) return true;
        else return false;
    }
    int NumberOfVertices() { return numVertices; } // 返回当前顶点数
    int numberOfEdges() { return numEdges; }        // 返回边数
    virtual int getValue(int i);                                    // 取顶点i的值，不合理返回0
    virtual int getWeight(int v1, int v2);                   // 获取权值
    virtual int getFirstNeighbor(int v);                      // 取顶点v的第一个邻接顶点
    virtual int getNextNeighbor(int v, int w);           // 取邻接顶点w的下一个邻接顶点
    virtual bool insertVertex(const int vertex);         // 插入一个顶点vertex
    virtual bool insertEdge(int v1, int v2, int cost);      // 插入边(v1,v2)，权为cost
    virtual bool removeVertex(int v);                           // 删去顶点v和所有与相关联边
    virtual bool removeEdge(int v1, int v2);                // 删去边

protected:
    int maxVertices;
    int numEdges;
    int numVertices;
    int getVertexPos(int vertex);

};

3.1 图的邻接矩阵表示

简单来说就是用矩阵表示邻接关系

看图很好理解（大学考试还考过

这是带权的：

#include <iostream>

using namespace std;

const int maxWeight = 100;
const int DefaultVertices = 30;

class Graph {
public:
    Graph(int sz = DefaultVertices);
    ~Graph();
    bool GraphEmpty()const {

        if (numEdges == 0) return true;
        else return false;
    }
    bool GraphFull()const {
        if (numVertices == maxVertices ||
            numEdges == maxVertices * (maxVertices - 1) / 2) return true;
        else return false;
    }
    int NumberOfVertices() { return numVertices; } // 返回当前顶点数
    int numberOfEdges() { return numEdges; }        // 返回边数
    virtual int getValue(int i);                                    // 取顶点i的值，不合理返回0
    virtual int getWeight(int v1, int v2);                   // 获取权值
    virtual int getFirstNeighbor(int v);                      // 取顶点v的第一个邻接顶点
    virtual int getNextNeighbor(int v, int w);           // 取邻接顶点w的下一个邻接顶点
    virtual bool insertVertex(const int vertex);         // 插入一个顶点vertex
    virtual bool insertEdge(int v1, int v2, int cost);      // 插入边(v1,v2)，权为cost
    virtual bool removeVertex(int v);                           // 删去顶点v和所有与相关联边
    virtual bool removeEdge(int v1, int v2);                // 删去边

protected:
    int maxVertices;
    int numEdges;
    int numVertices;
    int getVertexPos(int vertex);

};

class Graphmtx :public Graph{
    friend istream& operator>>(istream& in, Graphmtx& G);
    friend ostream& operator<<(ostream& out, Graphmtx& G);
public:
    Graphmtx(int sz = DefaultVertices);         
    ~Graphmtx() { delete[]VerticesList; delete[]Edge; }
    int getValue(int i) {
        return i >= 0 && i <= numVertices ? VerticesList[i] : NULL;
    }
    int getWeigh(int v1, int v2) {
        return v1 != -1 && v2 != -1 ? Edge[v1][v2] : 0;
    }
    int getFirstNeighbor(int v);                    // 取v的第一个邻接顶点
    int getNextNeighbor(int v, int w);          // 取v的邻接顶点w的下一个邻接顶点
    bool insertVertex(const int vertex);        // 插入vertex
    bool insertEdge(int v1, int v2, int cost);      // 插入v(v1,v2),权值为cost
    bool removeVertex(int v);                           // 删除v和与其连接的所有v
    bool removeEdge(int v1, int v2);                // 在图中删去边(v1,v2)
private:
    int* VerticesList;
    int** Edge; // 邻接矩阵
    int getVertexPos(int vertex) {
        for (int i = 0; i < numVertices; i++)
            if (VerticesList[i] == vertex) return i;
        return -1;
    }
};


int main()
{
    std::cout << "Hello World!\n";
}

Graphmtx::Graphmtx(int sz)
{
    maxVertices = sz;
    numVertices = 0;
    numEdges = 0;
    int i;
    int j;
    VerticesList = new int[maxVertices];
    Edge = (int**) new int* [maxVertices];
    for (i = 0; i < maxVertices; i++) {
        Edge[i] = new int[maxVertices];
    }
    for (i = 0; i < maxVertices; i++)
        for (j = 0; j < maxVertices; j++)
            Edge[i][j] = (i == j) ? 0 : maxWeight;
}

int Graphmtx::getFirstNeighbor(int v)
{
    if (v != -1) {
        for (int col = 0; col < numVertices; col++) {
            if (Edge[v][col] > 0 && Edge[v][col] < maxWeight) return col;
        }
    }
    return -1;
}

int Graphmtx::getNextNeighbor(int v, int w)
{
    // 这个函数是为了获得v的已存在邻接顶点的下一个结点，
    // 就相当于屏蔽掉w结点和W之前的结点
    if (v != -1 && w != -1) {
        for (int col = w + 1; col <= numVertices; col++)
            if (Edge[v][col] > 0 && Edge[v][col] < maxWeight) return col;
    }
    return -1;
}

bool Graphmtx::insertVertex(const int vertex)
{
    if (numVertices == maxVertices) return false;
    VerticesList[numVertices++] = vertex;
    return true;
}

bool Graphmtx::insertEdge(int v1, int v2, int cost)
{
    if (v1 > -1 && v1<numVertices && v2>-1
        && v2 < numVertices && Edge[v1][v2] == maxWeight) {

        Edge[v1][v2] = Edge[v2][v1] = cost;
        numEdges++;
        return true;
    }
    return false;
}

bool Graphmtx::removeVertex(int v)
{
    if (v < 0 && v >= numVertices) return false;
    if (numVertices == 1) return false;
    int i, j;
    VerticesList[v] = VerticesList[numVertices - 1];
    for (i = 0; i < numVertices; i++) {                         // 减去与v相关联的边个数
        if (Edge[i][v] > 0 && Edge[i][v] < maxWeight) numEdges--;
       
    }
    for (i = 0; i < numVertices; i++) {
        Edge[i][v] = Edge[i][numVertices - 1];              // 用最后一列填补第v列，然后删除最后一列
    }
    numVertices--;
    for (j = 0; j < numVertices; j++) {
        Edge[v][j] = Edge[numVertices][j];                   // 用最后一行填补第v行，然后
    }
    return true;
}

bool Graphmtx::removeEdge(int v1, int v2)
{
    if (v1 > -1 && v1<numVertices && v2>-1 && v2 < numVertices
        && Edge[v1][v2] >0 && Edge[v1][v2] < maxWeight) {
        Edge[v1][v2] = Edge[v2][v1] = maxWeight;
        numEdges--;
        return true;
    }
    return false;
}

3.2 图的邻接表表示

也很好理解

#include <iostream>

using namespace std;

const int maxWeight = 100;
const int DefaultVertices = 30;

class Graph {
public:
    Graph(int sz = DefaultVertices);
    ~Graph();
    bool GraphEmpty()const {

        if (numEdges == 0) return true;
        else return false;
    }
    bool GraphFull()const {
        if (numVertices == maxVertices ||
            numEdges == maxVertices * (maxVertices - 1) / 2) return true;
        else return false;
    }
    int NumberOfVertices() { return numVertices; } // 返回当前顶点数
    int numberOfEdges() { return numEdges; }        // 返回边数
    virtual int getValue(int i);                                    // 取顶点i的值，不合理返回0
    virtual int getWeight(int v1, int v2);                   // 获取权值
    virtual int getFirstNeighbor(int v);                      // 取顶点v的第一个邻接顶点
    virtual int getNextNeighbor(int v, int w);           // 取邻接顶点w的下一个邻接顶点
    virtual bool insertVertex(const int vertex);         // 插入一个顶点vertex
    virtual bool insertEdge(int v1, int v2, int cost);      // 插入边(v1,v2)，权为cost
    virtual bool removeVertex(int v);                           // 删去顶点v和所有与相关联边
    virtual bool removeEdge(int v1, int v2);                // 删去边

protected:
    int maxVertices;
    int numEdges;
    int numVertices;
    int getVertexPos(int vertex);

};

struct Edge {
    int dest;   // 边的另一顶点位置
    int cost;   // 权值
    Edge* link;     // 下一条边链
    Edge(){}
    Edge(int num,int weight):dest(num),cost(weight),link(NULL){}
    bool operator != (Edge& R)const {
        return (dest != R.dest) ? true : false;
    }

};

struct Vertex {
    int data;
    Edge* adj;          // 边链表的头指针
};

class GraphLnk :public Graph {
public:
    GraphLnk(int sz = DefaultVertices);
    ~GraphLnk();
    int getValue(int i) {
        return (i > 0 && i < numVertices) ? NodeTable[i].data : 0;
    }
    int getWeight(int v1, int v2);
    bool insertVertex(const int& vertex);
    bool removeVertex(int v);
    bool insertEdge(int v1, int v2, int cost);
    bool removeEdge(int v1, int v2);
    int getFirstNeighbor(int v);
    int getNextNeighbor(int v, int w);      
private:
    Vertex* NodeTable;      // 顶点表
    int getVertexPos(const int vertex) {
        for (int i = 0; i < numVertices; i++)
            if (NodeTable[i].data == vertex) return i;
        return -1;
    }
};

int main()
{
    std::cout << "Hello World!\n";
}

GraphLnk::GraphLnk(int sz)
{
    maxVertices = sz;
    numVertices = 0;
    numEdges = 0;
    NodeTable = new Vertex[maxVertices];
    if (NodeTable == NULL) { cout << "error when allocate memory!"; exit(1); }
    for (int i = 0; i < maxVertices; i++)
        NodeTable[i].adj = NULL;
}

GraphLnk::~GraphLnk()
{
    for (int i = 0; i < numVertices; i++) {
        Edge* p = NodeTable[i].adj;
        while (p != NULL) {
            NodeTable[i].adj = p->link;
            delete p;
            p = NodeTable[i].adj;
        }
        delete[]NodeTable;
    }
}

int GraphLnk::getWeight(int v1, int v2)
{
    if (v1 != -1 && v2 != -1) {
        Edge* p = NodeTable[v1].adj;
        while (p != NULL && p->dest != v2)
            p = p->link;
        if (p != NULL) return p->cost;
    }
    return 0;
}

bool GraphLnk::insertVertex(const int& vertex)
{
    if (numVertices == maxVertices) return false;
    NodeTable[numVertices].data = vertex;
    numVertices++;
        return true;
}

bool GraphLnk::removeVertex(int v)
{
    if (numVertices == 1 || v < 0 || v >= numVertices) return false;

    Edge* p, * s, * t;
    int i, k;
    while (NodeTable[v].adj != NULL) {
        p = NodeTable[v].adj;       // 找到目标结点
        k = p->dest;
        s = NodeTable[k].adj;
        t = NULL;
        while (s != NULL && s->dest != v) {         // 找到对称结点
            t = s;
            s = s->link;
        }

        if (s != NULL) {
            if (t == NULL) NodeTable[k].adj = s->link;  // 删除对称存放的边结点
            else t->link = s->link;
            delete s;
        }
        NodeTable[v].adj = p->link;
        delete p;
        numEdges--;

    }

    numVertices--;
    NodeTable[v].data = NodeTable[numVertices].data;
    p = NodeTable[v].adj = NodeTable[numVertices].adj;
    while (p != NULL) {
        s = NodeTable[p->dest].adj;
        while (s != NULL)
            if (s->dest == numVertices) { s->dest = v; break; }
            else s = s->link;
    }


    return true;
}

bool GraphLnk::insertEdge(int v1, int v2, int cost)
{
    if (v1 >= 0 && v1 < numVertices && v2 >= 0 && v2 < numVertices) {
        Edge* q;
        Edge* p = NodeTable[v1].adj;           // 找到v1
        while (p != NULL && p->dest != v2)
            p = p->link;                        // 需按照邻接顶点v2
        if (p != NULL) return false;
        p = new Edge;
        q = new Edge;
        // 创建新结点v2，连接到v1的表
        p->dest = v2;
        p->cost = cost;                                     
        p->link = NodeTable[v1].adj;            // 找到v2

        NodeTable[v1].adj = p;                          // 连接到v2的表
        q->dest = v1;
        q->cost = cost;
        q->link = NodeTable[v2].adj;
        NodeTable[v2].adj = q;
        numEdges++;             // 存在表头
        return true;
    }
    return false;
}

bool GraphLnk::removeEdge(int v1, int v2)
{
    if (v1 != -1 && v2 != -1) {
        Edge* p = NodeTable[v1].adj;
        Edge* q = NULL;
        Edge* s = p;
        while (p != NULL && p->dest != v2) {
            q = p;
            p = p->link;            // 找到被删的边
        }
        if (p != NULL) {
            if (p == s) NodeTable[v1].adj = p->link;        // 被删边是首结点
            else q->link = p->link;                                     // 重新连接
            delete p;
        }
        else return false;
        p = NodeTable[v2].adj;              // 删除v2对应的边
        q = NULL;
        s = p;
        while (p->dest != v1) {
            q = p;
            p = p->link;
        }

        if (p == s) NodeTable[v2].adj = p->link;
        else q->link = p->link;
        delete p;
        return true;
    }


    return false;
}

int GraphLnk::getFirstNeighbor(int v)
{
    if (v != -1) {
        Edge* p = NodeTable[v].adj;
        if (p != NULL) return p->dest;
    }

    return -1;
}

int GraphLnk::getNextNeighbor(int v, int w)
{
    if (v != -1) {
        Edge* p = NodeTable[v].adj;
        while (p != NULL && p->dest != w) p = p->link;
        if (p != NULL && p->link != NULL)
            return p->link->dest;
    }
    return -1;
}

搞不懂可以取看单链表

4. 图的遍历

给每个顶点加一个标志位visited,避免重复访问

4.1 深度优先搜索

一条路走到底，如果走不动，就返回上一个状态（结点）搜索这个状态的其他结点，如果邻接结点都被访问过了，再返回上一个节点进行搜索

void DFS(Graph& G, int v, bool visited[]) {
    cout << G.getValue(v) <<endl;           
    visited[v] = true;                                          
    int w = G.getFirstNeighbor(v);              // 前三部处理开始，也就是顶点的V
    while (w != -1) {                                       
        if (visited[w] == false) DFS(G, w, visited);        // 如果没被访问过，则对这个顶点进行广度搜索
        w = G.getNextNeighbor(v, w);        // 如果被访问过，则寻找下一个邻接顶点，然后循环
    }
}

void DFS(Graph& G, const int v) {
    // 从顶点v出发，对图G进行深度优先遍历
    int loc;
    int n = G.NumberOfVertices();
    bool* visited = new bool[n];
    for (int i = 0; i < n; i++) visited[i] = false;
    loc = G.getVertexPos(v);
    DFS(G, loc, visited);
    delete[]visited;
}

4.2 广度优先遍历

广度优先相当于一下子把这个结点的所有邻接结点都访问了，然后找邻接结点的结点

void BFS(Graph& G, const int v) {
    int w, n = G.NumberOfVertices();
    bool* visited = new bool[n];
    for (int i = 0; i < n; i++) visited[i] = false;
    int loc = G.getVertexPos(v);
    cout << G.getValue(loc) << endl;            // 获得首个结点
    visited[loc] = true;
    Queue Q;
    Q.EnQueue(loc);                                             // 顶点进队列
    while (!Q.IsEmpty()) {
        Q.DeQueue(loc);
        w = G.getFirstNeighbor(loc);
        while (w != -1) {
            if (visited[w] == false) {
                cout << G.getValue(w) << "endl";
                visited[w] = true;
                Q.EnQueue(w);
            }
            w = G.getNextNeighbor(loc, w);

        }
        delete[]visited;

    }

}

5 连通分量

顶点访问他结点，最多结点的路径上的结点构成连通分量。

void Components(Graph& G) {

    int n = G.NumberOfVertices();
    bool* visited = new bool[n];
    for (int i = 0; i < n; i++) visited[i] = false;
    for(int i=0;i<n;i++)
        if (visited[i] == false) {
            DFS(G, i, visited);
            OutputNewComponent();           // 输出连通分量
        }
    delete[] visited;

}

用DFS遍历的话，很容易得到连通分量。

6 最小生成树

用DFS和BFS访问所有结点产生的边。树不能有环
图的生成树删去任何一条边，生成树就不再连接，引入新边后能恰好生成一个回路。对带权图而言，不同生成树所带有的权值不同。

6.1 Kruskal 算法

就选权值最小的边，直到边=结点数-1

6.2 实现

void Kruskal(Graph& G, MinSpanTree& MST) {
    MSTEdgeNode ed;
    int u, v, count;            // 边界点辅助单元
    int n = G.NumberOfVertices();       // 顶点数
    int m = G.NumberOfEdges();          // 边数
    MinHeap H(m);                               // 最小堆
    UFSet F(n);                                     // 并查集
    for(u = 0;u>n;i++)
        for(v = u+1;v<n;v++)
            if (G.getWeight(u, v) != maxValue) {
                ed.tail = u;
                ed.head = v;
                ed.key = G.getWeight(u, v);
                H.Insert(ed);               // 插入堆
            }
    count = 1; // 最小生成树加入边数计数
    while (count < n) {                 // 取n-1条边
        H.RemoveMin(ed);
        u = F.Find(ed.tail);
        v = F.Find(ed.head);            // 找到两个结点
        if (u != v) {
            F.Union(u, v);                  // 连接两节点
            MST.Insert(ed);             // 存入最小生成树
            count++;
        }

    }
}

6.2 Prim 算法

书上讲的晦涩难懂

这样一个图，求他最小生成树，首先任选一个结点，这里选v0，
然后看连接他的结点，v1,v2,v3，找到最小权值的边<v0,v3>
然后把v0,v3看作一个整体，

查看连接到这个集合的结点，v1,v2,v4,v5
发现有两个最小的边v2,v5，我们任选一边（得出最小生成树可能不止一棵）
这里选v2，再把v2加入集合中

查找到最小的权值边为<v2,v5>
加入集合
依次类推

最终得到这样一棵树
但刚才有共同权值的，我们再算出另一棵树

void Prim(Graph& G, const int u0, MinSpanTree& MST) {

    MSTEdgeNode ed;
    int i, u, v, count;
    int n = G.NumverOfVertices();       // 顶点数
    int m = G.NumberOfEdges();        // 边数
    int u = G.getVertexPos(u0);           // 起始顶点号u
    MinHeap H(m);
    bool Vmst = new bool[n];
    for (i = 0; i < n; i++) Vmst[i] = false;
    Vmst[u] = true;
    count = 1;
    do {
        v = G.getFirstNeighbor(u);
        while (v != -1) {
            if (Vmst[v] == false) {
                ed.tail = u;
                ed.head = v;
                ed.key = G.geiWeight(u, v);
                H.Insert(ed);                           // 存所有边到最小堆
            }
            v = G.getNextNeighbor(u, v);
        }
        while (H.IsEmpty() == false && count < n) {
            H.RemoveMin(ed);                // 找到权值最小的边
            if (Vmst[ed.head] == false) {
                MST.Insert(ed);
                u = ed.head;
                Vmst[u] = true;
                count++;
                break;


            }

        }
    } while (count < n);

}

7 最短路径

像各城市一样，找到一个城市到另一个城市的最短路径。

7.1 dijkstra算法

以下部分出自B站
Dijkstra算法手动模拟流程


首先准备一个表，然后我们选取第一个点v1

看他的出度，是<1,2> = 10， <1,5> = 5。记录到表中的第一轮

和prim算法一样，选取离v1最短的v5，划到已选取的范围中

观察出度，并忽略到之前已经看到过的出度的那条边,并且计算到点的距离时要加上上一轮选的结点5的权值3
此时连接到圈内的出度：到v2 = 5+3 =8，到v3=5+9=14，到v4=5+2=7，并记录到表中，如果比上次记录的要短，则更新，本轮有没有更新

选择最短的点v4，加入到圈中

此时看出度，因为已经选了v4，所以无法从已经选择的路径1->5->4 到达2，所以本轮的到v2的距离不变，保持上一轮的搜索结果，到达v3的最短距离是v3 = 7+6=13，比上一轮的的距离要短，记录到表中

选择距离最短的点v2，加入到圈中

看没看过的出度，就是1，所以到v3的记录就是v3 = 8+1=9

最后遍历完，简单就是，谁没进圈，就看圈到这个点的距离，和prim算法很像

书上的实现，真的跟那啥一样

void ShortestPath(Graph& G, int v, int dist[], int path[]) {
    int n = G.NumberOfVertices();
    bool* S = new bool[n];                  // 判断是否已经进圈
    int i, j, k;
    int w, min;
    for (i = 0; i < n; i++) {
        dist[i] = G.getWeight(v, i);        // 数组初始化，先存权值
        S[i] = false;                                           // 所有结点都不在圈内
        if (i != v && dist[i] < maxWeight) path[i] = v;     // 存最短路径
        else path[i] = -1;
    }
    S[v] = true;
    dist[v] = 0;                // 顶点v先进
    for (i = 0; i < n - 1; i++) {
        min = maxWeight;
        int u = v;              // 选不在圈S中的最短路径的顶点u
        for (j = 0; j < n; j++) {
            if (S[j] == false && dist[j] < min) { u = j; min = dist[j]; }           // 循环结点，找到最短路径的顶点u
            S[u] = true;
            for (k = 0; k < n; k++) {           // 修改
                w = G.getValue(u, k);
                if (S[k] == false && w < maxWeight && dist[u] + w < dist[k]) {
                    dist[k] = dist[u] + w;
                    path[k] = u;                        // 如果要短一些，就改表里的值
                }

        }
        }

    }

}

读取，看这些代码图一乐就行，写得真的不是很尽人意

void printShortestPath(Graph& G, int v, int dist[], int path[]) {
    cout << "从顶点" << G.getValue(v) << "到其他顶点的最短路径为:" << endl;
    int i, j, k, n = G.NumberOfVertices();
    int* d = new int[n];
    for(i = 0;i<n;i++)
        if (i != v) {
            j = i; k = 0;
            while (j != v) { d[k++] = j; j = path[j]; }
            cout << "顶点" << G.getValue(I) << "的最短路径为:" << G.getValue(v);
            while (k > 0) {
                cout << G.getValue(d[--k]) << "";
                cout << "最短路径长度" << dist[i] << endl;
            }

            delete[]d;

        }

}

8 用顶点表示活动的网络（AOV)

如要学c3，必须先学C1C2


删掉没有直接前驱的顶点，和该顶点有的边。然后找下一个没有直接前驱的顶点

求拓补排序

实现方法还是挺简单的，直接看代码

void TopologicalSort(Graph& G) {
    int i, j, w, v;
    int top = -1;
    int n = G.NumberOfVertices();                          
    int* count = new int[n];                                    // 记录每个结点的入度
    for (i = 0; i < n; i++) count[i] = 0;
    cin >> i >> j;                                                      // 输入一条边
    while (i > -1 && i < n && j < -1 && j < n) {
        G.insertEdge(i, j);
        count[j]++;
        cin >> i >> j;
    }
    for(i = 0;i<n;i++)
        if (count[i] == 0) { count[i] = top; top = i; }             // 入度为0的顶点进栈
    for (i = 0; i < n; i++) {
        if (top == -1)
        {
            cout << "有回路" << endl;
            return;
        }
        else {
            v = top;
            top = count[top];
            cout << G.getValue(v) << "" << endl;            // 输出
            w = G.getFirstNeighbor(v);                                  // 找到入度为0的结点的首个邻接结点
            while (w!=-1)
            {
                if (--count[w] == 0)      // 邻接顶点入度-1
                {
                    count[w] = top;
                    top = w;                            // 入度为0，入栈
                }
                w = G.getNextNeighbor(v, w);    // 找到下一个
            }


        }
    }

9 用边表示活动的网络（AOE)

例子是，有一个工程，都是从0开始，做不同的事情，上图中，1，2，3是可以一起做的事情，但如果要从结点4往下做，则需要1，2都做完才能到达4，随后在做其他事情
因此，完成整个工程所需要的时间，是这条路径上所有活动的持续时间之和，路径最长的路径就是关键路径。
这一段从B站学
ＡＯＥ网求关键路径，包含所有事件和活动的最早或最晚发生时间

首先知道两个概念,活动和事件,活动是边,事件是结点

四个概念

先提出怎么算,然后依次来算

9.1 VE 事件最早发生时间

首先算Ve(),就是事件最早发生时间,
首先看结点v1原点,他前驱结点+路径=0,填入表中

看v2,他直接前驱v1的ve+路径a1 = 0+3 = 3;填入表中

看v3,其前驱结点v1的ve0+路径a2 = 0+2 = 2,填入表中

看v4,他前驱结点有两个,分别是v2,v3.此时v4的ve可以从两个地方算
第一条v2的ve+ a3 = 3+2 = 5
第二条v3的ve+a5 = 2+4=6
我们取最大的值6,填入表中,并舍弃a3

然后计算v5,前驱结点v2的ve+a4 = 3+3 =6,填入

最后算v6,和v4一样,有三条路,依次算出取最大的那个
v5的Ve + a8 = 6+1 =7;
v4的ve + a7 =6+2 =8;
v3的ve + a6 = 2+3 =5;
取8,并舍弃a8和a6

所以我们得出的关键路径:

看删去的边,连不到最终结点v6的就不要管,只管连得到的
v1->v3->v4->v6
这就是关键路径

9.2 VL 事件最晚发生时间

后继结点的V(l)-路径的最小值
我们要从ve取最后结点的值


v6结点的vl 等于v6结点的ve,所以我们已知V6的vl=8,填入表中

看到v6的路径有3条,我们分别算出v4,v5的各个的值
v4的 = vl(v6) - a7 = 8-2 = 6
v5的 = vl(v6) -a8 = 8-1 =7

我们算v3的时候,发现他有两个后继结点,我们分别算出

1. vl(4) - a5 = 6-4 =2
2. vl(6) - a6 = 8-3 =5
   我们取最小的2填入
   
   算v2
3. vl(4) - a3 = 6-2 =4;
4. vl(5) - a4 = 7-3 = 4;
   所以vl(2) = 4

v1 = 0肯定的

9.3 E()活动的最早发生时间

e(i) = ve(i) 出度结点

a1的出度结点为v1,所以e(1) = ve(1) = 0
a2的出度节点v1,所以e(2) = ve(2) = 0
同理 a3 =ae(v2) = 3,同理我们直接写完

9.4 L()活动的最晚发生时间

vl() - 路径,入度结点的vl()值

a1的入度结点时v2,然后求出a1的L()的值: VL(V2) - a1的路径长度 = 4-3 = 1填入

a2 = vl(v3) -2 =2-2 =0

a3 = vl(v4)-a3 = 6-2 = 4
a4 = vl(v5) - 3 = 7-3 =4
a5 = vl(v4) - a5 = 6-4 =2
a6= vl(v6) - a6 = 8-3 =5
a7 = vl(v6) - a7 = 8-2=6
a8 = vl(v6) - a8 = 8-1 = 7

void CriticalPath(Graph& G) {
    int i, j, k;
    int Ae, Al, w;
    int n = G.NumberOfVertices();
    int* Ve = new int[n];
    int* Vl = new int[n];
    for (i = 0; i < n; i++) Ve[i] = 0;
    for (i = 0; i < n; i++) {
        j = G.getFirstNeighbor(i);
        while (j!=-1)
        {
            w = G.getWeight(i, j);
            if (Ve[i] + w > Ve[j]) Ve[j] = Ve[i] + w;    // ve = 前驱结点的ve+路径长度，去最大值
                                                                            // 如果算出来的ve更大，就填更大的数
            j = G.getNextNeighbor(i, j);        // 找到下一个结点
        }
    }
    Vl[n - 1] = Ve[n - 1];          // 汇点的  Vl = VE
    for (j = n - 2; j > 0; j--) {
        k = G.getFirstNeighbor(j);
        while (k != -1) {
            w = G.getWeight(j, k);
            if (Vl[k] - w < Vl[j]) Vl[j] = Vl[k] - w;           // vl = 后继节点的vl - 路径长度，取最小值
            k = G.getNextNeighbor(j, k);
        }
    }
    for (i = 0; i < n; i++) {
        j = G.getFirstNeighbor(i);
        while (j!= -1)
        {
            Ae = Ve[i];
            Al = Vl[k] - G.getWeight(i, j);         // 入度的vl（）- 路径长度
            if (Al == Ae) cout << "<" << G.getValue(i) << "," << G.getValue(j) << ">" << "是关键活动" << endl;
            j = G.getNextNeighbor(i, j);
        }



    }
    delete[] Ve;
    delete[] Vl;
}