|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 >
|
|
相关知识点：30个
|
|
|
|
|
|
|
图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为：
|
|
|
|
|
|
其中V=｛x|x?某个数据对象集｝，它是顶点的有穷非空集合；E=｛（x，y） |x, y? V｝或E=｛|x，y?V且Path （x, y）｝,它是顶点之间关系的有穷集合，也称为边集合，PathP （x，y）表示从x到y的一条单向通路。
|
|
|
|
通常，也将图G的顶点集和边集分别记为V （G）和E （G）。E （G）可以是空集，若E （G）为空，则图G只有顶点而没有边。
|
|
|
|
若图G中的每条边都是有方向的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对有向边i，vj>表示一条由vi到vj的有向边。有向边又称为弧，也称为边弧，边弧的始点vi称为弧尾（Tail），边弧的终点vj称为弧头（Head）。若图G中的每条边都是没有方向的，则称G为无向图。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
|
|
|
|
|
|
设G=（V，E）是有n （n31）个顶点的图，在图的邻接矩阵表示法中，可用两个表格分别存储数据元素（顶点）的信息和数据元素之间的关联（边）信息。通常用一维数组（顺序表）存储数据元素的信息，用二维数组（邻接矩阵）存储数据元素之间的关系。
|
|
|
|
|
|
给定图G=（V，E），其中V（G）=｛v0，…，vi, …，vn-1｝，G邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵，G的邻接矩阵是具有如下性质的n阶方阵：
|
|
|
|
|
|
若图中顶点信息是0至n-1的编号，则仅需令权值为1，存储一个邻接矩阵就可以表示图。若是网络，则adjtype为权的类型。由于无向图或无向网络的邻接矩阵是对称的，故可采用压缩存储的方法，仅存储下三角阵（不包括对角线上的元素）中的元素即可。显然，邻接矩阵表示法的空间复杂度S（n）=O（n2）。
|
|
|
|
|
|
给定图G=（V，E）和V （G）中的某一顶点v，从v出发访问G中其余顶点，且使每个顶点位置仅被访问一次，这一过程称为图的遍历。
|
|
|
|
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法，它们对无向图和有向图均适用。
|
|
|
|
|
|
深度优先搜索（Depth-First Search）的基本思想是：对于给定的图G=（V，E），首先将V中每一个顶点都标记为未被访问，然后，选取一个源点将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历。如果从v出发有路的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到V中所有顶点都已被访问过为止。
|
|
|
|
|
|
图的广度优先遍历的基本思想是：给定图G=（V，E），从图中某个源点v出发，在访问了顶点v之后，接着就尽可能先在横向搜索v的所有邻接点。在依次访问v的各个未被访问过的邻接点w1，w2，…，wk之后，分别从这些邻接点出发依次访问与w1，w2, …，wk邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问过为止，此时从v开始的搜索过程结束。若G是连通图，则遍历完成；否则，在图G中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至图G中所有顶点均已被访问为止。采用广度优先搜索法遍历图的方法称为图的广度优先遍历。
|
|
|
|
为确保先访问的顶点其邻接点亦先被访问，在搜索过程中可使用队列来保存已访问过的顶点。当访问v和u时，这两个顶点相继入队，此后，当v和u相继出队时，分别从v和u出发搜索其邻接点v1，v2，…，vs和u1，u2, …，ut，对其中未访者进行访问并将其入队。这种方法是将每个已访问的顶点入队，保证了每个顶点至多只有一次入队。
|
|
|
