首页 > 其他分享 >图的存储-邻接矩阵

图的存储-邻接矩阵

时间:2024-04-04 18:45:46浏览次数:29  
标签:表示 存储 有向图 int 邻接矩阵 Edge 顶点

1. 有向图和无向图的邻接矩阵 

设 G(V, E)是一个具有 n 个顶点的图,则图的邻接矩阵是一个 n×n 的二维数组,用 Edge[n][n]表示,它的定义为:

下面的图给出了无向图 G1(V, E)及其邻接矩阵表示。在图中,为了表示顶点信息,特意将顶点的标号用字母 A、 B、 C、 D、 E 和 F 表示,各顶点的信息存储在顶点数组中,如图(b)所示,注意在 C/C++语言中,数组元素下标是从 0 开始计起的。 G1 的邻接矩阵如图(c)所示,从该图可以看出,无向图的邻接矩阵是沿主对角线对称的。 

对无向图的邻接矩阵来说, 如果 Edge[i][j] = 1, 则表示顶点 i 和顶点 j 之间有一条边。因此,邻接矩阵 Edge 第 i 行所有元素中元素值为 1 的个数表示顶点 i的度数,第 i 列所有元素中元素值为 1 的个数也表示顶点 i 的度数,即: 

而对有向图的邻接矩阵来说, 如果 Edge[i][j] = 1, 则表示存在从顶点 i 到顶点 j 有一条有向边, i 是起点, j 是终点。因此,邻接矩阵 Edge 第 i 行所有元素中元素值为 1 的个数表示顶点 i 的出度,第 i 列所有元素中元素值为 1 的个数表示顶点 i 的入度,即: 

2. 用邻接矩阵存储有向图,并输出各顶点的出入和入度 

输入描述:

输入文件中包含多个测试数据,每个测试数据描述了一个无权有向图。每个测试数据的第一行为两个正整数 n 和 m, 1 ≤ n ≤ 100, 1 ≤ m ≤ 500,分别表示该有向图的顶点数目和边数,顶点的序号从 1 开始计起。接下来有 m 行,每行为两个正整数,用空格隔开,分别表示一条边的起点和终点。每条边出现一次且仅一次,图中不存在自身环和重边。输入文件最后一行为 0 0,表示输入数据结束。

输出描述:

对输入文件中的每个有向图,输出两行:第 1 行为 n 个正整数,表示每个顶点的出度;第 2行也为 n 个正整数,表示每个顶点的入度。每两个正整数之间用一个空格隔开,每行的最后一个正整数之后没有空格。 

#include <iostream>
#include <cstring>

#define MAXL 100

using namespace std;

int Edge[MAXL][MAXL]; // 定义存储矩阵

int main() {
    int n, m; // n为顶点个数,m为边个数

    int od, id; // od为出度,id为入度
    int u, v; // u为起点,v为终点

    while (1) {
        cin >> n >> m;

        if (m == 0 && n == 0) {
            break;
        }
        memset(Edge, 0, sizeof(Edge));

        for (int i = 1; i <= m; i++) {
            cin >> u >> v; // 读入起点终点
            Edge[u - 1][v - 1] = 1; // 构建邻接矩阵
        }

        for (int i = 0; i < n; i++) {
            od = 0;
            for (int j = 0; j < n; j++) {
                od += Edge[i][j]; // 求入度
            }
            cout << od << " ";
        }
        cout << endl;
        for (int i = 0; i < n; i++) {
            id = 0;
            for (int j = 0; j < n; j++) {
                id += Edge[j][i]; // 求出度
            }
            cout << id << " ";
        }
        cout << endl;
    }
}

程序输出结果如下:

3.  有向网和无向网的邻接矩阵 

对于网络(即带权值的图),邻接矩阵的定义为: 

在编程实现时,可以用一个比较大的常量表示无穷大∞。

下面给出了无向网 G1(V, E)及其邻接矩阵表示。在无向网的邻接矩阵中,如果 0<Edge[i][j]<∞,则顶点 i 和顶点 j 之间有一条无向边,其权值为 Edge[i][j]。从图中可以看出,无向网的邻接矩阵也是沿主对角线对称的。

下面给出了有向网 G2(V, E)及其邻接矩阵表示。在有向网的邻接矩阵中,如果 0<Edge[i][j]<∞,则从顶点 i 到顶点 j 有一条有向边,其权值为 Edge[i][j]。从该图可以看出,有向网的邻接矩阵不一定是沿对主角线对称的。

  

 

标签:表示,存储,有向图,int,邻接矩阵,Edge,顶点
From: https://www.cnblogs.com/love-9/p/18114474

相关文章

  • 对象存储:现代数据管理的关键技术
    在当今数字化时代,数据的产生和积累呈现出爆炸式增长的趋势。面对海量的数据,传统的存储方式已经无法满足日益增长的需求。为了有效管理和利用这些数据,对象存储技术应运而生。对象存储分为三种类型,第一种:标准存储,较适合用于云应用,数据分享,内容分享,热点分享等等浏览频率较高的存......
  • 散列表的数据结构以及对象在JVM堆中的存储过程
    【版权声明】未经博主同意,谢绝转载!(请尊重原创,博主保留追究权)https://www.cnblogs.com/cnb-yuchen/p/18032068出自【进步*于辰的博客】参考笔记二,P67、P68.1。目录1、什么是“散列表”?2、关于对象存储过程2.1加载过程2.2注意事项3、Hashtable扩容机制3.1扩容机制是什么......
  • 达梦执行存储过程报死锁问题分析排查方法
    最近在一个项目中调用存储过程报死锁错误,而根据DEADLOCK_HISTORY也无法看出是哪个表产生了死锁,下面模拟一下环境做测试dropTABLEifEXISTStest;CREATETABLEtest(idint);BEGINforiin1..100loopinsertintotestVALUES(i);endloop;commit;end;CREATEorREP......
  • 【阅读笔记】MySQL数据库存储类型选择
    摘自:《高性能MySQL》第四版原则更小的通常更好一般来说,尽量使用能够正确存储和表示数据的最小数据类型。更小的数据类型通常更快,因为它们占用的磁盘、内存和CPU缓存的空间更少,并且处理时需要的CPU周期也更少。简单为好简单数据类型的操作通常需要更少的CPU周期。例如,整型数......
  • 进程调度-死锁-存储管理-固定分页分段
    进程调度进程调度方式是指当有更高优先级的进程到来时如何分配CPU。分为可剥夺和不可剥夺两种,可剥夺指当有更高优先级进程到来时,强行将正在运行进程的CPU分配给高优先级进程;不可剥夺是指高优先级进程必须等待当前进程自动释放CPU。在某些操作系统中,一个作业从提交到完成需要经......
  • MybatisPlus存储非List<Long>类型
    错误信息:java.lang.RuntimeException:FailedtodeserializeJSONtoList<Long> 使用mybatisplus的时候,对应数据库的实体类有个字段如下:@TableField(typeHandler=JacksonTypeHandler.class)privateList<String>authImages;需要存储图片列表的地址,["aaa.png","bbb.png&q......
  • 视频监控/云存储/AI智能分析平台EasyCVR集成时调用接口报跨域错误的原因排查
    EasyCVR视频融合平台基于云边端架构,可支持海量视频汇聚管理,能提供视频监控直播、云端录像、云存储、录像检索与回看、智能告警、平台级联、智能分析等视频服务。平台兼容性强,支持多协议、多类型设备接入,包括:国标GB/T28181协议、RTMP、RTSP/Onvif协议、海康Ehome、海康SDK、大华SDK......
  • MySQL之存储引擎,详细总结
    在介绍存储引擎之前我们先了解了解MySQL的体系结构:连接层最上层是一些客户端和链接服务,主要完成一些类似于连接处理、授权认证、及相关的安全方案。服务器也会为安全接入的每个客户端验证它所具有的操作权限服务层第二层架构主要完成大多数的核心服务功能,如SQL接口,并完......
  • 进程的操作与管理(PV方法/死锁/存储方法)
     操作系统本质上是人机之间交互的接口,人通过操作系统(比如命令行、窗口、菜单)去操控计算机硬件;同时也是应用软件与硬件之间的接口(换而言之可以控制程序的运行)。操作系统的五大作用:进程管理、存储管理、文件管理、作业管理、设备管理上图就是典型的计算机结构:硬件层......
  • mysql存储过程编写步骤
    1.创建存储过程DELIMITER$$  #将语句的结束符号从分号;临时改为2个$$(可以是自定义的)CREATEPROCEDUREProc()#创建存储过程,过程名为Proc,不带参数BEGIN #存储过程,以BEGIN关键字开......