有向图和无向图
什么是图形?
图是一个集合节点和边缘它代表关系:
节点是与对象对应的顶点。
边缘是对象之间的连接。
图的边有时会权重,表示节点之间每个连接的强度(或其他一些属性)。
这些定义是通用的,因为图中节点和边的确切含义取决于特定的应用程序。例如,你可以用图表来模拟社交网络中的友谊。图的节点是人,边代表友谊。图与物理对象和情况的自然对应关系意味着您可以使用图对各种各样的系统建模。例如:
网页链接——图节点是网页,边表示页面之间的超链接。
机场——图节点是机场,边缘表示机场之间的航班。
在MATLAB®,图
和有向图
函数构造表示无向图和有向图的对象。
无向图有没有方向的边。这些边表示双向关系,因为每条边都可以在两个方向上遍历。该图显示了一个简单的无向图,有三个节点和三条边。
指示图有方向的边缘。这些边表示单向关系,因为每条边只能在一个方向上遍历。该图显示了一个简单的有向图,有三个节点和两条边。
在图形插图中,边缘的确切位置、长度或方向通常没有意义。换句话说,只要底层结构不变,通过重新排列节点和/或扭曲边缘,同一个图可以以几种不同的方式可视化。
自循环和多图
使用图
和有向图
可以有一个或多个吗self-loops,这些边是连接节点自身的边。此外,图可以具有具有相同源节点和目标节点的多条边,然后将图称为a油印。多图可以包含也可以不包含自循环。
对于MATLAB中的图算法函数而言,包含单个自环节点的图不是多图。但是,如果图中包含带有的节点多个自我循环,它是一个多图。
例如,下图显示了一个带有自环的无向多图。节点A有三个自循环,而节点C有一个。图包含这三个条件,其中任何一个都使它成为多图。
节点A有三个自环。
节点A和B之间有5条边。
节点A和C之间有两条边。
要确定给定的图是否是多图,请使用ismultigraph
函数。
创建图表
创建图的主要方法包括使用邻接矩阵或边表。
邻接矩阵
在图形中表示信息的一种方法是用正方形表示邻接矩阵。邻接矩阵中的非零表项表示两个节点之间的一条边,该表项的值表示这条边的权重。邻接矩阵的对角线元素通常为零,但非零的对角线元素表示a自身环,或者一个通过边与自身相连的节点。
当你使用
图
要创建无向图,邻接矩阵必须是对称的。在实践中,矩阵通常是三角形的,以避免重复。若要仅使用邻接矩阵的上三角形或下三角形构造无向图,请使用图(一个“上”)
或图(一个“低”)
。当你使用
有向图
要创建一个有向图,邻接矩阵不需要是对称的。对于大型图,邻接矩阵包含许多零,通常是一个稀疏矩阵。
不能从邻接矩阵创建多图。
例如,考虑这个无向图。
你可以用这个邻接矩阵来表示这个图:
在MATLAB中构造图形,输入:
A = [0 1 2];1 0 3;[30];Node_names = {“一个”,“B”,“C”};G = graph(A,node_names)
G =带属性的图:边:[3×2 table]节点:[3×1 table]
你可以使用图
或有向图
函数来使用邻接矩阵创建图形,也可以使用邻接
函数用于查找预先存在的图的加权或未加权稀疏邻接矩阵。
边列表
在图中表示信息的另一种方法是列出所有的边。
例如,考虑相同的无向图。
现在用边列表表示这个图
从边表中很容易得出图有三个唯一的节点,一个
,B
,C
,它们由列出的三条边连接起来。如果图中有断开连接的节点,则在边缘列表中找不到它们,并且必须单独指定。
在MATLAB中,边的列表被列分隔成源节点和目标节点。对于有向图,边缘方向(从源到目标)很重要,但对于无向图,源和目标节点是可互换的。使用边列表构建此图的一种方法是为源节点、目标节点和边权重使用单独的输入:
Source_nodes = {“一个”,“一个”,“B”};Target_nodes = {“B”,“C”,“C”};Edge_weights = [1 2 3];G = graph(source_nodes, target_nodes, edge_weights);
这两个图
和有向图
允许从边表构造简单图或多图。在构造了一个图之后,G
,您可以使用命令查看边缘(及其属性)G.Edges
。边的顺序G.Edges
按源节点(第一列)排序,其次按目标节点(第二列)排序。对于无向图,索引较小的节点被列为源节点,索引较大的节点被列为目标节点。
的底层实现图
和有向图
依赖于稀疏矩阵,许多相同的索引成本适用。使用前面的一种方法从三联体对一次构造一个图(来源、目标、重量)
比创建空图并迭代地添加更多节点和边要快。为获得最佳性能,请尽量减少对图
,有向图
,addedge
,addnode
,rmedge
,rmnode
。
图节点id
默认情况下,使用创建的图中的所有节点图
或有向图
已经屈指可数了。因此,您总是可以通过它们的数字来引用它们节点索引。
如果图有节点名(即,G.Nodes
包含一个变量名字
),然后您也可以使用它们的名称来引用图中的节点。因此,可以通过节点索引或节点名称来引用图中的已命名节点。例如,node1
可以称为,“一个”
。
这个词节点ID包含节点标识的两个方面。节点ID是指节点索引和节点名称。
为了方便起见,MATLAB会记住在调用大多数图函数时使用的节点ID类型。因此,如果你通过节点索引来引用图中的节点,大多数图函数都会返回一个数字答案,这个答案也会通过节点索引来引用节点。
A = [0 1 1 0];10 0 10 0;1 1 0 1;0 0 1 0];G =图(A,{“一个”,“b”,“c”,' d '});p = shortestpath(G,1,4)
P = 1 3 4
但是,如果按名称引用节点,那么大多数图函数返回的答案也按名称引用节点(包含在字符向量的单元数组中)。
p1 = short testpath(G,“一个”,' d ')
P1 = 1×3细胞数组{'a'} {'c'} {'d'}
使用findnode
查找给定节点名称的数字节点ID。相反,对于给定的数字节点ID,索引到G.Nodes.Name
以确定相应的节点名称。
修改或查询现有图形
在你构造一个图
或有向图
对象,则可以使用各种函数来修改图结构或确定图有多少个节点或边。该表列出了一些可用的修改或查询功能图
和有向图
对象。
addedge |
向图形添加一条或多条边 |
rmedge |
从图中删除一条或多条边 |
addnode |
向图中添加一个或多个节点 |
rmnode |
从图中删除一个或多个节点 |
findnode |
定位图中的特定节点 |
findedge |
定位图中的特定边 |
numnodes |
求图中节点的个数 |
numedges |
求图中边的个数 |
edgecount |
指定节点之间的边数 |
flipedge |
反转有向图边的方向 |
reordernodes |
调整图中节点的顺序 |
子图 |
提取子图 |
看到修改已有图的节点和边对于一些常见的图形修改示例。