作者:Gofy
出处:
图图形结构是一种比树形结构更复杂的非线性结构 。 在树形结构中 ， 结点间具有分支层次关系 ， 每一层上的结点只能和上一层中的至多一个结点相关 ， 但可能和下一层的多个结点相关 。 而在图形结构中 ， 任意两个结点之间都可能相关 ， 即结点之间的邻接关系可以是任意的 。
因此 ， 图形结构被用于描述各种复杂的数据对象 ， 在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。 图形结构在计算机科学、人工智能、电子线路分析、最短路径寻找、工程计划、化学化合物分析统计力学、遗传学、控制论语言学和社会科学等方面均有不同程度的应用可以这样说 ， 图形结构在所有数据结构中应用最为广泛 。 如在地铁站中的线路图：
文章插图
图的定义图是一种数据结构 ， 其中节点可以具有零个或多个相邻元素 ， 两个节点的连接称之为边 ， 节点在图形结构中也被称为顶点 ， 一个顶点到另一个顶点的经过的的线路称为路径 。
图形结构有3种类型：无向图、有向图、带权图
无向图：顶点A与顶点B之间的边是无方向的 ， 可以从A到B ， 也可以从B到A
有向图：顶点A与顶点B之间的边是有方向的 ， 可以从A到B ， 但不可以从B到A
带权图：顶点A与顶点B之间的边是带有属性的 ， 如A到B的 距离 。
文章插图
图的表达方式图的表达方式有两种：邻接矩阵(使用二维数组)和邻接表(使用数组+链表)
邻接矩阵
邻接矩阵是表示图形中各顶点之间的关系 ， 矩阵的行和列对应各顶点 ， 坐标位置上的值对于它们之间的关系 ， 1为连接, 0为没有连接 。 在程序中用二维数组来实现 。
文章插图
邻接表
邻接表只关系存在的边 ， 不需要去为不存在的边分配空间 ， 因此比邻接矩阵来说 ， 避免了不必要的空间浪费 。 在程序中用数组+链表的形式实现 ， 数组存储对应的顶点 ， 链表存储该顶点连接的所有顶点 。
文章插图
图的搜索算法图形结构基础属性和方法
以下的代码演示都是以邻接矩阵表达方式来实现的
//图形结构(邻接矩阵)class Graph {//存储图中所有顶点private List vertexes;//图形结构的邻接矩阵private int[][] matrix;//各顶点访问情况 ， true为已访问 ， false为未访问private boolean[] visited;/*** 根据传入的顶点信息生成矩阵* @param s*/public Graph(String s[]) {vertexes = new ArrayList<>();for (String vertex : s){vertexes.add(vertex);}matrix = new int[s.length][s.length];}/*** 将俩个顶点连接 ， 即生成边* @param index1 顶点在集合中的索引* @param index2*/public void connect(int index1, int index2){if (index1 < 0 || index1 > matrix.length || index2 < 0 || index2 > matrix.length){throw new RuntimeException("该顶点未存在");}//将新的邻接添加的邻接矩阵中matrix[index1][index2] = 1;matrix[index2][index1] = 1;}/*** 展示邻接矩阵*/public void showGraphMatrix(){for (int arr[] : matrix){System.out.println(Arrays.toString(arr));}}/*** 获取顶点在邻接矩阵对应行row中的第一个邻接顶点下标* @param row* @return 当有邻接顶点时返回邻接顶点下标 ， 没有则返回-1*/public int getFirstNeighbor(int row){for(int i =0; i深度优先搜索深度优先搜索属于图算法的一种 ， 英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止 ， 而且每个节点只能访问一次 。 这样的访问策略是优先往纵向进行深入挖掘 ， 而不是对一个顶点的所有邻接顶点进行横线访问 。 简单来说就是一条路走到死 ， 不行再掉头 。
【数据结构与算法：图形结构】思路：从当前顶点选一个与之连接而未访问过的顶点 ， 将当前节点往该邻接顶点移动 ， 如果邻接顶点没有未访问的 ， 则回溯到上一个顶点位置 ， 继续该步骤 。 直到所有顶点都访问过 。
往邻接但未访问过的顶点移动
文章插图