关于#c++#的问题：实验邻接矩阵类的设计

Question

1. 实验邻接矩阵类的设计：实现无向图，有向图，无向网，有向网的输入，存储，度（入度，出度）的求解，任意两顶点之间是否有边或弧，若是网，还要输出其权值（若存在）；
2. 输入输出方式自定义

Answer 1

#include <iostream>
using namespace std;

#define MAX_VERTEX_NUM  20                              //图的最大顶点
#define INF             10000                           //最大极值
typedef enum{ DG, DN, UDG, UDN } GraphKind;             //图的种类
typedef int TYPE;                                       //数据的类型

class GraphMat
{
public:
    GraphMat(GraphKind k);
    ~GraphMat();
private:
    //图的邻接矩阵一般需要6个信息
    GraphKind kind;                                //图的种类。枚举类型:有向图DG，有向网DN，无向图UDG，无向网UDN。
    int vex_num;                                //图的顶点个数
    TYPE vexs[MAX_VERTEX_NUM];                    //顶点的数据值数组GraphMat(GraphKind k) :kind(k), vex_num(0);
    int arc_num;                                //图的边（弧）个数
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];    //邻接矩阵。对图：用1或0表示两顶点是否相邻；对网：表示两顶点之间的权值。
    bool is_trav[MAX_VERTEX_NUM];                //遍历标志
public:
    void CreateGraph();                                 //构造一个图
    void BFSTraverse();                                 //广度优先遍历
    void DFSTraverse();                                 //深度优先遍历
public:
    void Degree(int index,int& inDegree,int& outDegree);//求图中某个顶点的入度和出度
    int isExistEdgeBetweenAandB(int A,int B);             //任意两顶点之间是否有边或弧,对网：表示两顶点之间的权值。
private:
    void BFSFunction(int);                              //广度优先
    void DFSFunction(int);                              //深度优先
};

GraphMat::GraphMat(GraphKind k = UDG)
    :kind(k), vex_num(0), arc_num(0)
{
    //清空矩阵
    for (int i = 0; i < MAX_VERTEX_NUM; i++)
    {
        for (int j = 0; j < MAX_VERTEX_NUM; j++)
            arcs[i][j] = INF;                           //设置矩阵中各元素的值为最大值  
    }
    //清空遍历标志
    for (int i = 0; i < MAX_VERTEX_NUM; i++){
        is_trav[i] = 0;
    }
}


GraphMat::~GraphMat()
{
}

void GraphMat::CreateGraph()
{
    cout << "输入顶点元素的个数" << endl;
    cin >> vex_num;
    cout << "输入顶点元素的类型值" << endl;
    for (int i = 0; i < vex_num; i++){
        cin >> vexs[i];
    }

    cout << "输入邻接矩阵的大小" << endl;
    cin >> arc_num;
    cout << "输入邻接矩阵" << endl;
    for (int i = 0; i < arc_num; i++){
        for (int j = 0; j < arc_num; j++){
            cin >> arcs[i][j];
        }
    }
}

//广度优先遍历
void GraphMat::BFSTraverse()
{
    //将标记清0
    for (int i = 0; i < vex_num; i++){
        is_trav[i] = 0;
    }
    //对顶点遍历
    for (int i = 0; i < vex_num; i++){
        //if (!is_trav[i]){
        //  BFSFunction(i);
        //}
        BFSFunction(i);
    }
}

void GraphMat::BFSFunction(int i)
{
    if (!is_trav[i]){
        is_trav[i] = 1;                                     //标记顶点
        cout << "->" << vexs[i];
    }
    for (int j = 0; j < vex_num; j++){
        if (arcs[i][j] != 0 && !is_trav[j]){
            cout << "->" << vexs[j];
            is_trav[j] = 1;
        }
    }
}

void GraphMat::DFSTraverse()
{
    //将标记清0
    for (int i = 0; i < vex_num; i++){
        is_trav[i] = 0;
    }
    //对顶点遍历
    for (int i = 0; i < vex_num; i++){
        //if (!is_trav[i]){
            DFSFunction(i);
        //}
    }
}

void GraphMat::DFSFunction(int i)
{
    is_trav[i] = 1;
    cout << "->" << vexs[i];
    for (int j = 0; j < vex_num; j++){
        if (arcs[i][j] != 0 && !is_trav[j]){
            DFSFunction(j);
        }
    }
}


// 求图中某个顶点的入度和出度
void GraphMat::Degree(const int index,int& inDegree,int& outDegree)
{
    int inD = 0;
    int ouD = 0;
    for(int i = 0; i < MAX_VERTEX_NUM; i++) // 行
    {
        if(0 != arcs[i][index] && i!=index)
        {
            inD++;
        }
        if(0 != arcs[index][i] && i!=index)
        {
            ouD++;
        }
    }
    cout << "顶点" << index << "的入度为:" << inD << endl; 
    cout << "顶点" << index << "的出度为:" << ouD << endl; 
    inDegree = inD;
    outDegree= ouD;
}
 

int GraphMat::isExistEdgeBetweenAandB(int A,int B)
{
    return arcs[A][B];
}
int main()
{
    GraphMat graph(UDG);
    graph.CreateGraph();
    
    int inD = 0;
    int ouD = 0;
    int index= 1;
    graph.Degree(index,inD,ouD);
    cout<<"节点"<<index<<"的入度为："<<inD<<" 出度为："<<ouD<<endl;
    
    int indexA = 1;
    int indexB = 2;
    int isExist = graph.isExistEdgeBetweenAandB(indexA,indexB);
    cout<<"节点"<<indexA<<"与"<<"节点"<<index<<"之间的邻接矩阵值为"<<isExist<<endl;
    
    cout << "广度遍历效果 ： " << endl;
    graph.BFSTraverse();
    cout << endl;
    cout << "深度遍历效果 ： " << endl;
    graph.DFSTraverse();
    cout << endl;
    return 0;
}