算法与数据结构(十)--图的入门

一.图的定义和分类

定义:图是由一组顶点和一组能够将两个顶点连接的边组成的。

特殊的图
1.自环:即一条连接一个顶点和其自身的边;
2.平行边:连接同一对顶点的两条边;

图的分类
按照连接两个顶点的边的不同,可以把图分为以下两种:
无向图:边仅仅连接两个顶点,没有其他含义;
有向图:边不仅连接两个顶点,并且具有方向;

二.无向图

1.图的相关术语

相邻顶点
当两个顶点通过一条边相连时,我们称这两个顶点是相邻的,并且称这个边依赖于这两个顶点。

某个顶点的度就是依附于该顶点的边的个数。
子图
是一幅图的所有边的子集(包含这些边依附的顶点)组成的图。
路径
是由边顺序连接的一系列的顶点组成。

是一条至少含有一条边且终点和起点相同的路径。

连通图
如果图中任一一个顶点都存在一条路径到达另外一个顶点,那么这幅图就称之为联通图。
连通子图
一个非联通图由若干连通的部分组成,每一个连通的部分都可以成为该图的连通子图。

 

2.图的存储结构

要表示一幅图,只需要表示清楚一下两部分内容即可:
1.图中所有的顶点;
2.所有连接顶点的边;
常见 图的存储结构有两种:邻接矩阵和邻接表


【1】邻接矩阵

1.使用一个V*V的二维数组int[V][V]  adj。
2.如果顶点v和顶点w相连,我们只需要把adj[v][w]和adj[w][v]的值设置为1,否则设置为0即可。

 很明显,邻接矩阵这种存储方式的空间复杂度是V^2的,如果我们处理的问题规模比较大的话,内存空间极有可能不够用。

【2】邻接表

1.使用一个大小为V的数组Queue[V]  adj,把索引看做是顶点;
2.每个索引处adj[v]存储了一个队列,该队列中存储的是所有与该顶点相邻的其他顶点

很明显,邻接表的空间并不是是线性级别的,所以后面我们一直采用邻接表这种存储形式来表示图。

三.图的实现

四.图的搜索

1.深度优先搜索

所谓的深度优先搜索,指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找子结点,然后找 兄弟结点。

2.广度优先搜索

所谓的广度优先搜索,指的是在搜索时,如果遇到一个结点既有子结点,又有兄弟结点,那么先找兄弟结点,然后 找子结点。