精选文章 图结构(Graph)

图结构(Graph)

作者:weixin_33994429 时间: 2010-03-25 04:05:00
weixin_33994429 2010-03-25 04:05:00

   定义:图可以理解由顶点集合V和边的集合E构成的一种数据结构
G=(V,E)。图的边可用括号括住两个顶点来表示,通常用圆括号
表示无向图的边,尖括号表示有向图的边。

    定义:与一个顶点有关的边的个数称为该顶点的度。对有向图的顶点
的度可进一步分为出度+入度,出度是指从该顶点出发的边数,入度是
指到达该顶点的边数。

    定义:路径中包含边的个数称为路径长度。

    定义:对于一个图,从Vi顶点出发有路径可达顶点Vj,则称顶点
Vi,Vj连通。对无向图,如果任何两个不同的顶点都连通,称为连通
图。对于有向图,如果任何两个顶点都连通则称为强连通图。

    定义:对于一个图如果对边赋以权值,则称这种边带权的图为网络。
在实际问题中边的权可理解为距离、代价、费用等。

    定义:若一个图的顶点和边都是另一个图的顶点和边的子集,也就是
说G2实际是G1的一部分,则称G2是G1的子图。

    图的存储结构:通常采用邻接矩阵表示顶点之间的关联,这种方法属
静态分配内存;另一种分配存储的方式是通过链式结构表示与顶点关联
的边表,这种方式称为邻接表。


定义图:1邻接矩阵表示
    矩阵的[i,j]元素为1表示(Vi,Vj)边存在,为0表示(Vi,Vj)边不存在。
CONST n=;
TYPE  adj=0..1;
      adjm=array[1..n,1..n] of adj;{邻接矩阵}
      graph=RECORD
            V:array[1..n] of Vtype;{顶点元素}
            E:adjm;
            END;
    邻接矩阵同样可以表示网络,对于网络可以直接在边的位置上填上权值,没有边的位
置可以认为权值为0或一个不可能的很大值MAX,为了简化表示可写为M。
        2用邻接表表示
    用邻接表表示图的结构,实际上邻接表由两个部分组成,一个是存储顶点数据元素的
顶点表,另一个是与顶点相关联的边表,对有向图边表还要再分为入边表和出边表。
TYPE Epinter=^enode;        {指向边表结点}
     enode=RECORD           {边表数据元素}
           adjv:1..n;       {顶点在顶点表中的位置}
           next:epinter;    {链接用指针}
           END;
     Vnode=RECORD           {顶点表数据元素}
           V:Vtype;         {顶点数据}
           LINK:Epinter;
           END;
     adjl=ARRAY[1..N] OF Vnode;
建立无向图结构的邻接表算法:
Procedure SCLJB(Var T:adjl);{生成无向图邻接表}
Begin
    for i:=1 to n do        {建立顶点表}
        read(T[i],V);
        T[i].link:=NIL;
    end for;
    for k:=1 to e do        {E为边数}
        read(i,j);          {读入边(Vi,Vj)}
        new(s);             {分配表边元素,S为Epinter类型}
        s^.adjv:=j;
        s^.next:=T[i].link;
        T[i].link:=s;       {顶点j作为Vi的边表元素}
        new(s);             {分配邻接于Vj的边表元素}
        s^.adjv:=i;
        s^.next:=T[j].link;
        T[j].link:=s;       {顶点i作为Vj的边表元素}
    end for;
End;
对连通图顶点的遍历算法:
    1连通图的深度优先遍历算法
Procedure DFS(i:1..n);         {从Vi开始深度优先遍历}
Begin{设Vflag--标记顶点的数组--和邻接表T调用时已知}
    write(T[i].V);             {访问Vi}
    Vflag[i]:=true;
    p:=T[i].link;              {沿边表向前一步}
    while p<>NIL do            {边表不完继续深度优先搜索遍历}
        if not Vflag[p^.adjv]  {边表找到的顶点没有访问过}
             then DFS(p^.adjv);{对找到的顶点继续深度优先遍历}
        end if;
        p:=p^.next;            {沿Vi的边表前进一步}
    end while;
End;
    2连通图的广度优先遍历算法
Procedure BFS(i:1..n);
Begin
    NULL(Q);       {队列Q初始化,用于保存优先搜索边表中顶点的序号}
    Write(T[i].V);         {访问Vi}
    Vflag[i]:=true;        {置Vi的访问标记}
    ENQU(Q,i);             {Vi进队列}
    while not EMPTY(Q) do  {队列不空进BFS}
        i:=DEQU(Q);        {从队列取顶点}
        p:=T[i].link;      {取边表指针}
        while p<>NIL do    {沿边表涉及顶点搜索}
            if not Vflag[p^.adjv]     {边表涉及顶点未被访问过}
               then
               write(T[p^.adjv].V);
               Vflag[p^.adjv]:=true;
               ENQU(Q.p^.adjv);       {访问的顶点进队列}
            end if;
        p:=p^.next;        {在边表中取下一个邻接边}
        end while;
    end while;
End;

转载于:https://my.oschina.net/RapidBird/blog/3402

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:B-树

下一篇:软件公司运营SaaS并非易事

您可能感兴趣

  • OpenCV 识别图片中的米粒个数,并计算米粒的平均面积和长度(转)

    介绍 OpenCV+Python 使用OpenCV构建图像识别算法,识别图片中的米粒个数,并计算米粒的平均面积和长度 软件架构 模块:OpenCV 4.0.0.21 编程语言:Python 3.7.2 编译器:PyCharm 2018 程序设计思路 首先介绍一下程序设计的思路: 图像采集(取到图像):可以用摄像头拍摄或者图片直接导入 图像预处理:对图像进行灰度化 基于灰度的阈值分割:使用局部...

  • JetPack WorkManager

    1.概览 官方文档:WorkManager 谷歌实验室:官方教程 官方案例:android-workmanager WorkManger介绍视频:中文官方介绍视频 谷歌工程师博客:https://medium.com/androiddevelopers/workmanager-basics-beba51e94048 Android JetPack实例学习:https://www.jiansh...

  • IntellIJ IDEA2020新功能

    一、java 1、Java 14支持:记录和模式匹配 IntelliJ IDEA 2020.1添加了对Java 14及其新功能的支持。IDE不仅添加了对Records的完整代码洞察支持,而且还使您能够快速创建新记录并生成其构造函数和组件,并警告存在的错误。您还将发现对instanceof运算符的模式匹配的支持,包括新的检查和快速修复,该快速修复通过用新的简洁模式变量替换它们来快速简化冗长的i...

  • 机器如何实现完全自主类人的学习方式?道翰天琼认知智能机器人API平台接口为您揭秘。

    机器如何实现完全自主类人的学习方式?道翰天琼认知智能机器人API平台接口为您揭秘。 本文作者来自东北大学,他通过整理自监督学习的一系列工作,把主流方法分成三大类,方便大家更全面的了解自监督学习的定义、方法、用途。与此同时,文中也穿插着几大主流方法的最新工作进展,现在正在探索自监督学习未来前景研究方向的同学,也不妨借鉴一二,说不定能找到灵感哦~ 1 学习的范式 我们首先来回顾下机器学习中两种基...

  • 什么是十字链表?

    十字链表是一种存储稀疏矩阵的方法,该存储方式采用的是 "链表+数组" 结构,如图1 所示。 图 1 十字链表示意图 可以看到,使用十字链表压缩存储稀疏矩阵时,矩阵中的各行各列都各用一各链表存储,与此同时,所有行链表的表头存储到一个数组(rhead),所有列链表的表头存储到另一个数组(chead)中。 因此,各个链表中节点的结构应如图 2 所示: 图 2 十字链表的节点结构 两个指针域分别用于...

  • 前端路 - Webpack

    概述 本质 JavaScript 应用程序的静态模块打包器 核心 加载器(Loader)机制 工作流程 配置初始化 webpack 会首先读取配置文件,执行默认配置 编译前准备 webpack 会实例化 compiler,注册 plugins、resolverFactory、hooks。 reslove 前准备 webpack 实例化 compilation、NormalModuleFact...

  • JAVA 集合框架简介

    1. JAVA 集合框架主要分三部分, set , list 和 Map (1)List 列表 特点:列表中的元素可重复, 元素有先后顺序 list 存储以及相关实现类, 如图: 继承list接口的类主要有 LinkedList, Vector, ArrayList。 其中 vector 和 ArrayList底层是数组结构,两者的区别在于 Vector中的方法使用了synchronized...

  • Java异常面试题(2020最新版)

    文章目录 Java异常架构与异常关键字 Java异常简介 Java异常架构 1. Throwable 2. Error(错误) 3. Exception(异常) 运行时异常 编译时异常 4. 受检异常与非受检异常 受检异常 非受检异常 Java异常关键字 Java异常处理 声明异常 抛出异常 捕获异常 如何选择异常类型 常见异常处理方式 直接抛出异常 封装异常再抛出 捕获异常 自定义异常 t...

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。