精华内容
下载资源
问答
  • 有向图和无向图

    万次阅读 多人点赞 2019-04-13 18:51:19
    有向图和无向图是我们常用到的术语,本文属于简单的科普帖。 全部由无向边构成图称为无向图(Undirected Graph),全部由有向边构成图称为无向图(Directed Graph)。有向,顾名思义,有方向。本文中顶点Vertex(V)...

    有向图、无向图

    有向图和无向图是我们常用到的术语,本文属于简单的科普帖。

    全部由无向边构成图称为无向图(Undirected Graph),全部由有向边构成图称为有向图(Directed Graph)。有向,顾名思义,有方向。本文中顶点Vertex(V),边Edge(E)

    (1)出度和入度:如图D,以点A为例子,在所有与A关联的边中,以A为起点的边的条数称为出度。而入度则刚好相反,以A为终点的边的条数则称为入读。其中,入度+出度,我们称为A的度。注意特殊情况:如图:A有一个自环,起点和终点都是自己,此时出度算一度,入度也算一度。如图:A的出度为3,入度也为2,A的度的5。

    在这里插入图片描述
    (2)描述图的邻接矩阵和关联矩阵
    【邻接矩阵】

    定义:
    设无向图G=(V,E),其中顶点集V=v1,v2,…,vn,边集 E=e1,e2,…,eε。用aij表示顶点vi与顶点vj之间的边数,可能取值为0,1,2,…,称所得矩阵A=A(G)=(aij)n×n为图G的邻接矩阵。邻接矩阵可以描述有向图和无向图。

    示例,求图所示简单图的邻接矩阵?
    在这里插入图片描述
    解:根据定义,可求得该无向图的邻接矩阵为
    在这里插入图片描述

    邻接矩阵的存储特点:
    (a)无向图的邻接矩阵一定是一个对称矩阵,有向图不一定是。
    *(b)邻接矩阵所需的存储空间值域只与顶点数有关系。
    (c)用邻接矩阵存储图,容易判断两个点之间是否有边。
    (d)如果一个有向图的邻接矩阵为三角矩阵(主对角线为0),则它的拓扑排序一定存在。
    *(e)小技巧:
    无向图:邻接矩阵的第i行或者第i列的非零元素的个数正好是第i个顶点Vi的度;
    有向图:邻接矩阵的第i行的非零元素个数正好是第i个顶点Vi的出度,第i列非零元素的个数正好是第i个顶点Vi的入度。

    【关联矩阵】

    定义:
    设任意图G=(V,E),其中顶点集V=v1,v2,…,vn,边集E=e1,e2,…,eε。用mij表示顶点vi与边ej关联的关系,可能取值为0,1,-1,称所得矩阵M(G)=(mij)n×ε为图G的关联矩阵。
    在这里插入图片描述
    mij 表示i行j列,探究顶点Vi和边Ej之间的关系,形成下列的关联矩阵
    示例:
    在这里插入图片描述
    关联矩阵
    在这里插入图片描述

    连通图、连通分量

    连通图:无向图中,若从顶点u到顶点v有路径,称为u,v是连通的。若图中任意两个顶点均是连通的,则称为连通图。
    连通分量:无向图中极大连通子图称为连通分量。

    强连通图、强连通分量

    强连通图:有向图中,若从顶点u到顶点v有路径,称为u,v是连通的。若图中任意两个顶点均是连通的,则称为强连通图。
    连通分量:无向图中极大连通子图称为强连通分量。特:强连通图只有强连通分量(本身),非强连通图有多个强连通分量。

    另外,本文参考路了下面两位作者的优秀博客
    https://blog.csdn.net/Hanging_Gardens/article/details/55670356
    https://blog.csdn.net/legendaryhaha/article/details/83049101

    展开全文
  • 有向图和无向图以及拓扑的复习

    万次阅读 2018-10-14 17:43:36
    有向图和无向图的定义 1)关于有向图,百科中是这样描述的:一个有向图D是指一个有序三元组(V(D),A(D),ψD),其中ψD为关联函数,它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点...

    备注:大一学了图后,一段时间没用就还给老师了,如今重新复习一下,理解有误的地方请指教。


    有向图和无向图的定义

    1)关于有向图,百科中是这样描述的:一个有向图D是指一个有序三元组(V(D),A(D),ψD),其中ψD为关联函数,它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。
    理解:如图D,如果e是D的一条边,而这时候存在这样的一个关系,ψD,有A,B两点,使得,ψD(A,B)=e(到底是怎样的关系?我觉得在应用中,需要我们自己制定,就像在预算100元的条件下,你选择怎样的交通工具快速到达目的地),通俗理解:边有方向的图。即AB != BA。
    [外链图片转存失败(img-OHZsll7R-1567908307459)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483515239_C07BA5588B40E754EB534225BA630A0D “图片标题”)]


    (2)平行边:在图中,如果起点和终点相同则称为平行边,平行边的条数则称为重数。如图:e2和e3为平行边,B和C之间的重数为2。
    [外链图片转存失败(img-EMKaEUe6-1567908307460)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483671400_6DA66AE52EFE0CF2370DF02226877263 “图片标题”)]


    (3)关于无向图:了解了有向图,那它就好理解了,就是有向图中去掉所有的方向,AB=BA,如图,就是去掉D中的所有箭头(此时,又称为基础图,反之给无向图添上箭头的有向图又称为定向图)。
    [外链图片转存失败(img-DJM75Udh-1567908307461)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539483731056_5FB56EBF13116F56F22CCFD0F068F03B “图片标题”)]


    (4)出度和入度:如图D,以点A为例子,在所有与A关联的边中,以A为起点的边的条数称为出度。而入度则刚好相反,以A为终点的边的条数则称为入读。其中,入度+出度,我们称为A的度。注意特殊情况:如图:A有一个自环,起点和终点都是自己,此时出度算一度,入度也算一度。如图:A的出度为3,入度也为2,A的度的5。


    (5)邻接矩阵和关联矩阵定义:设D(V,E)是有向图,其中V={v1,v2,v2…vn},E={e1,e2,e3,…em}称A(D)=(aij)nxn是D的领接矩阵,其中aij是以vi为起始点,以vj为终点的边的条数。若图D中无环,则称M(D)=(mij)nxm为关联矩阵。[i,j是下标,n是点的个数,m是边的数量注意:1.关联矩阵是针对边来说的,所以矩阵大小为n*m,它的取值如下:

    图片来源于百科
    例子:
    图片来源于百科
    (6)补充:对于无向图而言:邻接矩阵则是对称的,且只有0和1,因为没有方向的区别后,要么有边,要么没边:
    在这里插入图片描述
    从图我们可以看到,它是关于对角线对称的一个矩阵,我们在编程中,遍历和存储是只需要关注上半部分或者下半部分即可。
    在这里插入图片描述


    (7)跟邻接矩阵一样,用来存储图中信息的,还有邻接表:如果学过链表了,就很好理解了,首先在一个数组中存储各个点(对象或者成为链),而每个对象又保存着一个next引用指向连接的点在数组中的坐标,如图:A到E在数组中存储后,坐标依次排列,A连B,B的坐标为1,所以指向的地方标记为1,代表A连着B,接着,B连着E,E的坐标为4,这1的引用指向4。

    从图我们就可以得出邻接表的存储方式了:即链表加数组,这存储结构比起纯粹用数组(邻接矩阵)要节约很多空间。邻接矩阵,我们需要一个n*n维的数组,复杂度为O(n^2),而邻接表是根据点和边来保存数据的,当一个起点决定后,就采用深度搜索的方法沿着边,保存连接点的信息,复杂度为O(n+m)

    另外,若果是有向图,我们在保存下一个顶点时,还需要保存边的权值,看图中每个格子都分成两小格了吗,第二个小格子就是用来存储权值的。

    图来自百度词条,好难画
    在这里插入图片描述


    拓扑排序

    百度词条这样描述:对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。
    理解:(1)根据定义,我们可以知道它是针对有向图而言的.(2)它是一个包含有向图的所有点的线性序列,且满足两个条件:a.有向图的每个顶点只出现一次。b.若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 应该出现在顶点 B 的前面。

    备注:图来源于百度,之前都没发现,它的786,应该是678,C0是连着C2和C6的
    [外链图片转存失败(img-q5yfBWrf-1567908307464)(https://uploadfiles.nowcoder.com/images/20181014/443077457_1539485618410_F203E6F40B767104E9635E84C103CA7C “图片来源于百科”)]

    (2)注意,拓扑排序并不是唯一的,它的排序方式:以上图为例子:a.首先我们从有向图图中选择一个没有前驱(即入度为0)的顶点并输出,这里我们可以选择c0或者c1。b.从图中删除输出的顶点和所有以它为起点的有向边。c.循环 a步骤 和 b步骤,终止条件为当前的有向图为空或当前图中不存在无前驱的顶点为止。备注:若当前图中不存在无前驱的顶点,说明有向图中必然存在环。


    展开全文
  • 判断无向图和有向图是否有回路

    万次阅读 多人点赞 2014-03-06 00:22:47
     对于无向图,判断其是否回路两种方法,如下所示:  1、利用深度优先搜索DFS,在搜索过程中判断是否会出现后向边(DFS中,连接顶点u到它的某一祖先顶点v的边),即在DFS对顶点进行着色过程中,若出现所指向的...

    一、无向图回路的判断

        对于无向图,判断其是否有回路有四种方法,如下所示:

        1、利用深度优先搜索DFS,在搜索过程中判断是否会出现后向边(DFS中,连接顶点u到它的某一祖先顶点v的边),即在DFS对顶点进行着色过程中,若出现所指向的顶点为黑色,则此顶点是一个已经遍历过的顶点(祖先),出现了后向边,若完成DFS后,则图中有回路;

        2、在图的邻接表表示中,首先统计每个顶点的度,然后重复寻找一个度为1的顶点,将度为1和0的顶点从图中删除,并将与该顶点相关联的顶点的度减1,然后继续反复寻找度为1的,在寻找过程中若出现若干顶点的度都为2,则这些顶点组成了一个回路;否则,图中不存在回路。

        3、利用BFS,在遍历过程中,为每个节点标记一个深度deep,如果存在某个节点为v,除了其父节点u外,还存在与v相邻的节点w使得deep[v]<=deep[w]的,那么该图一定存在回路;
        4、用BFS或DFS遍历,最后判断对于每一个连通分量当中,如果边数m>=节点个数n,那么改图一定存在回路。因此在DFS或BFS中,我们可以统计每一个连通分量的顶点数目n和边数m,如果m>=n则return false;直到访问完所有的节点,return true。

    二、有向图回路的判断

        对于有向图,判断其是否有回路的方法也有两种,如下所示:

        1、与无向图类似,若在DFS中出现后向边,即存在某一顶点被第二次访问到,则有回路出现;

        2、同样,利用拓扑排序的思想,通过这一步骤来执行拓扑排序,即重复寻找一个入度为0的顶点,将该顶点从图中删除,并将该顶点及其所有的出边从图中删除(即与该点相应的顶点的入度减1),最终若途中全为入度为1的点,则这些点至少组成一个回路。

        对于有向图,具体点就可得到如下分析:

        问题分析:如果图中存在回路,则必包含一个子图为回路。即该子图中所有顶点入度不为0且至少有边指向另外的顶点。
        算法:
        步骤1:按邻接表方式存储图。遍历与每个节点关联的边并统计每个节点的入度。需要O(n+m)次的运算。
        步骤2:删除所有入度为零的顶点及其相发出的边。并将被删除边所指向的顶点的入度减1。
        重复步骤2直到:
        (1)所有顶点被删除(则没有回路)或;
        (2)还有顶顶点但没有入度为零的顶点可删除(则存在回路)。
        算法复杂度分析:
        由于步骤二中的删除边的操作运算复杂度为O(m),删除节点的操作为O(n) 判断节点入度是否为0需要O(n+m)次运算。其中O(n)次为初始入度为零的节点,O(m)次为删除边后导致的入度为零的节点。于是整个算法复杂度为O(m+n)。

    展开全文
  • 23.有向图和无向图

    千次阅读 2017-09-04 20:29:24
    无向图的邻接表 有向图的邻接表 无向图的邻接矩阵 有向图的邻接矩阵

    无向图的邻接表



    有向图的邻接表


    无向图的邻接矩阵


    有向图的邻接矩阵


    展开全文
  • 有向图和无向图差别就是一句代码的差别 ,无向图中代码注释掉即可 有向图和有向网的差别也就是权值的差别 有向网需要赋予权值 有向图有连线自动赋值为1 深度优先采用递归方法(参考前面几篇文章,里面有具体的...
  • 判断无向图/有向图中是否存在环

    千次阅读 2019-02-03 11:54:50
    本文主要针对如何判断有向图/无向图中是否存在环的问题进行简单的论述。 一 无向图 1.利用DFS进行判断 利用DFS判断有向图是否存在环,是最为常用的一种方法,虽然这种方法很常用,但可参考的代码的实现比较少,...
  • matlab 绘制有向图无向图、有权有向图、有权无向图1、Matlab作无权无向图2、Matlab作有权无向图3、Matlab作无权有向图4、Matlab作有权有向图 1、Matlab作无权无向图 % 函数graph(s,t):可在 s t 中的对应节点...
  • 由邻接矩阵画有向图无向图

    万次阅读 2017-07-19 10:39:08
    由邻接矩阵画有向图无向图 由邻接矩阵画有向图的逻辑如下: 设邻接矩阵的行(列)数为N,矩阵中非零元素的个数为M,画布宽为W、高为H 1、有向图顶点数为N、有向边数为M,问题转化为:画正N边形的所有顶点、以及顶点...
  • 有向图和无向图的相关概念

    千次阅读 2020-04-29 15:44:42
    图的定义:  图在数据结构中是中一对多的关系,一般分为无向图无向图  常用 邻接矩阵 或者 邻接链表 来...对于图7-1所示的无向图G1和有向图G2,它们的数据结构可以描述为:  G1=(V1,E1), 其中 V1={a,b,c,d...
  • Gephi画无向图和有向图(显示节点和边序号) 数据形式 如果画无向图只要把Type这一列设置成undirected,不填入数据默认是directed 导入数据以后就可以设计节点以及边的属性了,如下: 显示的有向图如下: ...
  • c语言实现数据结构中有向图和无向图邻接表的建立、插入、删除操作
  • 有向图和无向图区别: 三:简单图 1.定义 2.图形化解释 四:完全无向图 1.定义 2.图形化解释 五:有向完全图 1.定义 2.图形化解释 一:无向图 1.定义 若顶点到之间的边没有方向,则称这条边为无向边...
  • 在解决实际问题的过程中我们经常需要将有向图(directed graph)转化成一个与之对应的无向图(undirected graph),但是相同结构的有向图和无向图能够表达的变量间的独立性是不同的,如何将一个有向图转化成一个无向...
  • 用邻接链表存储无向图和有向图

    千次阅读 2017-04-08 09:48:44
    上一篇文章我们说到用邻接矩阵存储有向图和无向图,这种方法的有点是很直观的知道点与点之间的关系,查找的复杂度是为O(1)。但是这种存储方式同时存在着占用较多存储空间的问题, 邻接矩阵存储很好理解,但是,有...
  • 有向图和无向图用邻接矩阵储存

    万次阅读 多人点赞 2017-04-08 09:15:47
    一般存储图的方式两种:一是用邻接矩阵表示,二是用邻接链表。 所谓用邻接矩阵,是用一个二维数组存储,边使用矩阵来构建模型,...无向图的边的矩阵一定是一个对称矩阵,因为无向图只关心边是否存在,而不关心方向,
  • 有向图无向图判断有环

    万次阅读 多人点赞 2015-11-17 12:38:59
    最近开始认真学习算法,用的是...而判断环问题又分为有向图无向图,我会分别对无向图和有向图判断环问题进行阐述,然后比较他们之间的不同. 首先介绍一下无向图,无向图的边没有方向,或者说每一条无向图的边都是双
  • 没有找到原文出处,请参考一下链接: http://www.cnblogs.com/hiside/archive/2010/12/01/1893878.html ... 一、无向图: 方法1: 如果存在回路,则必存在一个子图
  • 20171124  图的概念: ... 图的无向图顶点的边数叫有向图顶点的边数叫出度入度 。  图的数据存储结构-邻接矩阵:  带权邻接矩阵表示法:  图的存储结构-邻接表  无向图的邻接表:  有向
  • 一、通路与回路 1、通路: 顶点与边的交替序列 2、起点, 终点, 通路长度 第一个点是起点,最后一个点是终点 ...复杂通路: 重复边的通路 复杂回路: 重复边的回路 初级通路(路径): 没有重复顶点...
  • 数据结构: 无向图和有向图的API

    千次阅读 2015-10-21 00:17:08
    可以多种方式表示无向图:邻接矩阵、边的数组、邻接表数组。邻接矩阵需要的空间为V^2,对于稀疏图(大部分情况下都是)太浪费了。 边的数组使用起来十分不方便,不能快速得到顶点v的邻接顶点。所以邻接表数组...
  • 图只有树边反向边,如果有反向边...有向图的code如下: #include #include #include const int maxn=1001; int vis[maxn]; int map[maxn][maxn]; int flag; int n,m; void input() { memset(vis,0,sizeof(vis));
  • //确定v1v2在G中的位置,即顶点数组的下标 int i=LocateVex(G, v1); printf("v1在G中的位置:%d\n", i); int j=LocateVex(G, v2); printf("v2在G中的位置:%d\n", j); G.arcs[i][j]=weight; G.arcs[j][i]=G....
  • 无权无向图、带权无向图的实现 java 邻接矩阵实现无权无向图、带权无向图 java 1.图的接口 import java.util.List; public interface Graph { public int getSize(); //返回图中的顶点数 public List getVertices();...
  • 无向图的割顶,桥构造双连通分量以及有向图的极大连通分量,相关概念看这里 http://www.byvoid.com/blog/biconnect/ 程序部分自己写,理论部分参考上方链接。 根据黑书上面的相关内容,无向图的tarjan算法大致...
  • 概率图模型之有向图无向图

    千次阅读 2016-06-12 20:32:18
    图模型用图结构描述随机变量之间的依赖关系,结点表示随机变量,边表示随机变量之间的依赖关系,可以是有向图和无向图。 一 无向图模型 无向图模型又叫马尔可夫网络、马尔可夫随机场,是关于一组有马尔可夫性
  • 网上查了很多资料,发现主要是使用邻接表来实现图,并进行遍历的。而采用邻接矩阵的就非常少...不想看的可以直接下载:python 邻接矩阵三种方法实现有向图无向图,并绘图显示不废话。上代码首先图类 class Graph_Matr
  • 有向图和无向图用邻接矩阵储存及代码实现

    万次阅读 多人点赞 2017-09-14 17:26:48
    一般存储图的方式两种:一是用邻接矩阵表示,二是用邻接链表。 所谓用邻接矩阵,是用一...1、无向图的存储:无向图的边的矩阵一定是一个对称矩阵,因为无向图只关心边是否存在,而不关心方向,V0V1边,那么V1V
  • 其中无向图结点(0,1,3)表示该节点为0,与其相邻的结点为13。 创建该图后根据邻接矩阵计算每个结点的,并输出。 文本输入 input_7_1.txt,每一组数据表示一个图,至少包含3个结点,第一行为节点个数,第二行...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 847,015
精华内容 338,806
关键字:

无向图和有向图的度