首页 > 代码库 > 数据结构之图详解
数据结构之图详解
数据结构之图详解
图在计算机的程序设计中用途也十分广泛，图是一种与树有些相似的数据结构，从数学的角度来看，树也是图的一种。
连通图：如果至少有一条路径可以连接起所有的顶点，那么这个图称为连通图。大家现在可能会想心在图用什么数据结构来表示啊，顶点：用一个顶点类来表示，顶点放在数组中然后用下标指示，当然顶点也可以放在链表或者其他的数据结构中，存储的目的就是为了使用方便，这与边如何连接点没有关系。
边：可以用邻接矩阵或者邻接表来表示。邻接矩阵说白了就是一个二维数组，邻接表中的“表”指的是链表（链表的数组）
上代码：
顶点：
public class Vertex { /** * 这个类就是点类 */ public char label;//点的名称 public boolean wasVisited;//标志位 public Vertex(char label) { this.label = label; }}
图：
public class Graph { /** * 这个类是表示数据结构的图 */ private final int max_vertex = 20;//最大的点的数量 private Vertex[]vertexs ;//顶点的数组 private int adjMat[][];//表示一个邻接矩阵 private int currentVertexs;//当前顶点的实际的数量。 public Graph() { vertexs = new Vertex[max_vertex]; adjMat = new int [max_vertex][max_vertex]; currentVertexs = 0;//当前的数量0个 //初始化邻接矩阵 for(int i = 0;i<max_vertex;i++) { for(int j=0;j<max_vertex;j++) { adjMat[i][j] = 0; } } } //定义图的操作类 //添加顶点的方法 public void addVertex(char lab) { vertexs[currentVertexs++] = new Vertex(lab); } //添加边的方法 public void addEdge(int start,int end) { adjMat[start][end] = 1; adjMat[end][start] = 1; } //为了输出的效果 public void printGraph() { for(int i=0;i<max_vertex;i++) { for(int j=0;j<max_vertex;j++) { System.out.print(adjMat[i][j]+" "); } System.out.println(); } } }
测试：
public class App { public static void main(String[] args) { Graph theGraph = new Graph(); theGraph.addVertex(‘A‘); theGraph.addVertex(‘B‘); theGraph.addVertex(‘C‘); theGraph.addVertex(‘D‘); theGraph.addVertex(‘E‘); theGraph.addEdge(0, 1); theGraph.addEdge(1, 2); theGraph.addEdge(0, 3); theGraph.addEdge(3, 4); theGraph.printGraph(); }}
测试的结果：
0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
数据结构之图详解