图的基本算法求遍历和路径

定义一个有n个结点的以邻接矩阵为存储方式的网（有向无向均可）
1.深度优先遍历，并输出遍历序列2.广度优先遍历，并输出遍历序列3.求源点到图中每个点的最短路径，并输出

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

const int MAXV = 100;
const int INF = 0x3f3f3f3f;

int n;
int G[MAXV][MAXV];
bool vis[MAXV];
int d[MAXV];

// 深度优先遍历
void DFS(int u) {
    vis[u] = true;
    cout << u << " ";
    for (int v = 0; v < n; v++) {
        if (!vis[v] && G[u][v] != INF) {
            DFS(v);
        }
    }
}

// 广度优先遍历
void BFS(int u) {
    queue<int> q;
    vis[u] = true;
    cout << u << " ";
    q.push(u);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 0; v < n; v++) {
            if (!vis[v] && G[u][v] != INF) {
                vis[v] = true;
                cout << v << " ";
                q.push(v);
            }
        }
    }
}

// Dijkstra算法求最短路径
void Dijkstra(int s) {
    fill(d, d + n, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) return;
        vis[u] = true;
        for (int v = 0; v < n; v++) {
            if (!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
                d[v] = d[u] + G[u][v];
            }
        }
    }
}

int main() {
    cin >> n;
    fill(G[0], G[0] + MAXV * MAXV, INF);
    // 读入邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> G[i][j];
        }
    }
    // 深度优先遍历
    fill(vis, vis + MAXV, false);
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            DFS(i);
        }
    }
    cout << endl;
    // 广度优先遍历
    fill(vis, vis + MAXV, false);
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            BFS(i);
        }
    }
    cout << endl;
    // Dijkstra算法求最短路径
    fill(vis, vis + MAXV, false);
    Dijkstra(0);
    for (int i = 0; i < n; i++) {
        cout << d[i] << " ";
    }
    return 0;
}

好的，以下是C++代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

const int MAX_SIZE = 100; // 矩阵大小
const int INF = 0x3f3f3f3f; // 无穷大

// 网的邻接矩阵
struct MGraph {
    int vexs[MAX_SIZE]; // 顶点集合
    int edges[MAX_SIZE][MAX_SIZE]; // 邻接矩阵
    int n, e; // 点数和边数
};

// 深度优先遍历
void DFS(const MGraph& G, int v, vector<bool>& visited, vector<int>& result) {
    visited[v] = true;
    result.push_back(G.vexs[v]);
    for (int i = 0; i < G.n; i++) {
        if (G.edges[v][i] != INF && !visited[i]) {
            DFS(G, i, visited, result);
        }
    }
}

// 广度优先遍历
void BFS(const MGraph& G, int v, vector<bool>& visited, vector<int>& result) {
    queue<int> q;
    visited[v] = true;
    q.push(v);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(G.vexs[u]);
        for (int i = 0; i < G.n; i++) {
            if (G.edges[u][i] != INF && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

// 求源点到图中每个点的最短路径
void ShortestPath(const MGraph& G, int v, vector<int>& dist, vector<int>& path) {
    vector<bool> visited(G.n, false);
    dist.assign(G.n, INF);
    path.assign(G.n, -1);
    dist[v] = 0;
    for (int i = 0; i < G.n; i++) {
        int u = -1;
        for (int j = 0; j < G.n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        visited[u] = true;
        for (int j = 0; j < G.n; j++) {
            if (G.edges[u][j] != INF && dist[j] > dist[u] + G.edges[u][j]) {
                dist[j] = dist[u] + G.edges[u][j];
                path[j] = u;
            }
        }
    }
}

// 输出遍历序列
void PrintResult(const vector<int>& result) {
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    cout << endl;
}

int main() {
    MGraph G;
    cout << "请输入点数和边数：";
    cin >> G.n >> G.e;
    cout << "请输入顶点集合：";
    for (int i = 0; i < G.n; i++) {
        cin >> G.vexs[i];
    }
    fill(G.edges[0], G.edges[0] + MAX_SIZE * MAX_SIZE, INF);
    cout << "请输入边信息：" << endl;
    for (int i = 0; i < G.e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G.edges[u][v] = w;
        G.edges[v][u] = w; // 如果是无向图，需要加上这句
    }

    // 深度优先遍历
    vector<bool> visited(G.n, false);
    vector<int> result;
    cout << "深度优先遍历：";
    for (int i = 0; i < G.n; i++) {
        if (!visited[i]) {
            DFS(G, i, visited, result);
        }
    }
    PrintResult(result);

    // 广度优先遍历
    visited.assign(G.n, false);
    result.clear();
    cout << "广度优先遍历：";
    for (int i = 0; i < G.n; i++) {
        if (!visited[i]) {
            BFS(G, i, visited, result);
        }
    }
    PrintResult(result);

    // 求源点到图中每个点的最短路径
    int s;
    cout << "请输入源点编号：";
    cin >> s;
    vector<int> dist, path;
    ShortestPath(G, s, dist, path);
    cout << "源点到各点的最短路径如下：" << endl;
    for (int i = 0; i < G.n; i++) {
        cout << G.vexs[s] << "到" << G.vexs[i] << "的最短路径为：" << dist[i] << "，路径为：";
        stack<int> stk;
        int p = path[i];
        while (p != -1) {
            stk.push(p);
            p = path[p];
        }
        while (!stk.empty()) {
            cout << G.vexs[stk.top()] << "->";
            stk.pop();
        }
        cout << G.vexs[i] << endl;
    }

    return 0;
}

以上代码实现了深度优先遍历、广度优先遍历和求源点到图中每个点的最短路径。其中，深度优先遍历和广度优先遍历的思路比较简单，都是基于图的邻接矩阵实现的，而求最短路径采用了Dijkstra算法，可以实现单源最短路径问题。