数据结构——图结构

目录

一. 图的概述

1.1 图的基本概念

1.2 为什么要有图

1.3 几种常见图

1.4 图的基本术语

二. 图的存储结构

2.1 邻接矩阵

2.2 邻接矩阵表述形式

---

         图是较线性表和树更为复杂的数据结构，因此和线性表、树对节点的定义有所不同。在本章中主要是介绍图结构在计算机中的具体实现。     

---

一. 图的概述

1.1 图的基本概念

        图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。结点也可以称为顶点。

概念为：

        由顶点（Vertex）集和边( Edge）集组成， 记为G＝（V，E）,其中V 是有穷非空集合，称为顶点集，v ∈V称为顶点。E是有穷集合，称为边集， e∈E 称为边。

1.2 为什么要有图

1. 前面我们学了线性表和树
2. 线性表局限于一个直接前驱和一个直接后继的关系
3. 树也只能有一个直接前驱也就是父节点
4. 当我们需要表示多对多的关系时， 这里我们就用到了图

1.3 几种常见图

• 在图中，如果代表边的顶点对（或序偶）是无序的，则称为无向图。无向图中代表边的无序顶点对通常用圆括号括起来，用以表示一条无向边。如(i，j)表示顶点i与顶点j的一条无向边，显然，(i，j)和(j，i)所代表的是同一条边。

• 如果表示边的顶点对（或序偶）是有序的，则称为有向图。在有向图中代表边的顶点对通常用尖括号括起来，用以表示一条有向边（又称为弧），如表示从顶点i到顶点j的一条边。

• 图中每一条边都可以附有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图

1.4 图的基本术语

• 在一个无向图中，若存在一条边(i，j)，则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点，即顶点i是顶点j的一个邻接点，顶点j也是顶点i的一个邻接点。
• 在一个有向图中，若存在一条边，则称此边是顶点i的一条出边，同时也是顶点j的一条入边。i和j分别为此边的起始端点（简称为起点）和终止端点（简称终点）。并称顶点j是i的出边邻接点，顶点i是j的入边邻接点。
• 在无向图中，顶点所具有的边的数目称为该顶点的度。在有向图中，顶点i的度又分为入度和出度，以顶点i为终点的入边的数目，称为该顶点的入度。以顶点i为起点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。
• 若一个图（无论有向图或无向图）中有n个顶点和e条边，每个顶点的度为di（0≤i≤n-1），则有：

  

---

二. 图的存储结构

2.1 邻接矩阵

       邻接矩阵是表示顶点之间邻接关系的矩阵。设G=(V，E)是含有n（设n>0）个顶点的图，各顶点的编号为0～n-1，则G的邻接矩阵数组A是n阶方阵。

（所谓邻接矩阵，就是一个反应边与边之间联系的一个二维数组。这个二维数组我们使用A[n][n]来表示，其中 n 是顶点数。）

• 如果是不带权图，则二维数组中的每一个元素的值根据是否有边，设置为 0 或 1：

• 如果是带权图，则：

2.2 邻接矩阵表述形式

可以这样理解上图：

第一行表示：0 顶点与 1、3、4 顶点有边，与自身和 2 顶点没有边

第二行表示：1 顶点与 0、2、3 顶点有边，与自身和 4 顶点没有边

第三行表示：2 顶点与 1、3、4 顶点有边，与自身和 0 顶点没有边

... ...