数据结构与算法：图形结构（算法与数据结构图）-人工智能-知优网

图形结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层中的至多一个结点相关，但可能和下一层的多个结点相关。而在图形结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。

图

图形结构是一种比树形结构更杂乱的非线性结构。在树形结构中，结点间具有分支层次联系，每一层上的结点只能和上一层中的至多一个结点相关，但或许和下一层的多个结点相关。而在图形结构中，恣意两个结点之间都或许相关，即结点之间的邻接联系可所以恣意的。

因而，图形结构被用于描绘各种杂乱的数据目标，在自然科学、社会科学和人文科学等许多范畴有着十分广泛的运用。图形结构在计算机科学、人工智能、电子线路剖析、最短途径寻觅、工程方案、化学化合物剖析统计力学、遗传学、控制论语言学和社会科学等方面均有不同程度的运用能够这样说，图形结构在一切数据结构中运用最为广泛。如在地铁站中的线路图：

图的界说

图是一种数据结构，其间节点能够具有零个或多个相邻元素，两个节点的衔接称之为边，节点在图形结构中也被称为极点，一个极点到另一个极点的通过的的线路称为途径。

图形结构有3种类型：无向图、有向图、带权图
无向图：极点A与极点B之间的边是无方向的，能够从A到B，也能够从B到A
有向图：极点A与极点B之间的边是有方向的，能够从A到B，但不能够从B到A
带权图：极点A与极点B之间的边是带有特点的，如A到B的间隔。

图的表达方式

图的表达方式有两种：邻接矩阵(运用二维数组)和邻接表(运用数组+链表)

邻接矩阵

邻接矩阵是表明图形中各极点之间的联系，矩阵的行和列对应各极点，坐标方位上的值关于它们之间的联系，1为衔接, 0为没有衔接。在程序顶用二维数组来完成。

邻接表

邻接表只联系存在的边，不需求去为不存在的边分配空间，因而比邻接矩阵来说，避免了不必要的空间糟蹋。在程序顶用数组+链表的方式完成，数组存储对应的极点，链表存储该极点衔接的一切极点。

图的查找算法

图形结构根底特点和办法

以下的代码演示都是以邻接矩阵表达方式来完成的

//图形结构(邻接矩阵)
classGraph{
//存储图中一切极点
privateList<String>vertexes;
//图形结构的邻接矩阵
privateint[][]matrix;
//各极点拜访状况，true为已拜访，false为未拜访
privateboolean[]visited;
/**
*依据传入的极点信息生成矩阵
*@params
*/
publicGraph(Strings[]){
vertexes=newArrayList<>();
for(Stringvertex:s){
vertexes.add(vertex);
}
matrix=newint[s.length][s.length];
}
/**
*将俩个极点衔接，即生成边
*@paramindex1极点在调集中的索引
*@paramindex2
*/
publicvoidconnect(intindex1,intindex2){
if(index1<0||index1>matrix.length||index2<0||index2>matrix.length){
thrownewRuntimeException("该极点未存在");
}
//将新的邻接增加的邻接矩阵中
matrix[index1][index2]=1;
matrix[index2][index1]=1;
}
/**
*展现邻接矩阵
*/
publicvoidshowGraphMatrix(){
for(intarr[]:matrix){
System.out.println(Arrays.toString(arr));
}
}
/**
*获取极点在邻接矩阵对应行row中的第一个邻接极点下标
*@paramrow
*@return当有邻接极点时回来邻接极点下标，没有则回来-1
*/
publicintgetFirstNeighbor(introw){
for(inti=0;i<matrix.length;i++){
if(matrix[row][i]!=0){
returni;
}
}
return-1;
}
/**
*获取极点在邻接矩阵关于行row中col列的下一个邻接极点
*@paramrow
*@paramcol
*@return当有邻接极点时回来邻接极点下标，没有则回来-1
*/
publicintgetNeighbor(introw,intcol){
for(inti=col+1;i<matrix.length;i++){
if(matrix[row][i]!=0){
returni;
}
}
return-1;
}
}

深度优先查找

深度优先查找归于图算法的一种，英文缩写为DFS即Depth First Search.其进程扼要来说是对每一个或许的分支途径深化到不能再深化停止，并且每个节点只能拜访一次。这样的拜访战略是优先往纵向进行深化发掘，而不是对一个极点的一切邻接极点进行横线拜访。简略来说便是一条路走到死，不可再掉头。

思路：从当时极点选一个与之衔接而未拜访过的极点，将当时节点往该邻接极点移动，假如邻接极点没有未拜访的，则回溯到上一个极点方位，持续该进程。直到一切极点都拜访过。

往邻接但未拜访过的极点移动

邻接极点没有未拜访的，进行回溯，直到遇到未拜访的邻接极点

当一切极点都被拜访过期，退出算法

下面是深度优先查找的进程动画

代码演示

publicvoiddsf(){
visited=newboolean[vertexes.size()];
//以在调集中下标为0的极点，进行深度查找
dsf(visited,0);
}
/**
*深度优先查找
*@paramvisited
*@paramrow
*/
publicvoiddsf(boolean[]visited,introw){
//输出当时极点
System.out.print(vertexes.get(row)+"->");
//将当时极点设为已拜访
visited[row]=true;
//获取当时极点的邻接极点下标
intindex=getFirstNeighbor(row);
//假如当时极点有邻接极点则进行深度查找
while(index!=-1){
//当邻接极点未拜访时，则递归遍历
if(visited[index]!=true){
dsf(visited,index);
}
//当邻接极点已拜访时，则寻觅另一个邻接极点
index=getNeighbor(row,index);
}
}

宽度优先查找

宽度优先查找算法(又称广度优先查找)是最简洁的图的查找算法之一，这一算法也是许多重要的图的算法的原型。Dijkstra单源最短途径算法和Prim最小生成树算法都采用了和宽度优先查找相似的思维。其别号又名BFS，归于一种盲目查找法，意图是体系地打开并查看图中的一切节点，以找寻成果。换句话说，它并不考虑成果的或许方位，彻底地查找整张图，直到找到成果停止。

宽度优先查找算法相似于一个分层查找的进程，宽度优先查找算法需求一个行列以坚持拜访过极点的次序，以便按这个次序来拜访这些极点的邻接极点。

思路：顺次拜访当时极点的邻接极点，并按拜访次序将这些邻接极点存储在行列中，当当时极点的一切邻接极点都被拜访后，从行列中弹出一个极点，以该极点为当时极点持续该进程，直到一切极点都被拜访过。

顺次拜访当时极点的一切邻接极点，并把这些邻接极点按拜访次序存储在行列中

当时极点没有未拜访的邻接极点，从行列中弹出一个极点，以该弹出极点持续拜访未拜访的邻接极点

留意，尽管图中的极点都现已拜访过了，但仍是要等行列中的一切极点弹出拜访后，算法才完毕

下面时宽度优先查找的进程动画

代码演示

publicvoidbfs(){
visited=newboolean[vertexes.size()];
////以在调集中下标为0的极点，进行广度优先查找
bfs(visited,0);
}
/**
*广度优先查找
*@paramvisited
*@paramrow
*/
publicvoidbfs(boolean[]visited,introw){
//创立行列，存储遍历邻接极点的次序
LinkedListqueue=newLinkedList();
//输出当时极点
System.out.print(vertexes.get(row)+"->");
//将当时极点设为已拜访
visited[row]=true;
//将当时极点参加行列中
queue.add(row);
//当行列不为空时，即有未查找的邻接极点，进行查找
while(!queue.isEmpty()){
//按次序从行列中弹出邻接极点下标
intlast=(Integer)queue.removeFirst();
//获取该弹出极点的邻接极点下标
intindex=getFirstNeighbor(last);
//当弹出极点有邻接极点时，进行广度查找
while(index!=-1){
//当邻接极点未拜访时
if(visited[index]!=true){
//输出该邻接极点
System.out.print(vertexes.get(index)+"->");
//把该邻接极点设为已拜访
visited[index]=true;
//将该邻接极点参加行列
queue.addLast(index);
}
//持续寻觅弹出极点的另一个邻接极点
index=getNeighbor(last,index);
}
}
}

完好演示代码

publicclassGraphDemo{
publicstaticvoidmain(String[]args){
String[]s={"A","B","C","D","E","F","G"};
Graphgraph=newGraph(s);
//A-BA-CA-GA-FF-DF-ED-EE-G
graph.connect(0,1);
graph.connect(0,2);
graph.connect(0,6);
graph.connect(0,5);
graph.connect(5,3);
graph.connect(5,4);
graph.connect(3,4);
graph.connect(4,6);
graph.showGraphMatrix();
graph.dsf();//A->B->C->F->D->E->G->
System.out.println();
graph.bfs();//A->B->C->F->G->D->E->
}
}
//图形结构
classGraph{
//存储图中一切极点
privateList<String>vertexes;
//图形结构的邻接矩阵
privateint[][]matrix;
//各极点拜访状况，true为已拜访，false为未拜访
privateboolean[]visited;
/**
*依据传入的极点信息生成矩阵
*@params
*/
publicGraph(Strings[]){
vertexes=newArrayList<>();
for(Stringvertex:s){
vertexes.add(vertex);
}
matrix=newint[s.length][s.length];
}
/**
*将俩个极点衔接，即生成边
*@paramindex1极点在调集中的索引
*@paramindex2
*/
publicvoidconnect(intindex1,intindex2){
if(index1<0||index1>matrix.length||index2<0||index2>matrix.length){
thrownewRuntimeException("该极点未存在");
}
//将新的邻接增加的邻接矩阵中
matrix[index1][index2]=1;
matrix[index2][index1]=1;
}
/**
*展现邻接矩阵
*/
publicvoidshowGraphMatrix(){
for(intarr[]:matrix){
System.out.println(Arrays.toString(arr));
}
}
publicvoiddsf(){
visited=newboolean[vertexes.size()];
//以在调集中下标为0的极点，进行深度优先查找
dsf(visited,0);
}
/**
*深度优先查找
*@paramvisited
*@paramrow
*/
publicvoiddsf(boolean[]visited,introw){
//输出当时极点
System.out.print(vertexes.get(row)+"->");
//将当时极点设为已拜访
visited[row]=true;
//获取当时极点的邻接极点下标
intindex=getFirstNeighbor(row);
//假如当时极点有邻接极点则进行深度查找
while(index!=-1){
//当邻接极点未拜访时，则递归遍历
if(visited[index]!=true){
dsf(visited,index);
}
//当邻接极点已拜访时，则寻觅另一个邻接极点
index=getNeighbor(row,index);
}
}
publicvoidbfs(){
visited=newboolean[vertexes.size()];