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

图的遍历-深度优先和广度优先遍历

程序员文章站 2024-02-11 13:23:40
...

图的遍历

之前学数据机构学了图的深度遍历和广度遍历,但是都没有手动实现,直到做笔试题才发现问题很严重,通过对图的遍历,让我更加喜欢面向对象的方式来编程。

通过邻接矩阵的形成来存储图的信息。广度优先遍历和二叉树的按层遍历十分相似。

//
// Created by lss on 2020-03-23.
//
#include <iomanip>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

#define MAX 100
#define mainMatrixUDG main

class MatrixUDG{
private:
    char mVexs[MAX]; //顶点集
    int mVexNum;    // 顶点数
    int mEdgNum;    // 边数
    int mMatrix[MAX][MAX];  // 邻接矩阵

public:
    MatrixUDG();    // 创建图(自己输入数据)
    MatrixUDG(char vexs[],int vlen,char edges[][2],int elen); // 创建图(提供矩阵)
    ~MatrixUDG();

    void DFS();
    void BFS();

    void print(); // 打印矩阵
private:
    char readChar();    // 输入一个字符
    int getPosition(char ch);   // 返回ch在mMatrix中的位置
    int firstVertex(int v);     // 返回顶点的第一个临界顶点的索引
    int nextVertex(int v,int w); // 返回顶点V相对于w的下一个邻接顶点的索引
    void DFS(int i,int* visited);// 深度优先遍历的递归实现
};
/*
 * 自己输入数据创建图
 */
MatrixUDG::MatrixUDG() {
    char c1,c2;
    int i,p1,p2;
    cin>>mVexNum;   // 顶点数
    cin>>mEdgNum;   // 边数
    // 判断输入是否合法
    if(mVexNum<1 ||mEdgNum<1 ||(mEdgNum > (mVexNum*(mVexNum-1))))
        return;
    for(i = 0;i<mVexNum;i++){
        mVexs[i] = readChar();
    }
    for(i=0;i<mEdgNum;i++){
        // 读取结束和起始顶点
        c1 = readChar();
        c2 = readChar();

        p1 = getPosition(c1);
        p2 = getPosition(c2);
        if(p1==-1 || p2== -1){
            return;
        }

        mMatrix[p1][p2] = 1;
        mMatrix[p2][p1] = 1;
    }
}

MatrixUDG::~MatrixUDG() {}
/*
 * ch在mMatrix中的位置
 */
int MatrixUDG::getPosition(char ch) {
    int i;
    for(i=0;i<mVexNum;i++){
        if(mVexs[i] == ch)
            return i;
    }
    return -1;
}
/*
 * 读取一个字符
 */
char MatrixUDG::readChar() {
    char ch;
    do{
        cin>>ch;
    }while(!(ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z'));
    return ch;
}
/*
 * 返回顶点v的第一个邻接顶点的索引
 */
int MatrixUDG::firstVertex(int v) {
    int i;
    if(v<0 || v>(mVexNum-1))
        return -1;
    for(i=0;i<mVexNum;i++)
        if(mMatrix[v][i] == 1)
            return i;

    return -1;
}
/*
 * 返回v相对于w的下一个邻接顶点的索引
 */
int MatrixUDG::nextVertex(int v, int w) {
    int i;
    if(v<0 || v>(mVexNum-1) || w<0 ||w>(mVexNum-1))
        return -1;
    for(i = w+1;i<mVexNum;i++){
        if(mMatrix[v][i] == 1)
            return i;
    }
    return -1;
}
/*
 * 深度优先遍历的递归实现
 */
void MatrixUDG::DFS(int i, int* visited) {
    int w;
    visited[i] = 1;
    cout<<mVexs[i]<<' ';
    for(w = firstVertex(i);w>=0;w=nextVertex(i,w)){
        if(!visited[w])
            DFS(w,visited);
    }
}
/*
 * 深度优先搜索遍历图
 */
void MatrixUDG::DFS() {
    int i;
    int visited[MAX];   // 访问标记设置

    for(i=0;i<mVexNum;i++)
        visited[i] = 0;
    for(i=0;i<mVexNum;i++){
        if(!visited[i])
            DFS(i,visited);
    }
    cout<<endl;
}
/*
 * 广度优先遍历
 */
void MatrixUDG::BFS() {
    int head = 0;
    int rear = 0;
    int queue[MAX];
    int visited[MAX];
    int i,j,k;

    for(i=0;i<mVexNum;i++){
        visited[i] = 0;
    }
    for(i=0;i<mVexNum;i++){
        if(!visited[i]){
            visited[i] = 1;
            cout<<mVexs[i]<<" ";
            queue[rear++] = i; // 入队列
        }
        while(head != rear){
            j = queue[head++];  // 出队列
            for(k = firstVertex(j);k>=0;k=nextVertex(j,k)){
                if(!visited[k]){
                    visited[k] = 1;
                    cout<<mVexs[k]<<" ";
                    queue[rear++] = k;
                }
            }
        }
    }
    cout<<endl;
}
void MatrixUDG::print() {
    int i,j;
    for(i=0;i<mVexNum;i++){
        for(j=0;j<mVexNum;j++){
            cout<<mMatrix[i][j]<<" ";
        }
        cout<<endl;
    }
}
int mainMatrixUDG(){
    MatrixUDG* matrixUdg = new MatrixUDG();
    matrixUdg->print();
    matrixUdg->DFS();
    matrixUdg->BFS();
    return 0;
}

结果:
图的遍历-深度优先和广度优先遍历
参考博客: 参考博客

相关标签: 算法