邻接矩阵存储无向图

邻接矩阵的优点:

        可以快速判断两个顶点之间是否有边;

        方便计算各顶点的度,无向图中:顶点i的度 = 邻接矩阵第i行(列)中的元素和;有向图中:顶点的出度 = 邻接矩阵第i行中的元素和,顶点的入度 = 邻接矩阵第i列中的元素和。

邻接表的缺点:

        不方便增删节点;

        不便于访问一个顶点的所有邻接点;

        空间复杂度高,为O(n^2)。

1、邻接矩阵类定义:

        有3部分组成:一个顶点类型的一维数组,用于存储顶点;一个int类型的二维数组,用于存储边;两个int型变量,分别存储顶点数、边数。

class AMGragh
{
public:
    VexType vex[max_vertex_num];
    int edge[max_vertex_num][max_vertex_num];
    int vex_num, edge_num;
};

2、查找顶点在数组的下标:

int LocateVex(const AMGragh& g, const VexType& x)
{
    for (int i = 0; i < g.vex_num; i++)
    {
        if (x == g.vex[i])
        {
            return i;
        }
    }
    return -1;
}

3、创建邻接矩阵:

        首先,把输入的顶点信息放置在顶点数组中;之后,根据输入边的两个顶点u、v,找到在顶点数组中的下标loc_u、loc_v;最后、在邻接矩阵中把对应位置置1,代表一条边。

void InsertEdge(AMGragh& g, const int i, const int j)
{
    g.edge[i][j] = g.edge[j][i] = 1;
}

void CreateAMGragh(AMGragh& g)
{
    VexType u, v;
    int loc_u, loc_v;
    memset(g.edge, 0, sizeof(g.edge));
    memset(g.edge, 0, sizeof(g.edge));
    cout << "请输入顶点数:" << endl;
    cin >> g.vex_num;
    cout << "请依次按顺序输入顶点:" << endl;
    for (int i = 0; i < g.vex_num; i++)
    {
        cin >> g.vex[i];
    }
    cout << "请输入边数:" << endl;
    cin >> g.edge_num;
    cout << "请依次输入边的两个顶点:" << endl;
    for (int i = 0; i < g.edge_num; i++)
    {
        cin >> u >> v;
        loc_u = LocateVex(g, u);
        loc_v = LocateVex(g, v);
        if (loc_u != -1 && loc_v != -1)
        {
            InsertEdge(g, loc_u, loc_v);
        }
        else
        {
            cout << "有没找到的顶点,请重新输入:" << endl;
            i--;
        }
    }
}

4、输出邻接矩阵:

void OutputAMGragh(const AMGragh& g)
{
    for (int i = 0; i < g.vex_num; i++)
    {
        for (int j = 0; j < g.vex_num; j++)
        {
            cout << g.edge[i][j] << " ";
        }
        cout << endl;
    }
}

整体代码实现:

#include <iostream>
using namespace std;
#define max_vertex_num 10

using VexType = char;

class AMGragh
{
public:
    VexType vex[max_vertex_num];
    int edge[max_vertex_num][max_vertex_num];
    int vex_num, edge_num;
};

int LocateVex(const AMGragh& g, const VexType& x)
{
    for (int i = 0; i < g.vex_num; i++)
    {
        if (x == g.vex[i])
        {
            return i;
        }
    }
    return -1;
}

void InsertEdge(AMGragh& g, const int i, const int j)
{
    g.edge[i][j] = g.edge[j][i] = 1;
}

void CreateAMGragh(AMGragh& g)
{
    VexType u, v;
    int loc_u, loc_v;
    memset(g.edge, 0, sizeof(g.edge));
    memset(g.edge, 0, sizeof(g.edge));
    cout << "请输入顶点数:" << endl;
    cin >> g.vex_num;
    cout << "请依次按顺序输入顶点:" << endl;
    for (int i = 0; i < g.vex_num; i++)
    {
        cin >> g.vex[i];
    }
    cout << "请输入边数:" << endl;
    cin >> g.edge_num;
    cout << "请依次输入边的两个顶点:" << endl;
    for (int i = 0; i < g.edge_num; i++)
    {
        cin >> u >> v;
        loc_u = LocateVex(g, u);
        loc_v = LocateVex(g, v);
        if (loc_u != -1 && loc_v != -1)
        {
            InsertEdge(g, loc_u, loc_v);
        }
        else
        {
            cout << "有没找到的顶点,请重新输入:" << endl;
            i--;
        }
    }
}

void OutputAMGragh(const AMGragh& g)
{
    for (int i = 0; i < g.vex_num; i++)
    {
        for (int j = 0; j < g.vex_num; j++)
        {
            cout << g.edge[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    AMGragh g;
    CreateAMGragh(g);
    OutputAMGragh(g);
    return 0;
}

上一篇:UI自动化框架搭建(五): selenium封装类解析


下一篇:pandas