首页 > 其他分享 >图的存储结构

图的存储结构

时间:2023-06-06 18:55:08浏览次数:31  
标签:存储 adjList struct int 邻接矩阵 arc 顶点 结构

图的存储结构

标签(空格分隔): DS 图 顺序存储 链式存储


图的邻接矩阵存储的结点结构

  邻接矩阵:
1.如果是无向图,则是对称矩阵,Vi与Vj有边则arc[i][j]和arc[j][i]为1,否则为0;arc[i][i]=0;
2.如果是有向图,则不是对称矩阵,vi->vj则arc[i][j]为1,否则为0;arc[i][i]=0;
3.如果是网,则vi和vj有边或弧,则arc[i][j]=权;否则a[i][j]=INFINITY;arc[i][i]=0;
#define INFINITY 65535//表示无穷
typedef struct
{
    char vexs[MAXVEX];//顶点表
    int arc[MAXVEX][MAXVEX];//邻接矩阵,边表
    int numVexs,numarc;//图当前顶点数和边数
}* MGraph;

建立无向网图的邻接矩阵表示

void CreateMGraph(MGraph G)
{
    int i,j,k,w;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d",&G->numVexs,&G->numarc);
    
    //输入顶点信息
    for(i=0;i<G->numVexs;i++)
        scanf("%c",&G->Vexs[i]);
    
    //邻接矩阵初始化
    for(i=0;i<G->numVexs;i++)//邻接矩阵行循环
        for(j=0;j<G->numVexs;j++)//邻接矩阵列循环
            G->arc[i][j]=INFINITY;
          
    //输入边和权 
    for(k=0;k<G->numarc;k++)
    {
        printf("输入边(vi,vj)上的下标i,j和权值w:\n");
        scanf("%d,%d,%d",&i,&j,&w);
        
        G->arc[i][j]=w;
        G->arc[j][i]=G->arc[i][j];
    }
}

邻接表结构

//边表结点
typedef struct EdgeNode
{
    int adjvex;//邻接点域,存储该顶点对应下标
    int weight;//用于存储权值
    struct EdgeNode* next;//指向下一个邻接点
}EdgeNode,* EdgePtr;

//顶点表结点
typedef struct VertexNode
{
    char data;
    EdgePtr firstedge;//边表头指针
}VexNode,AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVexs,numEdges;//图当前顶点数和边数
}GraphAdjList,* GPtr;

无向图的邻接表的创建

void CreateALGraph(GPtr G)
{
    int i,j,k;
    EdgePtr e;//边表指针
    printf("输入顶点数和边数:\n");
    scanf("%d,%d",&G->numVexs,&G->numEdges);
    
    //输入顶点表
    for(i=0;i<G->numVexs;i++)
    {
        scanf("%c",&G->adjList[i].data);
        G->adjList[i].firstedge=NULL;//将边表置为空
    }
    
    for(k=0;k<numEdges;k++)
    {
        printf("输入边(vi.vj)上的顶点序号:\n");
        scanf("%d,%d",&i,&j);
        
        e=(EdgePtr)malloc(sizeof(EdgeNode));
        e->adjvex=j;
        //尾插法
        e->next=G->adjList[i].firstadge;
        G->adjList[i].firstedge=e;
        
        e=(EdgePtr)malloc(sizeof(EdgeNode));
        e->adjvex=i;
        e->next=G->adjList[j].firstedge;
        G->adjList[j].firstedge=e;
    }

标签:存储,adjList,struct,int,邻接矩阵,arc,顶点,结构
From: https://www.cnblogs.com/wa2211lq/p/17461451.html

相关文章

  • 数据结构(严蔚敏)
    第1章 绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间需求第2章 线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现......
  • [记]Rust结构体转换为二进制数据
    这个函数可以直接读取或者转化为二进制数据,适用于系统编程;usestd::mem;structTestdata{ucc:u8,udd:u8,}fnmain(){letddd=Testdata{ucc:2,udd:9};unsafe{letuu16:u16=mem::transmute_copy(&ddd);println!("{}",uu16%256);......
  • 使用JOL查看java对象内存结构
    JOL(JavaObjectLayout)工具包可以展示java对象在jvm中的结构信息,用来进行内存分析。是由openjdk提供的小工具包。git地址https://github.com/openjdk/jol。因此下面的测试基于hotspot虚拟机环境下。添加依赖<dependency><groupId>org.openjdk.jol</group......
  • 为了拒绝 Windows 所有可移动存储类的权限,请使用以下批处理脚本
    为了拒绝Windows所有可移动存储类的权限,请使用以下批处理脚本:CopyCoderegadd"HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\USBSTOR"/v"Start"/tREG_DWORD/d4/fregadd"HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\UsbStor&qu......
  • NFS存储简述
    什么是NFS?NFS就是networkfilesystem的缩写,中文:网络文件系统,NFS主要的功能是通过网络让不同的机器,不同的系统之间可以共享文件或者目录,可以认为是一个文件服务器。NFS服务器可以让客户端将网络远程的NFS服务器分享的目录挂载到客户端,在客户端看来,远程的主机(NFS服务器端)就好像......
  • mysql 存储过程
    存储过程是一组特定的语句合计,为实现某种特定的功能。编译后存贮在字典中。因为的多条语句集合后执行,为了避免与sql语句的结束符;冲突而逐条执行,创建之前要申明存储过程需要使用的分隔符。 delimter$$#定义分隔符为$$…………$$#执行delimiter;#执行后结束符修改为;i......
  • 数据结构之B树
    1引言B-tree,B即Balanced,是自平衡的多叉搜索树,用于组织和存储大量数据,以及数据库和文件系统等需要高效查找和插入操作的应用中。为什么是“大量数据”?当主存不足以放入大量数据时,不常用的数据应存储于外存,而访问外存有额外时间开销(如磁盘转动时间、磁头移动时间等),于是我们需要一......
  • 每日记录(线性表链式存储结构(链表))
    链表的基本概念建议每次写的时候都加一个头节点各结点由两个域组成:数据域:存储元素数值数据指针域:存储直接后继结点的存储位置结点:数据元素的存储映像。由数据域和指针域两部分组成链表:n个结点由指针链组成一个链表。它是线性表的链式存储映像,称为线性表的链式存储结构单链表......
  • 每日记录(数据结构 第一章 绪论)
    这些天准备学一下数据结构,面对越来越多的问题都需要使用设计一些算法,所以从网上摘抄总结的数据结构有关的知识 数据(data)是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(dataelement)是数据的基本单位,在计算机程......
  • 每日记录(数据结构 第二章 线性表() )
     线性表的定义:存在唯一一个“第一个”元素存在唯一一个“最后一个”元素除第一个元素外,每一个元素都有且只有一个前驱除最后一个元素外,每个元素都有且只有一个后继一、线性表顺序存储结构(顺序表)0.线性表的基本概念线性表强调元素在逻辑上紧密相邻,所以首先想到用数组存储。但是......