欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的DFS和BFS的C++实现

程序员文章站 2022-05-24 08:47:39
...

使用邻接矩阵存储图

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

int vertex[100]; // 顶点数组
int edge[100][100]; // 边数组
bool visited[100]; // 访问标记
int n; // 顶点个数


void visit(int v) {
    cout << vertex[v] << "  ";
}

void DFS(int v) {
    visit(v); // 访问顶点元素
    visited[v] = true;
    for (int w = 0; w < n; w++) {
        if (edge[v][w] == 1 && visited[w] == false) {
            visited[w] = true;
            DFS(w);
        }
    }
}

void BFS(int v) {
    visit(v);
    visited[v] = true;
    queue<int> Q;
    Q.push(v);
    while (!Q.empty()) {
        int f = Q.front();
        Q.pop();
        for (int w = 0; w < n; w++) {
            if (edge[w][f] == 1 && visited[w] == false) {
                visit(w);
                visited[w] = true;
                Q.push(w);
            } 
        }
    }
}

int main() {
    n = 8; // 顶点个数

    /*--------------初始化-----------------*/
    for (int i = 0; i < n; i++) {
        vertex[i] = i;
    }
    for(int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j)
                edge[i][j] = 0;
            else edge[i][j] = 0x3fffffff;
        }
    }
    edge[0][1] = 1; edge[1][0] = 1;
    edge[0][3] = 1; edge[3][0] = 1;
    edge[4][3] = 1; edge[3][4] = 1;
    edge[1][4] = 1; edge[4][1] = 1;
    edge[1][6] = 1; edge[6][1] = 1;
    edge[1][2] = 1; edge[2][1] = 1;
    edge[2][6] = 1; edge[6][2] = 1;
    edge[2][5] = 1; edge[5][2] = 1;
    edge[5][6] = 1; edge[6][5] = 1;
    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }
    /*--------------初始化-----------------*/

    cout << "==============下面是DFS==================" << endl;
    for (int i = 0; i < n; i++) {
        if (!visited[i])
            DFS(i);
    }
    cout << endl;
    cout << "==============下面是BFS==================" << endl;
    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i])
            BFS(i);
    }
    cout << endl;
    return 0;
}
相关标签: C++