图算法

本文主要介绍Floyd、Dijkstra、Prim等图算法的代码实现

邻接表

//  节点
struct edge{
    int to;
    int cost;
};
vector<edge> graph[MAX];
int v, e;
void build() {
    // 顶点数，边数
    cin >> v >> e;
    for (int i = 0; i < e; ++i ) {
        int to;
        int from;
        int cost;
        cin >> from >> to >> cost;
        graph[from].push_back({to, cost});
        // 有向图，则是单向 没有to-->from链路
        graph[to].push_back({from, cost});
    }
}

邻接矩阵

vector<vector<int>> graph(MAX, vector<int>(MAX, INF));
int v, e;
void build() {
    cin >> v >> e;
    for (int i = 0; i < e; ++i) {
        // 对角线初始化
        graph[i][i] = 0;
        int to,
            from,
            cost;
        cin >> from >> to >> cost;
        graph[from][to] = cost;
        // 有向图 
        graph[to][from] = cost;
    }
}

Floyd算法

Floyd算法的核心在于

• 想求start ===> finish的最小距离
• 考虑借助中间节点k来实现start ===> k ===> finish间接抵达
• 此时cost[start][finish] = cost[start][k] + cost[k][finish]（cost[i][j]以表示i ===> j的花费）
• 遍历所有节点，找出最小权值和

//graph：邻接矩阵
// INF：
void  Floyd() {
    for (int k = 0; k < v; ++k) {
        for (int i = 0; i < v;++i) {
            for (int j = 0; j < v;++j) {
                if(graph[i][k] < INF && graph[k][j] < INF) { //节点均畅通
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
    }
}

Dijkstra算法

Dijkstra算法的核心是贪心

• 想求start ===> finish的最小距离
• 从start开始，考虑剩余（未到达）的可达节点中最小花费。
• 最小花费点作为下一个节点，更新花费表。
• 依次寻找最小花费，直至抵达目标点

      0     1     2     3
   -------------------------
  0|  0  |  2  |  6  |  4  |
   |     |     |     |     |
  1| INF |  0  |  3  | INF |
   |     |     |     |     |
  2|  7  | INF |  0  |  1  |
   |     |     |     |     |
  3|  5  | INF |  9  |  0  |
   -------------------------
从0号节点开始，此时达到其余各点的花费
	dist = [0, 2, 6, 4]
此时1、2、3节点均未达，1节点花费最小 前往1节点
	dist = [0, 2, 5, 4]
	借助1节点到达2节点比直接到达2节点花费小，更新距离表
......

实现

//graph：邻接矩阵
vector<bool> Dijkstr_visited(MAX, false);
vector<int> Dijkstra_dist(MAX, INF);
void Dijkstra(int val) {
    int start = val;
    Dijkstr_visited[start] = true; //到达过
    Dijkstra_dist = graph[start];      //初始化为初始行
    for (int i = 1; i < v; ++i) {
        int tmp = INF; //最近点
        for (int j = 0; j < v; ++j) {
            if (!Dijkstr_visited[j] && Dijkstra_dist[j] < tmp) { //未访问过，最小值
                start = j;//下次访问这个数组
                tmp = Dijkstra_dist[j];
            }
        }
        Dijkstr_visited[start] = true;
        for (int j = 0; j < v; ++j) {
            Dijkstra_dist[j] = min(Dijkstra_dist[j], Dijkstra_dist[start] + graph[start][j]);
        }
    }
}

Prim算法

Prim算法的核心在于

• 选择一个节点（生成树内部）开始，考虑到达其他节点的最小花费
• 寻找未抵达节点中最小花费（生成树外的节点），将该路径及点加入生成树内
• 遍历所有节点，直至全部节点加入生成树

在保证不成环的基础下，依次寻找抵达生成树外节点的最小花费

/***
 * graph：邻接矩阵
 * visited：存放节点是否访问过（最小生成树内部，外部）
 * lowcost：用于寻找靠近角标点的最小权值（扩展）
 * closecost：保存最靠近角标点的元素
 * lowcost[i]：closecost[i]是一对。
 * ***/
vector<bool> Prim_visited(MAX, false);
vector<int> Prim_lowcost(MAX, INF);
vector<int> Prim_closecost(MAX, INF);
void Prim() {
    int res = 0;
    // 初始化为从0节点开始
    Prim_visited[0] = true;
    Prim_lowcost = graph[0];
    cout << "0 ---->";
    for (int i = 0; i < v;++i) {
        // 最小权值，对应的角标
        int index = -1,
            tmp = INF;
        // 寻找lowcost的最小值（下一个目标）
        for (int j = 1; j < v; ++j) {   //0已经访问过了 visited[0]一定不成立 故从1开始
            if (!Prim_visited[j] && Prim_lowcost[j] < tmp) {
                index = j;
                tmp = Prim_lowcost[j];
            }
        }
        // 不可达
        if (index == -1) {
            cout << "cost:" << res << endl;
            return; //找不到节点 不可达
        }
        cout << index << " ---->";
        Prim_visited[index] = true;
        res += Prim_lowcost[index];
        // 更新最小权值表
        for (int j = 1; j < v;++j) {
            if (!Prim_visited[j] && graph[index][j] != INF && graph[index][j] < Prim_lowcost[j]) {
                Prim_lowcost[j] = graph[index][j];
                Prim_closecost[j] = index;
            }
        }
    }
}