有向图和无向图_有向图的邻接矩阵怎么画「建议收藏」

有向图、无向图

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

全部由无向边构成图称为无向图（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

今天的文章有向图和无向图_有向图的邻接矩阵怎么画「建议收藏」分享到此就结束了，感谢您的阅读。