图结构算法学习（一）

定义：有向图是一副具有方向性的图，是有一组顶点和一组有方向的边组成的，每条方向的边都连接着一对有序的顶点。 全部由无向边构成图称为无向图

出度：有某个顶点指出的边的个数称为该顶点的出度。 入度：指向某个顶点的边的个数称为该顶点的入度。 度：入度+出度，称为该顶点的度。 注意：自环（起点和终点为同一顶点），此时出度算一度，入度也算一度。

如上图所示，顶点A的出度为2，入度为1，度为3

有向边：一条有向边的第一个顶点称为它的头，第二个顶点称为它的尾。将有向边画为由头指向尾的一个箭头。 有向环：一条至少含有一条边，且起点和终点相同的有向路径。 有向路径：由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列中的下一个顶点。 注意：一副有向图中两个顶点v和w可能存在以下四种关系： 1：没有边相连； 2：存在从v到w的边v->w; 3：存在从w到v的边w->v; 4：即存在w到v的边，也存在v到w的边，即双向链接；

设图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=（V，E）有n个顶点，则顶点表为

图的邻接矩阵是一个二位数组A.arcs[n][n]，定义为：

 A.  arcs ⁡ [ i ] [ j ] = { 1 ,  如果  ⟨ i , j ⟩ ∈ E  或者  ( i , j ) ∈ E 0 ,  否则  \text { A. } \operatorname{arcs}[i][j]= \begin{cases}1, & \text { 如果 }\langle i, j\rangle \in E \text { 或者 }(i, j) \in E \\ 0, & \text { 否则 }\end{cases}  A. arcs[i][j]={1,0,​ 如果 ⟨i,j⟩∈E 或者 (i,j)∈E 否则 ​

分析1：无向图的邻接矩阵是对称的； 分析2：顶点i的度=第i行（列）中1的个数； 注：完全图的邻接矩阵中，对角元素为0，其余1。

第i行含义：以结点vi为尾的弧（即出度边）； 第i列含义：以结点vi为头的弧（即入度边）。

分析1：有向图的邻接矩阵可能是不对称的； 分析2：顶点的出度 = 第 i 行元素之和 顶点的入度 = 第 i 列元素之和 顶点的度 = 第 i 行元素之和 + 第 i 列元素之和

加权后的邻接矩阵定义为：  A.  arcs ⁡ [ i ] [ j ] = { W i j < v i , v j >  或  ( v i , v j ) ∈ V R ∞  无边  (  弧  ) \text { A. } \operatorname{arcs}[\mathrm{i}][\mathrm{j}]=\left\{\begin{array}{cc} \mathrm{W}_{\mathrm{ij}} & \text { 或 }(\mathrm{vi}, \mathrm{vj}) \in \mathrm{VR} \\ \infty & \text { 无边 }(\text { 弧 }) \end{array}\right.  A. arcs[i][j]={Wij​∞​ 或 (vi,vj)∈VR 无边 ( 弧 )​

如上图所示，矩阵中的“1”变为了相应边的权值。而“0”变为了“∞”

用两个数组分别存储顶点表和邻接矩阵

【算法思想】 （1）输入总顶点数和总边数。 （2）依次输入点的信息存入顶点表中。 （3）初始化邻接矩阵，使每个权值初始化为极大值。 （4）构造邻接矩阵。

本文参考以下博客： 有向图和无向图，SuperiorPluto. 【图结构专题】有向图，惜暮. 邻接矩阵，diviner_s.