正文 

当前位置： 首页 > java > java教程

图学习笔记（11.21）(代码片段)

未定_ 未定_     2023-02-07     762

关键词：

最近数据结构和离散数学都学习了有关图的知识，自己学习算法也对图有了更加深入的了解，下面做一下汇总，便于复习翻看。(思路是自己理解写的，代码非原创)

图

一、图的概念

戳一戳->

二、图的存储

先补充两种图的遍历方式：

1.邻接矩阵

思想：一个一维数组vertex[i]存顶点，一个二维数组edge[i][j]存边。
设图G=(V,E)有n个顶点，则邻接矩阵是一个n*n的方阵：
边无权值时，0表示顶点i和j之间无边，1表示有边：
e d g e [ i ] [ j ] = 0 若 ( v i , v j ) ∈ E 或 < v i , v j > ∈ E 1 否 则 edge[i][j]= \\begincases 0& &若(v_i,v_j)∈E或<v_i,v_j>∈E\\\\ 1& &否则 \\endcases edge[i][j]=01​​若(vi​,vj​)∈E或<vi​,vj​>∈E否则​
边有权值时，wij表示顶点i到j的权值，0表示i=j，∞表示i和j之间无边：
e d g e [ i ] [ j ] = w i j 若 ( v i , v j ) ∈ E 或 < v i , v j > ∈ E 0 若 i = j ∞ 否 则 edge[i][j]= \\begincases w_ij& &若(v_i,v_j)∈E或<v_i,v_j>∈E\\\\ 0& &若i=j\\\\ ∞& &否则 \\endcases edge[i][j]=⎩⎪⎨⎪⎧​wij​0∞​​若(vi​,vj​)∈E或<vi​,vj​>∈E若i=j否则​
无向图的邻接矩阵是对称矩阵，即edge[i][j]=edge[j][i]，有向图则不符合这个特点。邻接矩阵的主对角线为0，无向图中顶点i的度为第i行/列中非零元素的个数，有向图中顶点i的出度为第i行元素之和，入度为第i列元素之和。
注意：edge[i][j]中i和j代表顶点的顺序取决于vertex[i]中存储的顺序，如：vertex[4]=v0,v3,v1,v2，则edge[2][1]对应的边是(v1,v3)而不是(v2,v1)。
时间和空间复杂度O(n2)

const int MaxSize=10;
int visited[MaxSize];
class Mgraph

public:
    Mgraph(int a[],int n,int e);//构造函数，建立n个顶点e条边的图
    ~Mgraph() 
    void DFSTraverse(int v);//深度优先遍历图
    void BFSTraverse(int v);//广度优先遍历图
private:
    int vertex[MaxSize];
    int edge[MaxSize][MaxSize];
    int vertexNum,edgeNum;//顶点数与边数
;
Mgraph::Mgraph(int a[],int n,int e)

    int i,j,k;
    vertexNum=n;
    edgeNum=e;
    for(i=0; i<vertexNum; i++)
        vertex[i]=a[i];//顶点数组赋值
    for(i=0; i<vertexNum; i++)
        for(j=0; j<vertexNum; j++)
            edge[i][j]=0;//边数组初始化
    for(k=0; k<edgeNum; k++) //给边赋值
    
        cin>>i>>j;
        edge[i][j]=1;
        edge[j][i]=1;//无向图，若想变成有向图，只需要删除本句
    

void Mgraph::DFSTraverse(int v)

    cout<<vertex[v];//访问顶点
    visited[v]=1;//置顶点被访问过
    for(int j=0; j<vertexNum; j++)
    
        if(edge[v][j]==1&&visited[j]==0)
            DFSTraverse(j);
    

void Mgraph::BFSTraverse(int v)

    int w,j,Q[MaxSize];
    int front=-1,rear=-1;
    cout<<vertex[v];//访问顶点
    visited[v]=1;//置顶点被访问过
    Q[++rear]=v;
    while(front!=rear)
    
        w=Q[++front];//队头元素出队
        for(j=0; j<vertexNum; j++)
        
            if(edge[w][j]==1&&visited[j]==0)
            
                cout<<vertex[j];
                visited[j]=1;
                Q[++rear]=j;

2.邻接表

顺序存储与链式存储相结合的表示图的一种方法。
思想：图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（有向图则称为出边表）
所有边表的头指针和存储顶点信息的一维数组构成了顶点表。如下图：

如果边有权值的话只需要在边表结构体里加一个变量info表示权值即可。
无向图中顶点i的边表中结点的个数为顶点i的度。
有向图中顶点 i 的出边表中结点的个数为顶点 i 的出度；各顶点的出边表中以顶点 i 为
终点的结点个数为顶点 i 的入度。
时间和空间复杂度O(n+e)

const int MaxSize = 10;
struct EdgeNode//边表结点结构体

    int adjvex;//该顶点的邻接点在顶点表中的下标
    EdgeNode *next;
;
struct VertexNode//顶点表结点结构体

    int vertex;//存放顶点信息
    EdgeNode *firstEdge;//指向边表的第一个结点
;
int visited[MaxSize];
class ALGraph

public:
    ALGraph(int a[], int n, int e); //构造函数，建立n个顶点e条边的图
    ~ALGraph();
    void DFSTraverse(int v); //深度优先遍历图
    void BFSTraverse(int v); //广度优先遍历图
private:
    VertexNode adjlist[MaxSize]; //存放顶点表的数组
    int vertexNum,edgeNum;//顶点数和边数
;
ALGraph::ALGraph(int a[],int n,int e)

    int i,j,k;
    EdgeNode *s=NULL;
    vertexNum=n;
    edgeNum=e;
    for(i=0;i<vertexNum;i++)//初始化顶点表
    
        adjlist[i].vertex=a[i];
        adjlist[i].firstEdge=NULL;
    
    for(k=0;k<edgeNum;k++)
    
        cin>>i>>j;
        s=new EdgeNode;
        s->adjvex=j;
        s->next=adjlist[i].firstEdge;
        adjlist[i].firstEdge=s;//头插法
    

ALGraph::~ALGraph()

    EdgeNode *p=NULL,*q=NULL;
    for(int i=0;i<vertexNum;i++)
    
        p=q=adjlist[i].firstEdge;
        while(p!=NULL)
        
            p=p->next;
            delete q;
            q=p;
        
    

void ALGraph::DFSTraverse(int v)

    int j;
    EdgeNode *p=NULL;
    cout<<adjlist[v].vertex;
    visited[v]=1;
    p=adjlist[v].firstEdge; //工作指针p指向顶点v的边表
    while(p!=NULL)
    
        j=p->adjvex;
        if(visited[j]==0)
            DFSTraverse(j);
        p=p->next;
    

void ALGraph::BFSTraverse(int v)

    int w,j,Q[MaxSize];
    int front=-1,rear=-1;
    EdgeNode *p=NULL;
    cout<<adjlist[v].vertex;
    visited[v]=1;
    Q[++rear]=v;
    while(front!=rear)
    
        w=Q[++front];
        p=adjlist[w].firstEdge;
        while(p!=NULL)
        
            j=p->adjvex;
            if(visited[j]==0)
            
                cout<<adjlist[j].vertex;
                visited[j]=1;
                Q[++rear]=j;
            
            p=p->next;

vector实现邻接表

const int MaxSize = 10;
struct edge//边

    int from,to,w;//起点，终点，权值
    edge(int a,int b,int c)//对边赋值
    
        from=a;
        to=b;
        w=c;
    
;
vector<edge>e[MaxSize];//e[i]存第i个结点连接的所有边。
for(int i=1;i<=n;i++)//初始化
    e[i].clear();
e[a].push_back(edge(a,b,c));//存边
for(int i=0;i<e[u].size();i++)//检索结点u的所有邻居

    ...

3.链式前向星

例题

链式前向星存图如下：u表示结点，h[u]用来定位u的第一条边，t[i].to存u的邻居结点，t[i].next定位u的下一个邻居结点。例如：u=7时，h[u]=12，即结点7的第一条边连接的邻居结点存在i=12这个位置，t[12].to=6，表示结点7的第一个邻居是结点6，t[12].next=10,即结点7的第二条边连接的邻居结点存在i=10这个位置里，t[10].to=5，即结点7的第二个邻居结点是5，依次类推，直到t[i].next=0时停止。

const int N=16000;
struct n

    int to,next, w;
t[2*N];
int h[2*N],p=1;
void add(int u,int v,int w)

    t[p].to=v;
    t[p].w=w;
    t[p].next=h[u];
    h[u]=p++;

//遍历结点i的所有邻居
for(int  i=h[u];i;i=t[i].next)
...

三、最小生成树

生成树： 包含图所有顶点的极小连通子图
生成树的代价： 生成树上各边的权值之和称为生成树的代价。
最小生成树： 生成树中代价最小的。

1.prim算法

此方法对点进行贪心操作，设所有结点集合为V，再另设一个集合U用来存最小生成树的结点。从任一点v开始，把离它最近的结点u1加入到集合U中，再从剩下的集合V-U中找到离U中某一结点最近的u2，把加到集合U中，继续上述过程直到U中加满所有结点。如下图，蓝色结点表示已经加入U中的结点，绿色表示正在比较的边。

设数组adjvex[n]存结点，lowcost[n]存每个结点最短边权值，lowcost[v]=0表示顶点v已加入最小生成树中（加入到U中）。
怎么把点加入到集合U中呢？是每一次都把V-U中的所有结点与U中所有结点相连的边都比较一遍吗？你会发现每一次比较都会有重复比较的边，极浪费时间。怎么办呢？
聪明的你一定想到了动态规划，不过这里不用DP数组来实现。我们考虑最初把已知结点v加入到集合U中，lowcost[v]=0，表示v到v的最短边为0，其余结点的最短边在没有比较的情况下都假定最短边是与结点v相连，即adjvex[i]=v，每个结点对应最短边lowcost[i]等于结点i与v的边的权值，这就是初始化。
接下来加点到U中，我们找V-U中所有结点到结点v的边中权值最小的，把对应的结点j1加入集合U中，代码对应就是找到当前lowcost数组中最小的lowcost[j]，让其等于0；因为集合U的改变，V-U中到U中结点的最短边可能会改变，集合V-U结点最短边对应的邻接点也可能会变，需要更新两个数组。U中目前已经有结点j1，v，集合V-U中的任何一个结点到集合U

数据结构与算法学习笔记图(代码片段)

数据结构与算法学习笔记(8)图复习文章目录数据结构与算法学习笔记(8)图一.图的定义和基本术语二.图的类型定义三.图的存储结构1.邻接矩阵无向图的邻接矩阵有向图的邻接矩阵网(有权图)邻接矩阵的存储表示创建邻接矩阵(以无... 查看详情

深入浅出图神经网络|gnn原理解析☄学习笔记表示学习(代码片段)

深入浅出图神经网络|GNN原理解析☄学习笔记（四）表示学习文章目录深入浅出图神经网络|GNN原理解析☄学习笔记（四）表示学习表示学习表示学习的意义离散表示与分布式表示端到端学习基于重构损失的方法—... 查看详情

图学习笔记(11.25)(代码片段)

图学习笔记（一）图一、有向无环图及其应用1.AOV网与拓扑排序2.AOE网与关键路径事件的最早发生时间ve[k]事件的最迟发生时间vl[k]活动的最早开始时间e[i]活动的最晚开始时间l[i]一、有向无环图及其应用1.AOV网与拓扑排序AO... 查看详情

《深入浅出图神经网络》gnn原理解析☄学习笔记图的概述(代码片段)

《深入浅出图神经网络》GNN原理解析☄学习笔记（一）图的概述文章目录《深入浅出图神经网络》GNN原理解析☄学习笔记（一）图的概述图的基本定义图的基本类型邻居和度子图与路径图的存储与遍历邻接矩阵和... 查看详情

《深入浅出图神经网络》gnn原理解析☄学习笔记神经网络基础(代码片段)

《深入浅出图神经网络》GNN原理解析☄学习笔记（二）神经网络基础文章目录《深入浅出图神经网络》GNN原理解析☄学习笔记（二）神经网络基础机器学习基本概念机器学习分类机器学习流程概述常见的损失函数... 查看详情

unix环境高级编程学习笔记(代码片段)

目录图1-3ls命令简单实现图1-4从标准输入读，并向标准输出写图1.5跟图1.4功能差不多一样图1.6打印进程ID图1.7UNIX系统的进程控制功能简单的程序说明图1-3ls命令简单实现#include"apue.h"#include<dirent.h>intmain(intargc,char*argv[]... 查看详情

立创eda学习笔记——原理图绘制(代码片段)

一、画布设置1.1画布属性点击空白区可在右边属性面板查看和修改画布属性，或者鼠标右击空白区打开属性弹窗进行修改。画布属性内的参数均可以被自行配置。网格和栅格尺寸单位为像素(pixel)。1.2多页原理图立创EDA一个工... 查看详情

数据结构学习笔记——图的基本知识(代码片段)

目录一、图的结构二、图的定义（一）有向图和无向图1、无向图和无向完全图2、有向图和有向完全图（二）度的概念1、无向图的度2、有向图的度（三）路径、路径长度和简单路径（四）回路和简... 查看详情

数据结构学习笔记——图的基本知识(代码片段)

目录一、图的结构二、图的定义（一）有向图和无向图1、无向图和无向完全图2、有向图和有向完全图（二）度的概念1、无向图的度2、有向图的度（三）路径、路径长度和简单路径（四）回路和简... 查看详情

《深入浅出图神经网络》gnn原理解析☄学习笔记卷积神经网络(代码片段)

《深入浅出图神经网络》GNN原理解析☄学习笔记（三）卷积神经网络文章目录《深入浅出图神经网络》GNN原理解析☄学习笔记（三）卷积神经网络卷积与池化信号处理中的卷积单通道卷积多通道卷积池化卷积神经... 查看详情

nebulagraph数据库学习笔记(代码片段)

NebulaGraph是一款开源的、分布式的、易扩展的原生图数据库，能够承载数千亿个点和数万亿条边的超大规模数据集，并且提供毫秒级查询。一、图数据库简介图数据库是以点、边为基础存储单元，以高效存储、查询图... 查看详情

nebulagraph数据库学习笔记(代码片段)

NebulaGraph是一款开源的、分布式的、易扩展的原生图数据库，能够承载数千亿个点和数万亿条边的超大规模数据集，并且提供毫秒级查询。一、图数据库简介图数据库是以点、边为基础存储单元，以高效存储、查询图... 查看详情

深入浅出图神经网络|gnn原理解析☄学习笔记图信号处理与图卷积神经网络(代码片段)

深入浅出图神经网络|GNN原理解析☄学习笔记（五）图信号处理与图卷积神经网络文章目录深入浅出图神经网络|GNN原理解析☄学习笔记（五）图信号处理与图卷积神经网络矩阵乘法的三种形式图信号与图的拉普拉... 查看详情

《python深度学习》第五章-6（可视化类激活图）读书笔记(代码片段)

《Python深度学习》第五章-6（可视化类激活图）读书笔记卷积神经网络学到的表示非常适合可视化，很大程度上是因为它们是视觉概念的表示\\colorred视觉概念的表示视觉概念的表示。接下来介绍3种可视化方法。事中\\... 查看详情

设计模式-学习笔记-uml统一建模语言-类图classdiagram(代码片段)

设计模式-学习笔记-UML统一建模语言-类图ClassDiagram类图关系类型1.依赖关系Dependency参考资料类图由于是学习设计模式的准备工作，这里只是学习了一下UML中的类图关系类型classDiagramclassA--|>classB:继承classC--*classD:classC_1...class... 查看详情

51单片机学习笔记3--按键输入检测(代码片段)

学习输出控制之后，学习输入检测，以按键为例按键检测1.按键原理图绘制2.按键输入检测1.按键软件消抖2.按键操作电平变化3.按键检测编程4.实验结果3.按键控制4.课外科普--硬件消抖1.按键原理图绘制51开发板的原理图如... 查看详情

repuest转发学习笔记一(代码片段)

学习图：Java代码importjava.io.IOException;importjava.io.InputStream;importjava.util.Properties;importjavax.servlet.ServletException;importjavax.servlet.http.HttpServlet;importjavax.servlet.http.HttpServletR 查看详情

电子电路学习笔记——电容(代码片段)

一、电容的作用旁路去藕滤波储能二、电容的符号①：固定电容（没有极性）。②-⑥：都是有极性的电容。钽（tan，三声）电容，常用图②，铝电容（上述实物图的贴片电容中的圆柱电容&#x... 查看详情