|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
若矩阵中元素（或非零元素）的分布有一定的规律，则称之为特殊矩阵。常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵等。
|
|
|
|
|
|
|
|
|
|
上（下）三角矩阵：矩阵的上（下）三角（不包括对角线）中的元素均为常数或零。
|
|
|
|
对角矩阵：矩阵中的非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和在对角线上、下方若干条对角线上的元素外，其余的矩阵元素都为零。
|
|
|
|
|
|
在一个矩阵中，若非零元素的个数远远少于零元素的个数，且非零元素的分布没有规律，则称之为稀疏矩阵。存储稀疏矩阵的非零元素时必须同时存储其位置（行、列号），用三元组（i,j,aij）可唯一确定矩阵中的一个元素。因此，一个稀疏矩阵可由表示非零元素的三元组及其行、列数唯一确定。
|
|
|
|
稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
图的广度优先遍历的基本思想是：给定图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，对其中未访者进行访问并将其入队。这种方法是将每个已访问的顶点入队，保证了每个顶点至多只有一次入队。
|
|
|
|
|
|
|
|
|
|
|
|
|
