完全图 在有n个结点的无向图中，若有n(n-1)/2条边，即任意两个结点之间有且只有一条边，则称此图为无向完全图。在有n个结点的有向图中，若有n(n-1)条边，即任意两个结点之间有且只有方向相反的两条边，则称此图为有向完全图。
邻接结点 在无向图G中，若（u,v）是E(G)中的一条边，则称u和v互为邻接结点，并称边（u,v）依附于结点u和v。在有向图G中，若＜u,v＞是E(G)中的一条边，则称结点u邻接到结点v，结点v邻接自结点u，并称边＜u,v＞和结点u和结点v相关联。
子图 设有图G1={V1,E1}和图G2={V2,E2}，若V2V1且E2E1，则称图G2是图G1的子图。
连通图和强连通图 在无向图中，若从结点vi到结点vj有路径，则称结点vi和结点vj是连通的。如果图中任意一对结点都是连通的，则称该图是连通图。在有向图中，若对于任意一对结点vi和结点vj（vi≠vj）都存在路径，则称图G是强连通图。
最小生成树 一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图联通的最少的边。（n-1）条边。
邻接矩阵：
边的权值类：
//描述边的权值类public class Weight { //横纵表示哪两个点，之间的连线有权重 int row; //横坐标 int col; //纵坐标 int weight; //权值 Weight(int row,int col,int weight) { this.row = row; this.col = col; this.weight = weight; } //e是边的数量，n是节点的数量 //weight是指边权重的数组，里面封装了元素的下标和之间的权重，里面的横纵坐标是有顺序的 public static void createAdjGraphic(MyAdjGraphic g, Object[] vertices, int n,Weight[] weight,int e) throws Exception { //初始化结点 for(int i=0;i 邻接矩阵类
矩阵的横纵都是节点，组合表示为边
//邻接矩阵类public class MyAdjGraphic { static final int maxWeight=-1; //如果两个结点之间没有边，权值为-1； ArrayList vertices = new ArrayList();//存放结点的集合 int[][] edges; //邻接矩阵的二维数组 int numOfEdges; //边的数量 public MyAdjGraphic(int n) { edges = new int[n][n]; for(int i=0;i = vertices.size())||(v2 < 0||v2 >= vertices.size())) { throw new Exception("v1或者v2参数越界错误！"); } return this.edges[v1][v2]; } //插入结点 public void insertVertice(Object obj) { this.vertices.add(obj); } //插入带权值的边 public void insertEdges(int v1,int v2,int weight) throws Exception { if((v1 < 0 || v1 >= vertices.size())||(v2 < 0||v2 >= vertices.size())) { throw new Exception("v1或者v2参数越界错误！"); } this.edges[v1][v2]=weight; this.numOfEdges++; } //删除某条边 public void deleteEdges(int v1,int v2) throws Exception { if((v1 < 0 || v1 >= vertices.size())||(v2 < 0||v2 >= vertices.size())) { throw new Exception("v1或者v2参数越界错误！"); } if( v1==v2 || this.edges[v1][v2]==maxWeight) { throw new Exception("边不存在！"); } //删除就是把矩阵中的值置为-1即可 this.edges[v1][v2]=maxWeight; this.numOfEdges--; } //打印邻接矩阵 public void print() { for(int i=0;i 测试类：
public class Test { public static void main(String[] args) { int n=5; //5个结点 int e=5; //5条边 MyAdjGraphic g = new MyAdjGraphic(n); Object[] vertices = new Object[]{new Character('A'),new Character('B'),new Character('C'),new Character('D'),new Character('E')}; Weight[] weights = new Weight[]{new Weight(0,1,10),new Weight(0,4,20),new Weight(2,1,40),new Weight(1,3,30),new Weight(3,2,50)}; try { Weight.createAdjGraphic(g, vertices, n, weights, e); System.out.println("--------该临街矩阵如下---------"); g.print(); System.out.println("结点的个数："+g.getNumOfVertice()); System.out.println("边的个数："+g.getNumOfEdges()); g.deleteEdges(0, 4); System.out.println("--------删除之后---------"); g.print(); System.out.println("结点的个数："+g.getNumOfVertice()); System.out.println("边的个数："+g.getNumOfEdges()); } catch(Exception ex) { } }} 图的遍历
依序打印出所有节点
主要是在邻接矩阵上进行操作：
因此在邻接矩阵类中加入以下两个方法
//取第一个邻接结点 public int getFirstNeighbor(int v) throws Exception { if((v < 0 || v >= vertices.size())) { throw new Exception("v参数越界错误！"); } for(int col=0;col 0) { return col; } } return -1; } ///取下一个邻接结点 public int getNextNeighbor(int v1,int v2) throws Exception { if((v1 < 0 || v1 >= vertices.size())||(v2 < 0||v2 >= vertices.size())) { throw new Exception("v1或者v2参数越界错误！"); } for(int col=v2+1;col 0) { return col; } } return -1; } 深度优先遍历算法：使用了递归的思想，stack
也是基于在邻接矩阵中寻找
//连通图的深度优先遍历算法 public void deptFirstSearch(Visit v) throws Exception { //建立访问记录数组 boolean[] visited = new boolean[this.vertices.size()]; //一开始都置为未访问过 for(int i=0;i 广度优先算法：使用队列的思想，queue
利用队列，把当前点的邻居节点都入队列，然后一个一个出对列，寻找下一层再加入队列。
一层一层的走。
//广度优先遍历算法的调用算法 public void broadFirstSearch(Visit v) throws Exception { boolean[] visited = new boolean[this.vertices.size()]; for(int i=0;i 图的遍历的测试类
public class Test { public static void main(String[] args) { int n=5; //5个结点 int e=5; //5条边 MyAdjGraphic g = new MyAdjGraphic(n); Object[] vertices = new Object[]{new Character('A'),new Character('B'),new Character('C'),new Character('D'),new Character('E')}; Weight[] weights = new Weight[]{new Weight(0,1,10),new Weight(0,4,20),new Weight(2,1,40),new Weight(1,3,30),new Weight(3,2,50)}; try { Weight.createAdjGraphic(g, vertices, n, weights, e); System.out.println("--------该临接矩阵如下---------"); g.print(); System.out.println("结点的个数："+g.getNumOfVertice()); System.out.println("边的个数："+g.getNumOfEdges()); /* g.deleteEdges(0, 4); System.out.println("--------删除之后---------"); g.print(); System.out.println("结点的个数："+g.getNumOfVertice()); System.out.println("边的个数："+g.getNumOfEdges()); */ Visit v = new Visit(); System.out.println("\n深度优先遍历序列："); g.deptFirstSearch(v); System.out.println("\n广度优先遍历序列："); g.broadFirstSearch(v); } catch(Exception ex) { } }} 深度优先遍历：A B D C E
广度优先遍历：A B E D C