关于图论算法

#include 
using namespace std;

int arr[105][105], n, m;

int main(int argc, char const *argv[])
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        arr[a][b] = c;
    }
    for (int i = 1; i <= n; i++)
    {
        cout << i << " : ";
        for (int j = 1; j <= n; j++)
        {
            if (arr[i][j] != 0)
            {
                cout << "{" << i << "-->" << j << ", " << arr[i][j] << "} ";
            }
        }
        cout << endl;
    }  
    return 0;
}

用于求解最短路

特点：

①慢

②求解多源最短路（从任意点到任意点的最短路径）

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
            }
        }
    }

③简单，好实现

代码实现：

#include 
#include 
using namespace std;

int arr[1005][1005], n, m, s;

int main(int argc, char const *argv[])
{
    memset(arr, 0x3F, sizeof(arr));
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (arr[a][b] > c) {
            arr[a][b] = c;
            arr[b][a] = c;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        arr[i][i] = 0;
        if (arr[s][i] == 0x3F3F3F3F) {
            cout << -1 << endl;
        } else {
            cout << arr[s][i] << endl;
        }
    }
    return 0;
}

特点：

①只存储有用信息，省空间

②可以以某个点为起点的所有边

与邻接矩阵互补！

邻接表实现：

#include 
using namespace std;

int n, m, edg[105][105];

int main(int argc, char const *argv[])
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        edg[a][++edg[a][0]] = b;
    }
    for (int i = 1; i <= n; i++)
    {
        cout << i << " : ";
        for (int j = 1; j <= edg[i][0]; j++)
        {
            cout << edg[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

 节省内存的邻接表实现：

#include 
#include 
using namespace std;

struct edge
{
    int s, e, v;
};

int main(int argc, char const *argv[])
{
    int n, m;
    cin >> n >> m;
    vector> edg(n+5, vector());
    for (int i = 0; i < m; i++)
    {
        //起点，终点，边权
        int a, b, c;
        cin >> a >> b >> c;
        edg[a].push_back((edge){a, b, c});
    }
    for (int i = 1; i <= n; i++)
    {
        cout << i << " : ";
        for (int j = 0; j < edg[i].size(); j++)
        {
            cout << "{" << i << "-->" << edg[i][j].e << ", " << edg[i][j].v << "}";
        }
        cout << endl;
    }
   
    return 0;
}

求解单源，没有负值！

每次找到该点到其它的点的最短路径。

代码实现：

#include 
#include 
#include 
#include 
using namespace std;

struct node
{
    int now, dis;
    bool operator< (const node &b) const {
        return this->dis > b.dis;
    }
};

struct edge
{
    int e, v;
};

int main(int argc, char const *argv[])
{
    int n, m, s, ans[100005];
    memset(ans, 0x3F, sizeof(ans));
    // cin >> n >> m >> s;
    scanf("%d%d%d", &n, &m, &s);
    vector> edg(n+5, vector());
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        // cin >> a >> b >> c;
        scanf("%d%d%d", &a, &b, &c);
        edg[a].push_back((edge){b, c});
        edg[b].push_back((edge){a, c});
    }
    priority_queue que;
    que.push((node){s, 0});
    ans[s] = 0;
    while (!que.empty())
    {
        node temp = que.top();
        que.pop();
        if (ans[temp.now] < temp.dis) {
            continue;
        }
        for (int i = 0; i < edg[temp.now].size(); i++)
        {
            int e = edg[temp.now][i].e, v = edg[temp.now][i].v;
            if (ans[e] > temp.dis + v) {
                ans[e] = temp.dis + v;
                que.push((node){e, ans[e]});
            }
        }  
    }
    for (int i = 1; i <= n; i++)
        {
            if (ans[i] == 0x3F3F3F3F) {
                // cout << -1 << endl;
                printf("-1n");
            } else {
                // cout << ans[i] << endl;
                printf("%dn", ans[i]);
            }
        }
    return 0;
}

5.链式前向星

用指针域模拟一个链表。