数据结构与算法——图

图

1.图的定义和表示

图的定义

图G由集合V和集合E组成，记作G=(V,E),其中：

1、V是顶点元素的有限集合；

2、E是顶点间关系——边的有限集合。

3、边是顶点的无序对或有序对。

无向图和有向图：

 无向图

由没有方向的边构成的图。

无向图中的边由顶点的无序对组成。（用圆括号表示）

邻接点：无向图中，若存在一条边(Vi,Vj)，则称Vi和Vj互为邻接点。

上图中的边是无方向的，即(V1,V2)和(V2,V1)表示同一条边。

有向图

由有方向的边构成的图。

弧：有向图中的边由顶点的有序对组成，也称为弧。（用尖括号表示）

有向图中，顶点的有序对<Vi,Vj>表示从Vi指向Vj的一条有向边，其中Vi是起点，Vj是终点。

上图中的边是有方向的，<V1,V2>和<V2,V1>表示两条不同的边。

图的表示

上图G1中：

V(G1)={1,2,3,4,5,6,7}

E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}

上图G2中：

V(G2)={1,2,3,4,5,6}

E(G2)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>} 

完全图与子图

完全图：图中任意两项点间均有边直接相连。

无向完全图：有n个顶点和n(n-1)/2条边的无向图。

有向完全图：有n个顶点和n(n-1)条弧的有向图。

子图：对于图G=(V,E)和图G'=(V',E')，若存在V'∈V且E'∈E，则称图G'是图G的子图。

2.图的相关概念

顶点的度

无向图中，顶点的度是与每个顶点相连的边数。

有向图中，顶点的度分成入度与出度。

入度：以该顶点为终点的弧的数目

出度：以该顶点为起点的弧的数目

路径与回路

路径：从Vi出发，经过一系列的边或弧能够到达Vj，则称Vi到Vj所经过的顶点序列为从Vi到Vj的路径。

路径长度：路径经过的边的数目或各边权值之和。

回路：起点和终点相同的路劲。

简单路径：序列中顶点不重复出现的路径。

简单回路：除了起点和终点外，其余顶点不重复出现的回路。

连通图

连通：顶点Vi到Vj有一条路径（不要求直达）则Vi和Vj是连通的。

连通图：图中任意两个顶点都是连通的。

连通分量：非连通图的每一个极大连通子图。

强连通图：有向图中任意不同的顶点Vi和Vj，从Vi到Vj和从Vj到Vi都存在路劲。

连通图

强连通图

非连通图的两个连通分量

邻接矩阵

表示顶点间相邻关系的矩阵。

设G=(V,E)是有n(n>0)个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵：

特点：

无向图的邻接矩阵沿对角线对称。

有向图的邻接矩阵不一定对称。

示例：

无向图的邻接矩阵

有向图的邻接矩阵

权与网

权：图中边或弧上附带的数值称为权(w)。

网：带权的图称为网。

3.图的存储结构与实现 

邻接表

 邻接表：有顶点表和边表组成，是链式存储结构。

顶点表

存放图中每个顶点的信息以及指向该顶点边表的头指针。顶点表通常采用顺序存储结构。

顶点表的结点结构：data——head

顶点域data存放顶点信息，head为边表头指针。

边表

为图中的每个顶点建立的单链表，单链表中存放与同一个顶点相邻接的邻接点，相当于邻接矩阵中的一行。

边表的结点结构：adjVex——next

邻接点域adjVex存放邻接点在顶点表中的序号，next为指向下一个邻接点的指针。

示例：无向图的邻接表

逆邻接表

结构与邻接表完全相同，只是边表中每个 结点存放的是每条弧的弧尾顶点。

4.图的遍历方法

深度优先遍历（DFS）

1、从图的某一顶点v出现（起点任选），访问此顶点；

2、选择一个与顶点v相邻且未被访问过的顶点w，再从w出发进行深度优先遍历（递归），直至图中所有和v连通的顶点都被访问过为止；

3、若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。

深度优先遍历过程

为图的顶点设置一个访问标记数组visited[n]，其中相应顶点的元素值为0表示为访问，为1表示已访问。

该图的深度优先搜索的输出序列为：ABCFEGDHI

示例：深度优先遍历无向图

深度遍历：V1->V2->V4->V8->V5->V6->V3->V7

示例：深度优先遍历有向图

深度遍历：V1->V2->V4->V8->V3->V6->V7->V5

广度优先遍历（BFS）

1、从图的某一项顶点V出发（起点任选），访问顶点；

2、访问V的所有未被访问过的邻接点V1,V2,...,Vt，按照V1,V2,...,Vt的次序，访问每一个顶点的所有未被访问过的邻接点。依此类推，直至图中所有和V连通的顶点都未被访问过为止；

3、若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起点，重复上述过程，直至图中所有顶点都被访问为止。

广度优先遍历过程

该图的广度优先搜索的输出序列为：ABEDCGFHI

示例：广度优先遍历无向图

广度遍历：V1->V2->V3->V4->V5->V6->V7->V8

示例：广度优先遍历有向图

广度遍历：V1->V2->V3->V4->V6->V7->V8->V5