图的创建（邻接表/邻接矩阵）、遍历（DFS、BFS）与最短路径（Dijkstra/Floyd）算法
目录
一、图的创建
1.邻接矩阵
2.邻接表
3.其他存储方式
二、图的遍历
1.深度优先DFS(使用递归）
2.广度优先BFS(使用队列)
3.DFS与BFS的比较
三、最短路径求解
1.迪杰斯特拉算法(Dijkstra)
2.弗洛伊德算法(Floyd)
3.Dijkstra与Floyd的比较
抛出问题：为什么会有图这种数据结构？
因为线性表表示的是一对一的关系，树表示了一对多的关系。当我们需要使用到多对多关系时，就需要使用图这种数据结构。
图的创建
1.邻接矩阵（二维数组表示）
图有N个顶点，邻接矩阵就用N*N的二维数组表示。matrix[i][j] 的值为顶点i到顶点j的权值。比较简单，直接上java代码写的邻接矩阵（核心代码如下：）
public class Graph2 {ArrayList<Vertex> vertexList; //顶点加入到List集合int[][] edgeMatrix; //初始化后都为0int vertexNum; //顶点数量int edgeNum; //边的数量/*** 插入顶点* @param vertex*/public void insertVertex(Vertex vertex){vertexList.add(vertex);//this.vertexNum++;}/**\* 添加边* @param v1 第一个顶点的下标* @param v2 第二个顶点的下标* @param weight 边的权值*/public void insertEdge(int v1,int v2,int weight){edgeMatrix[v1][v2] =weight;edgeMatrix[v2][v1] =weight; //无向图就加上这一句edgeNum++;}}/*** 顶点类*/
class Vertex {String vertexName;public Vertex(String vertexName) {this.vertexName = vertexName;}@Overridepublic String toString() {return vertexName ;}
}
2.邻接表（一维数组加链表）
这里有两种实现情况：（这里数组都用ArrayList实现）
- 使用顶点链接顶点的方式构建图，这种方法比较low，头结点后链接的每一条边都是新new的顶点结点，这样做会避免指针紊乱，但会占用很多额外的空间。
- 使用边（边是由两个顶点V1 V2构成的）的第二个顶点V2所在ArayList中的索引位置作为边对象构建图（这种方法好些、李春葆教材使用的方式）
2.1使用顶点链接顶点的方式构建图
package vertex;import java.util.Scanner;/*** 数组加链表形式 数组是vertexList ，用ArrayList来代替* 邻接链表使用顶点作为对象构建图*/public class CreateGraph3 {/*** 根据用户输入的string类型的顶点返回该顶点* @param graph 图* @param str 输入顶点名称* @return返回一个顶点*/public Vertex1 getVertex(Graph1 graph,String str){for(int i=0;i<graph.verNum;i++){if(graph.vertexArray[i].verName.equals(str)){return graph.vertexArray[i];}}return null;}/*** 根据用户输入的数据初始化一个图，以邻接表的形式构建!* @param graph 生成的图*/public void initialGraph(Graph1 graph){@SuppressWarnings("resource")Scanner scan=new Scanner(System.in);System.out.println("请输入顶点数和边数：");graph.verNum=scan.nextInt();graph.edgeNum=scan.nextInt();System.out.println("请依次输入定点名称：");for(int i=0;i<graph.verNum;i++){Vertex1 vertex=new Vertex1();String name=scan.next();vertex.verName=name;vertex.nextNode=null;graph.vertexArray[i]=vertex;}System.out.println("请依次输入图的边（两个顶点）：");for(int i=0;i<graph.edgeNum;i++){String preV=scan.next();String folV=scan.next();Vertex1 v1=getVertex(graph,preV);if(v1==null)System.out.println("输入边存在图中没有的顶点！");//下面代码是图构建的核心：链表操作 头插法// ！！！注意 这里使用新new一个V2结点的方式 作为要连接的对象 不能链接VertexList中的V2对象，那样会使链表指向发生变化，导致整个链表发生错误紊乱Vertex1 v2=new Vertex1();v2.verName=folV;v2.nextNode=v1.nextNode;v1.nextNode=v2;//紧接着下面注释的代码加上便是构建无向图的，不加则是构建有向图的！
// Vertex1 reV2=getVertex(graph,folV);
// if(reV2==null)
// System.out.println("输入边存在图中没有的顶点！");
// Vertex1 reV1=new Vertex1();
// reV1.verName=preV;
// reV1.nextNode=reV2.nextNode;
// reV2.nextNode=reV1;}}/*** 输入图的邻接表* @param graph 待输出的图*/public void outputGraph(Graph1 graph){System.out.println("输出图的邻接链表为：");for(int i=0;i<graph.verNum;i++){Vertex1 vertex=graph.vertexArray[i];System.out.print(vertex.verName);Vertex1 current=vertex.nextNode;while(current!=null){System.out.print("-->"+current.verName);current=current.nextNode;}System.out.println();}}public static void main(String[] args) {Graph1 graph=new Graph1();CreateGraph3 createGraph=new CreateGraph3();createGraph.initialGraph(graph);createGraph.outputGraph(graph);}
}------------------------------------------------------
package vertex;/*** 自定义图类* @author King*/
public class Graph1 {Vertex1[] vertexArray=new Vertex1[100];int verNum=0;int edgeNum=0;
}
-------------------------------------------------------
package vertex;/*** 顶点类* @author King*/
public class Vertex1 {String verName;Vertex1 nextNode;
}
下面我们说一说这种方式为什么会占用很多额外空间
如下图与他的邻接表所示
对于B结点，如果数组中的结点和链表中的结点都是用同一个对象，那么B到底是指向C呢还是指向D呢？ 为了避免这种指针紊乱，所以每个边对象都需要新new一个顶点结点，有多少条边就会需要多少额外对象空间
2.2使用边（边是由两个顶点V1 V2组成的）的第二个顶点V2所在索引位置作为边对象构建图（教材中普遍使用的方式）
这样，边是边对象，顶点是顶点对象，不会发生上述情况。虽然说每个边对象也得重新new，但是边里面存放的只是下标与next指针，数据量比较小（假如顶点里面包含的信息很多，水平不够，暂时只能这么理解···）
package vertex;import java.util.Scanner;/*** 数组加链表形式 数组是vertexList ，用ArrayList来代替* 邻接链表使用顶点作为对象构建图*/public class CreateGraph3 {/*** 根据用户输入的string类型的顶点返回该顶点* @param graph 图* @param str 输入顶点名称* @return返回一个顶点*/public Vertex1 getVertex(Graph1 graph,String str){for(int i=0;i<graph.verNum;i++){if(graph.vertexArray[i].verName.equals(str)){return graph.vertexArray[i];}}return null;}/*** 根据用户输入的数据初始化一个图，以邻接表的形式构建!* @param graph 生成的图*/public void initialGraph(Graph1 graph){@SuppressWarnings("resource")Scanner scan=new Scanner(System.in);System.out.println("请输入顶点数和边数：");graph.verNum=scan.nextInt();graph.edgeNum=scan.nextInt();System.out.println("请依次输入定点名称：");for(int i=0;i<graph.verNum;i++){Vertex1 vertex=new Vertex1();String name=scan.next();vertex.verName=name;vertex.nextNode=null;graph.vertexArray[i]=vertex;}System.out.println("请依次输入图的边（两个顶点）：");for(int i=0;i<graph.edgeNum;i++){String preV=scan.next();String folV=scan.next();Vertex1 v1=getVertex(graph,preV);if(v1==null)System.out.println("输入边存在图中没有的顶点！");//下面代码是图构建的核心：链表操作 头插法// ！！！注意 这里使用新new一个V2结点的方式 作为要连接的对象 不能链接VertexList中的V2对象，那样会使链表指向发生变化，导致整个链表发生错误紊乱Vertex1 v2=new Vertex1();v2.verName=folV;v2.nextNode=v1.nextNode;v1.nextNode=v2;//紧接着下面注释的代码加上便是构建无向图的，不加则是构建有向图的！
// Vertex1 reV2=getVertex(graph,folV);
// if(reV2==null)
// System.out.println("输入边存在图中没有的顶点！");
// Vertex1 reV1=new Vertex1();
// reV1.verName=preV;
// reV1.nextNode=reV2.nextNode;
// reV2.nextNode=reV1;}}/*** 输入图的邻接表* @param graph 待输出的图*/public void outputGraph(Graph1 graph){System.out.println("输出图的邻接链表为：");for(int i=0;i<graph.verNum;i++){Vertex1 vertex=graph.vertexArray[i];System.out.print(vertex.verName);Vertex1 current=vertex.nextNode;while(current!=null){System.out.print("-->"+current.verName);current=current.nextNode;}System.out.println();}}public static void main(String[] args) {Graph1 graph=new Graph1();CreateGraph3 createGraph=new CreateGraph3();createGraph.initialGraph(graph);createGraph.outputGraph(graph);}
}
------------------------------------------------------
package vertex;/*** 自定义图类* @author King*/
public class Graph1 {Vertex1[] vertexArray=new Vertex1[100];int verNum=0;int edgeNum=0;
}
-------------------------------------------------------
package vertex;/*** 图的顶点类* @author King*/
public class Vertex1 {String verName;Vertex1 nextNode;
}
3.其他存储方式
3.1逆邻接表
由于在有向图的邻接表中只存放了一个以顶点为起点的边，所以不易找到 指向该顶点的边 ，所以有了有向图的逆邻接表.就是在有向图的邻接表中对每个顶点链接的是 指向该顶点的边。
3.2十字链表（有向图的另一种存储方式）
这种方式综合了邻接表与逆邻接表的优势，将两者结合 。既容易找到一顶点v为起点的所有边（方便求其出度），也容易找到以顶点v为终点所有边（方便求其入度）
3.3邻接多重表
无向图的另一种存储方式，与十字链表类似。
图的遍历在下一篇：图的遍历
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！