有向图和无向图的相关概念

我就是我 2024-05-01 16:01 90阅读 0赞

图的定义:

图在数据结构中是中一对多的关系，一般分为有向图与无向图

常用 邻接矩阵 或者 邻接链表 来表示图中结点的关系

⑴图是由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构  
　　⑵用二元组定义为：G=（V,E）。

例如：

![format_png][]

对于图7-1所示的无向图G1和有向图G2，它们的数据结构可以描述为：

G1=(V1,E1)， 其中 V1=\{a,b,c,d\},E1=\{(a,b),(a,c),(a,d),(b,d),(c,d)\},  
　　 G2=(V2,E2)，其中 V2=\{1,2,3\}, E2=\{<1,2>,<1,3>,<2,3>,<3,1>\}。

有向图与无向图

⑴在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。

如图7-1中:  
　　　　　　①G1为无向图， ②G2 为有向图。  
　　　　⑵在无向图中:一条边（x,y）与（y,x）表示的结果相同，用圆括号表示，  
　　　　⑶在有向图中:一条边<x,y>与<y,x>表示的结果不相同，故用尖括号表示。<x,y>表示从顶点x发向顶点y的边，x为始点，y为终点。  
　　　　⑷有向边也称为弧，x为弧尾，y为弧头,则<x,y>表示为一条弧, 而<y,x>表示y为弧尾，x为弧头的另一条弧 。

完全图/稠密图/稀疏图：

⑴具有n个顶点，n(n-1)/2条边的图，称为完全无向图，  
　　⑵具有n个顶点，n(n-1) 条弧的有向图,称为完全有向图。  
　　⑶完全无向图和完全有向图都称为完全图。  
　　⑷对于一般无向图，顶点数为n，边数为e，则 0≤e ≤n(n-1)/2。  
　　⑸对于一般有向图，顶点数为n，弧数为e， 则 0≤e≤n(n-1) 。  
　　⑹当一个图接近完全图时，则称它为稠密图，  
　　⑺当一个图中含有较少的边或弧时，则称它为稀疏图。

度/出度/入度：

⑴在图中，一个顶点依附的边或弧的数目，称为该顶点的度。

⑵在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。

⑶一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。

⑷若图中有n个顶点，e条边或弧，第i个顶点的度为di，则有 e=1/2 \* Σ(1<= i <= n, di)

子图

⑴若有两个图G1和G2， G1=(V1,E1)， G2=(V2,E2)， 满足如下条件：  
V2⊆V1 ，E2⊆ E1，即V2为V1的子集，E2为E1的子集，则 称图G2为图G1的子图。  
  
![format_png 1][]

权：  
⑴在图的边或弧中给出相关的数，称为权。  
⑵权可以代表一个顶点到另一个顶点的距离，耗费  
等，带权图一般称为网。

一个图由多个结点以及边组成。

无向图例子：

![format_png 2][]

有向图例子：

![format_png 3][]

从上述例子中可以看出，一个图表是由数个顶点和边组成的。

其中，无向图的边是没方向的，即两个相连的顶点可以互相抵达。

而有向图的边是有方向的，即两个相连的顶点，根据边的方向，只能由一个顶点通向另一个顶点。（当然，如有向图例子中的2和3，由于有两个指向对方的方向，所以2和3是互通的。）

#### 完全图 ####

连通图：如果一个无向图从每一个顶点到其他顶点都存在一条路径，则称该无向图为连通图

强连通图：具有这样的性质的有向图称为是强连通的，如果不是强连通的，

弱连通图：它的基础图，即去掉弧上的方向所形成的的图，是连通的，那么该有向图称为弱连通的

完全无向图：具有n个顶点，并具有n(n - 1)/2 条边的图，称为完全无向图（每个顶点到其他顶点都有边），连通图

完全有向图：具有n个顶点，并且具有n(n - 1) 条边的有向图，称为完全有向图（每个顶点到其他顶点都有相互两条边），强连通图

完全图：完全无向图和完全有向图都称为完全图

#### 邻接矩阵 ####

定义：  
设无向图G=(V,E)G=(V,E),其中顶点集V=v0,v1,v2,...,vnV=v1,v2,...，边集E=e0,e1,e2,...,eεE=e1,e2,...,eε。用aijaij表示顶点vivi与顶点vjvj之间的边数，可能取值为0,1,2,…，称所得矩阵A=A(G)=(aij)n×nA=A(G)=(aij)n×n为图G的邻接矩阵

性质：

![20200429153733584.png][]

类似地，有向图D的邻接矩阵A(D)=(aij)n×nA(D)=(aij)n×n, aijaij表示从始点vivi到终点vjvj的有向边的条数，其中vivi和vjvj为D的顶点

示例，求图所示简单图的邻接矩阵？

![20180129144803129][]

解：根据定义，可求得该无向图的邻接矩阵为

![20200429153830798.png][]

注：邻接矩阵是描述图的一种常用的矩阵表示。

#### 关联矩阵 ####

定义：  
设任意图G=(V,E)G=(V,E)，其中顶点集V=v1,v2,...,vnV=v1,v2,...,vn，边集E=e1,e2,...,eεE=e1,e2,...,eε。用mijmij表示顶点vivi与边ejej关联的次数，可能取值为0,1,2,…，称所得矩阵M(G)=(mij)n×εM(G)=(mij)n×ε为图G的关联矩阵

类似地，有向图DD的关联矩阵M(D)=(mij)n×εM(D)=(mij)n×ε的元素mi×jmi×j定义为：

![20200429153955860.png][]

示例，求图中有向图的邻接矩阵和关联矩阵

![20180129144434923][]

解：根据定义，可求得该有向图的邻接矩阵:

![20200429154109432.png][]

关联矩阵:

![20200429154126776.png][]

注：关联矩阵是描述图的另一种矩阵表示。

参考地址：

[邻接矩阵与关联矩阵\_关联矩阵和邻接矩阵\_hukai7190的博客-CSDN博客][hukai7190_-CSDN]

[有向图和无向图以及拓扑的复习\_无向拓扑图的初始状态\_legendaryhaha的博客-CSDN博客][legendaryhaha_-CSDN]

[https://www.cnblogs.com/schips/p/10632250.html][https_www.cnblogs.com_schips_p_10632250.html]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTI4MTUyMy8yMDE5MDMvMTI4MTUyMy0yMDE5MDMzMTE3MjYwMzAwMi0xODQzMzM4MTkxLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTI4MTUyMy8yMDE5MDMvMTI4MTUyMy0yMDE5MDMzMTE3MzYwMzk5OC0xMjc3MDE3MzgwLnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTUzNDc4My8yMDE5MDEvMTUzNDc4My0yMDE5MDEyMTExNDUwMjA1Ny0yMjEwNzQxNTgucG5n?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTUzNDc4My8yMDE5MDEvMTUzNDc4My0yMDE5MDEyMTExNDU1NTcwMy04MjQ4MTM1MTQucG5n?x-oss-process=image/format,png
[20200429153733584.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/232657aea7864beeadd531de771d6d9e.png
[20180129144803129]: https://img-blog.csdn.net/20180129144803129
[20200429153830798.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/121d6ae586754ea982cee07e5d3a3e0a.png
[20200429153955860.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/79189b8272b940f993e3b64c42e3bde2.png
[20180129144434923]: https://img-blog.csdn.net/20180129144434923
[20200429154109432.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/9ff09d2eecb749f38ded37ab10741ac8.png
[20200429154126776.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/01/f81995a6e12b497297fede34bbf2d375.png
[hukai7190_-CSDN]: https://blog.csdn.net/Hanging_Gardens/article/details/55670356
[legendaryhaha_-CSDN]: https://blog.csdn.net/legendaryhaha/article/details/83049101
[https_www.cnblogs.com_schips_p_10632250.html]: https://www.cnblogs.com/schips/p/10632250.html