图表结构是比树结构更复杂的非线性结构。 在树结构中，节点之间有分支层次关系，各层次上的节点只与一个层次上的多个节点相关，但有可能只与下一层次上的多个节点相关。 在图表结构中，任意两个节点之间可能存在相关性。 也就是说，节点之间的相邻关系是任意的。
因此，图形结构用于描述各种复杂的数据对象，在自然科学、社会科学、人文科学等多个领域应用非常广泛。 图形结构在计算机科学、人工智能、电子电路分析、最短路径搜索、工程计划、化学化合物分析统计力学、遗传学、控制论语言学和社会科学等方面有不同程度的应用，图形结构在所有数据结构中应用最广泛
图的定义
图中，节点是可以具有零以上邻接要素的数据结构，两个节点的连接称为边，节点在图形结构中也称为顶点，从一个顶点到另一个顶点的路径称为路径。
图表结构有三种：有向图表、有向图表和加权图表。
无向图：顶点a和顶点b之间的边是无方向的，从a到b或从b到a。
有向图：顶点a和顶点b之间的边有方向，可以从a到b，但不能从b到a。
加权图：顶点a和顶点b之间的边具有从a到b的距离等属性。
图的表现
图的表现有邻接矩阵(使用二维数组)和邻接表(使用数组链表)两种。
相邻矩阵
相邻矩阵表示图形中各顶点之间的关系，矩阵的行和列对应于各顶点，坐标位置上的值对于它们之间的关系，1是连接，0是无连接。 在程序中用二维数组实现。
旁边的表
邻接表只与存在的边缘有关，不需要给不存在的边缘分配空间，所以比邻接矩阵更能避免不必要的空间浪费。 程序中以数组链表的形式实现，数组存储对应的顶点，链表存储该顶点连接的所有顶点。
图的搜索算法
图形结构的基本属性和方法
深度优先搜索
深度优先搜索是图算法的一种，英语的简称是DFS——depth first search。 其过程简单地说，每个可能的分支路径都无法深入，每个节点只能访问一次。 这样的访问策略是优先纵向深入，而不是访问一个顶点的所有相邻顶点。 简单来说，走到死亡，不能再掉头了。
想法：选择从当前顶点没有连接访问过的顶点，将当前节点移动到其相邻顶点，如果相邻顶点没有访问，则追溯到上一个顶点位置，继续此步骤。 我访问过所有的顶点。
文/上海蓝盟 IT外包专家
中文
电话咨询
微信咨询
公众号
