程序员经验分享-hwhale

无向图的邻接矩阵与邻接表详细实现

2023-11-07

无向图的邻接矩阵

通过用邻接矩阵来表示无向图。如下无向图G1的邻接矩阵：

无向图G1的邻接矩阵

无向图G1包含了“A, B, C, D, E, F, G”共七个顶点，而且包含了“(A, C), (A, D), (A, F), (B, C), (C, D), (E, G), (F, G)”共七条边。由于这是无向图，所以(A, C)和(C, A)是同一条边，这里列举边时，按照字母先后顺序列举的。

无向图G1右边的邻接矩阵在内存中的邻接矩阵示意图。A[i][j] = 1表示第i个顶点与第j个顶点是邻接点，A[i][j] = 0表示它们不是邻接点。而i, j表示第i行和第j列的值。如：A[1, 2] = 1 表示第1个顶点B和第二个顶点C是邻接点。

代码实现

#include <iostream>
using namespace std;

#define MAX 100

class MatrixUDG
{
private:
    char mVexs[MAX];       //顶点集合
    int mVexNum;           //顶点数
    int mEdgNum;           //边数
    int mMatrix[MAX][MAX]; //邻接矩阵
public:
    //创建图(手动输入)
    MatrixUDG();
    //创建图(用提供的顶点和边)
    MatrixUDG(char *vexs, int vNum, char (*edges)[2], int eNum);
    ~MatrixUDG();
    //打印邻接表
    void print();
    //输入一个合法字母
    char readChar();
    //获得一个字母在顶点数组的下标
    int getPosition(char ch);
};

MatrixUDG::MatrixUDG()
{
    char c1, c2;
    int p1, p2;
    cout << "输入顶点数:";
    cin >> mVexNum;
    cout << "输入边数：";
    cin >> mEdgNum;
    if (mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum - 1))))
    {
        cout << "输入有误！" << endl;
        return;
    }
    for (int i = 0; i < mVexNum; ++i)
    {
        cout << "vertex(" << i << "):";
        mVexs[i] = readChar();
    }
    for (int j = 0; j < mEdgNum; ++j)
    {
        cout << "edge(" << j << "):";
        c1 = readChar();
        c2 = readChar();
        p1 = getPosition(c1);
        p2 = getPosition(c2);
        if (p1 == -1 || p2 == -1)
        {
            cout << "输入的边错误！" << endl;
            return;
        }
        mMatrix[p1][p2] = 1;
        mMatrix[p2][p1] = 1;
    }
}

MatrixUDG::MatrixUDG(char *vexs, int vNum, char (*edges)[2], int eNum)
{
    if (vNum > MAX)
        return;
    mVexNum = vNum;
    mEdgNum = eNum;
    //初始化顶点
    for (int i = 0; i < mVexNum; ++i)
        mVexs[i] = vexs[i];
    int p1, p2;
    for (int j = 0; j < mEdgNum; ++j)
    {
        //获得边的起始点和结束点
        p1 = getPosition(edges[j][0]);
        p2 = getPosition(edges[j][1]);
        //将连线的两个点都置为1
        if (p1 == -1 || p2 == -1)
        {
            cout << "输入的边错误！" << endl;
            return;
        }
        mMatrix[p1][p2] = 1;
        mMatrix[p2][p1] = 1;
    }
}

MatrixUDG::~MatrixUDG()
{
}

int MatrixUDG::getPosition(char ch)
{
    for (int 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;
}

void MatrixUDG::print()
{
    for (int i = 0; i < mVexNum; ++i)
    {
        for (int j = 0; j < mVexNum; ++j)
        {
            cout << mMatrix[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char edges[][2] = {
        {'A', 'C'},
        {'A', 'D'},
        {'A', 'F'},
        {'B', 'C'},
        {'C', 'D'},
        {'E', 'G'},
        {'F', 'G'}
    };
    int vNum = sizeof(vexs) / sizeof(vexs[0]);
    int eNum = sizeof(edges) / sizeof(edges[0]);
    //1. 根据提供的数据生成
//  MatrixUDG mudg(vexs, vNum, edges, eNum);
//  mudg.print();
    //2. 手动生成
    MatrixUDG mudg1;
    mudg1.print();
}

手动输入时运行结果如下：

输入顶点数:7
输入边数：7
vertex(0):A
vertex(1):B
vertex(2):C
vertex(3):D
vertex(4):E
vertex(5):F
vertex(6):G
edge(0):AC
edge(1):AD
edge(2):AF
edge(3):BC
edge(4):CD
edge(5):EG
edge(6):FG
0 0 1 1 0 1 0 
0 0 1 0 0 0 0 
1 1 0 1 0 0 0 
1 0 1 0 0 0 0 
0 0 0 0 0 0 1 
1 0 0 0 0 0 1 
0 0 0 0 1 1 0

无向图的邻接表

通过用邻接表来表示无向图。如下无向图G1的邻接表：

无向图G1的邻接表

无向图G1包含了“A, B, C, D, E, F, G”共七个顶点，而且包含了“(A, C), (A, D), (A, F), (B, C), (C, D), (E, G), (F, G)”共七条边。

无向图G1右边的邻接表示意图如上图。每个顶点都包含一个链表，该链表记录了“该顶点的邻接点的序号”。顶点C包含的链表所包含的数据分别是“0、1、3”，而“0、1、3”分别对应“A、B、D”的序号，“A、B、D”都是C的邻接点。就是通过这种方式记录图的信息的。

代码实现

#include <iostream>
using namespace std;

#define MAX 100

class ListUDG
{
private:
    //每一条边
    struct ENode
    {
        int iVex;               //指向的顶点的位置
        ENode *nextEdge = NULL; //指向顶点的下一条边的指针
    };
    //数组中存储的顶点
    struct VNode
    {
        char data;
        ENode *firstEdge = NULL; //指向第一条该顶点的边
    };

private:
    int mVexNum;      //图的顶点数目
    int mEdgeNum;     //图的边的数目
    VNode mVexs[MAX]; //存储顶点
public:
    ListUDG();
    ListUDG(char vexs[], int vNum, char edges[][2], int eNum);
    ~ListUDG();
    //打印邻接表
    void print();

private:
    //读取一个合法的输入字符
    char readChar();
    //返回字符ch在的位置
    int getPosition(char ch);
    //将node结点链接到list的最后
    void linkLast(ENode *list, ENode *node);
};

ListUDG::ListUDG()
{
    char c1, c2;
    int p1, p2;
    ENode *node1, *node2;
    cout << "输入顶点数:";
    cin >> mVexNum;
    cout << "输入边数:";
    cin >> mEdgeNum;
    if (mVexNum > MAX || mEdgeNum > MAX || mVexNum < 1 || mEdgeNum < 1 || (mEdgeNum > (mVexNum * (mVexNum - 1))))
    {
        cout << "输入有误！" << endl;
        return;
    }
    for (int i = 0; i < mVexNum; ++i)
    {
        cout << "vertex(" << i << "):";
        mVexs[i].data = readChar();
    }
    //初始化邻接表的边
    for (int j = 0; j < mEdgeNum; ++j)
    {
        cout << "edge(" << j << "):";
        c1 = readChar();
        c2 = readChar();
        p1 = getPosition(c1);
        p2 = getPosition(c2);
        if (p1 == -1 || p2 == -1)
        {
            cout << "输入的边有错误！" << endl;
            return;
        }

        node1 = new ENode();
        node1->iVex = p2;
        if (mVexs[p1].firstEdge == NULL)
            mVexs[p1].firstEdge = node1;
        else
            linkLast(mVexs[p1].firstEdge, node1);
        node2 = new ENode();
        node2->iVex = p1;
        if (mVexs[p2].firstEdge == NULL)
            mVexs[p2].firstEdge = node2;
        else
            linkLast(mVexs[p2].firstEdge, node2);
    }
}

ListUDG::ListUDG(char *vexs, int vNum, char (*edges)[2], int eNum)
{
    if (vNum > MAX || eNum > MAX)
        return;
    char c1, c2;
    int p1, p2;
    ENode *node1, *node2;
    mVexNum = vNum;
    mEdgeNum = eNum;
    for (int i = 0; i < mVexNum; ++i)
    {
        mVexs[i].data = vexs[i];
    }
    for (int j = 0; j < mEdgeNum; ++j)
    {
        c1 = edges[j][0];
        c2 = edges[j][1];
        p1 = getPosition(c1);
        p2 = getPosition(c2);
        if (p1 == -1 || p2 == -1)
        {
            cout << "输入的边有错误！" << endl;
            return;
        }
        node1 = new ENode();
        node1->iVex = p2;
        if (mVexs[p1].firstEdge == NULL)
            mVexs[p1].firstEdge = node1;
        else
            linkLast(mVexs[p1].firstEdge, node1);
        node2 = new ENode();
        node2->iVex = p1;
        if (mVexs[p2].firstEdge == NULL)
            mVexs[p2].firstEdge = node2;
        else
            linkLast(mVexs[p2].firstEdge, node2);
    }
}

ListUDG::~ListUDG() {}

void ListUDG::linkLast(ENode *list, ENode *node)
{
    ENode *p = list;
    while (p->nextEdge)
        p = p->nextEdge;
    p->nextEdge = node;
}

int ListUDG::getPosition(char ch)
{
    for (int i = 0; i < mVexNum; ++i)
    {
        if (mVexs[i].data == ch)
            return i;
    }
    return -1;
}

char ListUDG::readChar()
{
    char ch;
    do
    {
        cin >> ch;
    } while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));
    return ch;
}

void ListUDG::print()
{
    ENode *node;
    for (int i = 0; i < mVexNum; ++i)
    {
        cout << i << "(" << mVexs[i].data << "):";
        node = mVexs[i].firstEdge;
        while (node != NULL)
        {
            cout << node->iVex << "(" << mVexs[node->iVex].data << ")";
            node = node->nextEdge;
        }
        cout << endl;
    }
}

int main(int argc, char **argv)
{
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char edges[][2] = {
        {'A', 'C'},
        {'A', 'D'},
        {'A', 'F'},
        {'B', 'C'},
        {'C', 'D'},
        {'E', 'G'},
        {'F', 'G'}
    };
    int vNum = sizeof(vexs) / sizeof(vexs[0]);
    int eNum = sizeof(edges) / sizeof(edges[0]);
    //1. 根据提供的数据生成
//  ListUDG ludg(vexs, vNum, edges, eNum);
//  ludg.print();
    //2. 手动输入
    ListUDG ludg;
    ludg.print();
    return 0;
}

手动输入时运行结果如下：

输入顶点数:7
输入边数:7
vertex(0):A
vertex(1):B
vertex(2):C 
vertex(3):D
vertex(4):E
vertex(5):F
vertex(6):G
edge(0):AC
edge(1):AD
edge(2):AF
edge(3):BC
edge(4):CD
edge(5):EG
edge(6):FG
0(A):2(C)3(D)5(F)
1(B):2(C)
2(C):0(A)1(B)3(D)
3(D):0(A)2(C)
4(E):6(G)
5(F):0(A)6(G)
6(G):4(E)5(F)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

无向图的邻接矩阵与邻接表详细实现 的相关文章

  • Typora主题推荐

    Typora主题推荐 官网 https theme typora io 以前我用的是github主题 现在是Drake 但是字体有点小 改了css 进行微调一下 1 cobalt主题 2 Drake主题 3 fluent主题 4 gitbo

随机推荐

  • 读《自己动手写操作系统》（于渊著）第一节

    最近开始看 自己动手写操作系统 虽然很早以前就读过一点点 但一直没有机会动手实践 本着光说不练假把式的原则 今天动手实践了开头的一部分 说得这么正经其实你就是看了一点点吧 囧 废话不多说 在这里做一个小小的总结 实验环境 操作系统 win7

  • python实现调用科大讯飞语音听写（将音频识别成文字输出）

    一 大致流程 1 申请科大讯飞账号 https passport xfyun cn register 2 创建应用 应用平台选择WebAPI 3 查看开发文档 4 根据开发文档和示例代码进行调试 二 申请科大讯飞账号 首先我们先去科大讯飞开

  • MySQL——通过binlog恢复数据

    目录 1 binlog基本概念 2 MySQL开启binlog 3 使用binlog日志恢复数据 3 1 恢复前准备工作 3 2 数据恢复 3 2 1 通过mysqlbinlog将binlog转为sql 以方便查询具体位置 3 2 2 查看

  • 零点分布对单位脉冲响应的影响

    共四个二阶网络的系统函数 画系统零极点分布图 求各系统单位脉冲响应 画波形 H1 clc clear all close all A 1 1 6 0 9425 B 1 0 0 figure zplane B A z roots B zero

  • DM8 用户与权限管理

    一 用户及权限管理 1 1 创建用户 create user test identified by Test 1234 default tablespace test 1 2 用户改密码 alter user SYSDBA identifi

  • 【战略布局】12.8黄金白银涨跌发展趋势-黄金原油走势操作建议

    黄金消息面与技术面解析 消息面 周三 12月8日 亚市盘中 黄金期货温和上涨 现报1789美元 盎司附近 稍早期金曾短暂突破1790美元 盎司关口 周二 12月7日 金价小幅上涨 主要是受到通胀预期和地缘局势担忧的支撑 投资者将注意力聚焦将

  • Xshell突然连接不上虚拟机的解决

    目录 问题描述 失败的尝试 最终解决 感想 问题描述 国庆节后继续学习 在使用Xshell登录虚拟机时突然登不上了 而且只有三台中的一台登不上 考虑到之前对虚拟机的配置是在一台win机器上使用VMware Workstation软件创建了三

  • 锐浪(Grid++Report)报表脚本通过某些字段隐藏控件

    var panduantj Report ParameterByName leix AsString 你的字段名 var xians Report ControlByName chuchai 获取图片控件 if panduantj 出差 x

  • wps合并重复项并求和_表格技巧—Excel中重复项求和的方法

    在Excel统计数据时 经常会碰到重复项反复出现 很干扰视线 想要对重复项进行合并并求和 那要如何操作呢 下面 小编跟大家详细讲解Excel合并重复项数据并求和的操作方法 首先打开一个需要处理的Excel表格 比如对下列表格中相同型号的数量

  • Scrapy中extract_first()和extract()的区别

    测试用到的爬取网站 In 11 print response xpath h3 a title scrapy selector unified SelectorList 是Selector组成的列表 Out 11 为了方便阅读换行符我手打的

  • python降低cpu的占用

    import signal import resource import os import time from multiprocessing import Process def time exceeded signo frame ti

  • 2023华为OD机试真题-工作安排(JAVA、Python、C++)

    题目描述 小明每周上班都会拿到自己的工作清单 工作清单内包含n项工作 每项工作都有对应的耗时时长 单位h 和报酬 工作的总报酬为所有已完成工作的报酬之和 那么请你帮小明安排一下工作 保证小明在指定的工作时间内工作收入最大化 输入描述 输入的

  • Qt 事件过滤器

    通过前面的学习 我们已经知道 Qt 创建了QEvent事件对象之后 会调用QObject的event 函数处理事件的分发 显然 我们可以在event 函数中实现拦截的操作 由于event 函数是 protected 的 因此 需要继承已有类

  • 2023最新Web前端经典面试试题及答案-史上最全前端面试题(含答案)

    近期总结一一些面试题 都是企业的面试题笔记题 感觉薪资10k 15k的常见面试题 个人录制的最新Vue项目学习视频 B站 Vue2 第二版 后台管理系统项目实战 vue element ui vue经典全套系统案例讲解 哔哩哔哩 bilib

  • python中的 datetime 的使用

    python 中 datetime 的使用方法 介绍 所谓 datetime 其实就是 date time date 和 time的集合 下面介绍使用方法 常搭配logging记录日志 date from datetime import d

  • 三创赛优秀作品_三创赛优秀作品.doc

    PAGE PAGE 138 全国高校首届 创意 创新 创业 电子商务挑战赛 农舍吧 电子商务旅游网站 参赛策划书 北京邮电大学 开心吧 电子商务团队 团队成员 吴新军 林朝波 高有富 陈和磊 指导老师 胡 桃 2009年12月 TOC o

  • Map 和 Set 使用的区别和联系（建议收藏）

    我是目录 1 搜索 1 概念及场景 2 模型 2 Map 的使用 3 Set 的使用 表现 两个接口 Set 和 Map 接口 1 搜索 1 概念及场景 Map 和 set 是一种专门用来进行 搜索的容器 或者 数据结构 其搜索的效率与其具

  • 用递归求斐波那契数列

    2137 斐波那契数列 时间限制 1 Sec 内存限制 128 MB 提交 2116 解决 2242 提交 状态 讨论版 命题人 lym 题目描述 斐波那契数列 Fibonacci sequence 又称黄金分割数列 兔子数列 是数学家列昂

  • MyBatis-Plus：条件构造器Wrapper

    目录 1 Wrapper概述 1 1 Wrapper的继承关系 1 2 Wapper介绍 1 3 各个构造器使用区别 1 4 构造器常用方法 2 Wrapper常用构造器介绍 2 1 QueryWrapper 2 2 UpdateWrapp

  • 无向图的邻接矩阵与邻接表详细实现

    无向图的邻接矩阵 通过用邻接矩阵来表示无向图 如下无向图G1的邻接矩阵 无向图G1包含了 A B C D E F G 共七个顶点 而且包含了 A C A D A F B C C D E G F G 共七条边 由于这是无向图 所以 A C 和

热门标签