java 图 代码自己写

图的建立也是基于数组的，但是遍历的话是基于链表或者是矩阵的

 

 

在计算机程序中，图是最常用的结构之一。

一般来说，用图来帮助解决的问题类型与其他的数据结构有很大的差别。

如果处理一般的数据存储问题，可以用不到图，但是对一些特别的问题，用图来解决是必不可少的。

     对图的讨论有两种，一种是带权的，还有一种是不带权的。

 

     不带权的图

 

     图是一种与树有些相似的数据结构。实际上，从数学的意义上来说，树是图的一种。然而，在计算机程序设计中，图的应用方式与树不同。

     例如，二叉树是那样的一个形状，就是因为那样的形状使它容易搜索数据和插入新数据。树的边表示了从一个节点到另一个节点的快捷方式。

      另一方面，图通常是一个固定的形状，这是由物理或者是抽象的问题所决定的。例如，图中节点表示城市，而边可能表示城市间的班机航线。

      另一个更抽象的例子是一个代表了几个单独任务的图，这些任务是完成一个项目所必须的。在图中，节点可能代表任务，有向边指示某个任务必须

      在另一个任务前完成。在这种情况下，图的形状取决于真实世界的具体情况。

 

      图的节点通常叫做顶点，连接的边就叫连接边。

 

      邻接

      如果两个顶点被同一条边连接，就称为这两个顶点是邻接的。和某个指定顶点邻接的顶点有时叫做它的邻居。

 

      路径

      路径是边的序列。

      连通图

      如果至少有一条路径可以连接起所有的顶点，那么这个图称为连通图。

      非连通图

      非连通图包含几个连通子图。

      有向图

      如果连接线是没有箭头的，那么连接的两个顶点是等级的，如果有箭头表示从一个顶点到另一个顶点的。叫做有向图了。

      无向图

 

      带权图

      边被赋予了某一个值值，那么表示了两个顶点直接的物理距离了。或者是从一个顶点到另一个顶点的时间。或者是两点直接要花费的的钱。这样的图

      叫做带权的权。

 

 

      图的表示

      邻接矩阵

      邻接链表

 

     下面的代码是为了表示出顶点的意思

 

/**
 * 顶点
 * 在非常抽象的图中，只是简单的把顶点编号，从0--N-1（这里的N是顶点数）。不需要任何变量类型
 * 存储顶点，因为他们是用来自于他们之间的互相关系。
 * 
 * 在大多数的情况下，顶点表示某个真实世界的对象，对象必须用数据项来表述。例如一个飞机航线，顶点就是表示机场，线路表示长度；
 * 机场这个对象包含很多东西啊，名字，城市名字，规模大小等等。
 * 
 * @author Endual
 * 这个例子只是列举了一个列子
 * char label表示一个顶点
 * 
 *顶点对象可以放在数组中，然后用一个下标指示，在本例中，用数组vertexList来存储顶点的对象。顶点也可以放在链表或者其他数据结构中
 *不论使用什么结构，存储只是为了使用方便。这与边如何连接点没有关系。要达到这个目的，还需要其他机制。
 *
 *
 *在二叉树中，顶点只有两个子节点的。但是在图中，一个顶点有任意多个顶点连接的。
 *为了模拟这样的情况，那么我们引入了邻接矩阵和邻接表
 *
 *
 *在图中添加顶点和边。
 *
 *
 * 
 */

public class Vertex {

	public char label ; //表示顶点的符号 一般用 a b c d e f g 表示
	public boolean isVisisted ; //是否被访问过了的默认是没有
	
	public Vertex(char label) {
		super();
		this.label = label;
		this.isVisisted = false; //默认是没有访问过的
	}

	public char getLabel() {
		return label;
	}

	public void setLabel(char label) {
		this.label = label;
	}

	public boolean isVisisted() {
		return isVisisted;
	}

	public void setVisisted(boolean isVisisted) {
		this.isVisisted = isVisisted;
	}
	
	
	
}

 

图的创建是不向我们以前的那样一次性就可以了，它的创建是是要分两次是的。第一次是输入的是顶点的信息，第二次是输入的是顶点之间的关系，就是矩阵的数据。这样才可以进行图的整体的创建了

 

我是用邻接矩阵来做的

 

 

/**
 *  为了项图中添加顶点，必须先new一个新的对象，然后插入到顶点的数组中去。在模拟真实世界的程序中，顶点可能包含许多数据项，但是为了简单
 *起见，这里假定顶点只包含单一的字符。因此顶点的创建用下面的代码。
 * 
 * 怎样添加边取决于用连接矩阵还是连接链表表示的图
 * 
 * 假定我们用的是邻接矩阵并考虑到在顶点A和顶点B直接添加一条边。这些数字对用vertextList数组的下标，顶点
 * 存储在数组的对应位子。首次创建邻接矩阵adjMat时，初值为0。添加边的代码如下：
 * adjMat[1][2] = 1 ;
 * adjMat[2][1] = 1 ;
 * 如果是用连接链表的，就把这个连接点添加到AB的链表中就可以了
 */
public class VertexList {

 private Vertex[] vertexList ; //存放顶点
 private int nVertexs ; //记录有多少个了
 private int maxVertext ; //最多放多少个数据
 
 //添加顶点
  public void insert(char label) {
	  
	  Vertex newVertex = new Vertex(label) ;
	  this.vertexList[this.nVertexs] = newVertex ; //也放入到数组中去
	  this.nVertexs++ ; //数组中数据加一个
	  
  }
	
}

 

下面是代码了

 

这个是图的创建以及深度遍历的一个例子

深度遍历是基于栈的

而广度遍历是基于队列的

 

 

import java.util.Stack;

/**
 * 下面来看下Graph类，包含的是创建连接链表和连接矩阵的方法，以向Graph对象插入顶点和边的方法
 * 
 * @author Endual
 *
 */
public class Graph {

	private  final int MAX_VERTS = 20 ;
	private  Vertex[] vertexList ; //存放顶点的数组
	private  int adjMat[][] ; //表示用矩阵的形式来表示边有没有
	private  int nVerts ; //当前的图中有多少个顶点了
	
	public Graph() {
		super();
		this.vertexList = new Vertex[this.MAX_VERTS];
		this.nVerts = 0 ;
    this.initialAdjMat () ; //初始化矩阵的
	}
	//初始化矩阵的
	private void initialAdjMat() {
		
		for (int i=0; i < this.MAX_VERTS; i++) {
			for (int j=0; j < this.MAX_VERTS; j++) {
				this.adjMat[i][j] = 0 ; //初始数组
			}
		}
		
	}
	//////////////////////////////////////////////////////////////////////////////////////////////
	//创建图 = 创建顶点和创建边，两个步骤是分开的
	//添加顶点
	public void addVertex(char lab) {
		
		Vertex ver = new Vertex(lab) ;
		this.vertexList[this.nVerts] = ver ;
		this.nVerts++ ;
		
	}
	
	//创建边(start 和 end 要有范围的 从0 到 N-1)
	public void addEdge(int start, int end) {
		
		this.adjMat[start][end] = 1 ;
		this.adjMat[end][start] = 1 ;
		
	}
   ///////////////////////////////////////////////////////////////////////////////////////////////////
	//显示一个顶点
	public void displayVertex(int v) {
		
		System.out.println(this.vertexList[v].getLabel()) ;
		
	}
	//////////////////////////////////////////////////////////////////////////////////////////////////
	/**
	 * 搜索
	 * 在图中实现的最基本的操作之一就是搜索从一个指定顶点可以到达哪些顶点可以到达哪些顶点。例如，可以想象要找出美国有多少个城市
	 * 可以从kansan乘坐旅行车到达（当然了中间是不能换车的）。一些城市可以直达，而有些城市因为没有旅行列车服务而不能到达。
	 * 有些地方即使有列子服务也不能到达，因为他们的铁轨不能和出发或者沿途的标准铁轨系统相连。
	 * 
	 * 还有一种情况就是需要找出所有的当前顶点可以到达的顶点。
	 * 假设有这么一张图，现在需要一种算法来提供系统的方法，从某个特定顶点开始，沿着边移动到其他顶点，移动完毕后，需要保证访问了喝
	 * 起始点相连的每一个顶点。
	 * 有两种常用的方法可以用来搜索图；深度优先搜索和广度优先搜索，他们最终都会到达所有连通的顶点
	 *
	 * 深度优先搜索通过栈来实现，而广度优先搜索通过队列实现。
	 * 
	 * 
	 * 深度优先搜索
	 * 
	 * 在搜索到尽头的时候，深度优先搜索用栈记住下一步的走向，这里展示了一个例子，
	 * 为了实现深度优先搜索，找到一个起始本例的顶点是A
	 * 需要做的三件事情：
	 * 首先是访问该顶点，然后是把该节点放入到栈中去，以便记住它
	 * 最后标记该节点，这样就不会再访问它了
	 * 下面就可以访问任何与顶点A相连的顶点了，只要还没有访问过它，假设顶点按字母顺序访问，所以下面访问顶点B。然后标记它，放入栈中。
	 *  已经访问过B，做相同的事情，找下一个为访问的节点的顶点，也就是F，这个过程就叫做规则1。
	 *  
	 *  规则1：
	 *       如果可能，访问一个邻接的未访问顶点，标记它，并把它放入到栈中。
	 *   
	 *   再次应用规则1，这次访问顶点H。然而，这里还需要做一些事情，因为没有和H邻接的未访问顶点。
	 *   
	 *   规则2.
	 *      当不能执行规则1的时候，如果栈不空，就从栈中探出一个顶点
	 *      
	 *       根据这条规则，从栈中探出H，这样就又回到了顶点F，F也没有和邻接且邻接没有访问的顶点了。那么再弹出F，这回到顶点B。这时
	 *  只有顶点A在栈中了。
	 *       然而A还没有访问过的连接点，所以访问下一个顶点C，但是C又是在这一条线路的终点，所以栈中弹出它，再次回到A点。接着访问D，G和I。
	 *  当到达I时，把它们都弹出栈，现在回到A然后访问E，最后再次回到A
	 *     
	 *   规则3
	 *      如果不能执行规则1 和规则 2，那么就完成了整一个深度搜索的过程了
	 *  栈的内容就是刚才起始顶点到各个顶点访问的整个过程。从起始顶点出发访问下一个顶点时，就是把这个顶点入栈，回到起始顶点，出栈
	 *  访问顶点的顺序是ABFHCDGIE
	 *  
	 *    深度优先搜索算法要得到距离起始点最远的顶点，然后再不能继续前进的时候返回，使用深度这个属于表示与起始点的距离，便可以理解深度优先
	 *    搜索的意义。
	 *    
	 *    模拟问题
	 *    
	 *    深度优先搜索与迷宫问题有类似的，迷宫在英国很流行，可以由一方给另一方设置障碍，由另一方想办法通过，迷宫由狭小的过道和过道的交汇点组成
	 *    
	 *                                                                                                                                             
	 *      JAVA代码 深度优先搜索的关键在于能够找到与某一顶点邻接且没有访问过的顶点。邻接矩阵是关键，找到指定顶点所在的行。第一列开始向后寻找值为1的列；
	 *      列号是邻接顶点的号码。检验这个顶点是不是被访问过的，如果是这样的，那么就是要访问的下个顶点，如果该行没有顶点既等于1，且又是没有访问过的，那么
	 *      与指定点相邻接的顶点就全部访问过了。这个过程在下面的代码中实现                                                                                                                                   
	 *                                                                                                                                             
	 * 
	 * 
	 */
	
	
	
	public int getAdjUnivisitedVertex(int v) { //从哪个顶点开始访问
		
		for(int j=0; j < this.nVerts; j++) {
			if (this.adjMat[v][j] == 1 && this.vertexList[j].isVisisted == false) {
				return j ;
			}
			
		}
		
		return -1 ;//如果没有访问到，那么返回-1 ；
	}
	
	//考察dfs（）方法，这个方法实际执行了深度的优先搜索。包含三条规则。它循环执行，知道栈为空，每次循环中，有四件事情
	/**
	 * 1. 用peek()方法检查栈顶的顶点
	 * 2. 试图找到这个顶点还未访问的邻接点
	 * 3. 如果找没有找到，出栈
	 * 4. 如果找到了这样的顶点，访问这个顶点，并且把它压入栈
	 */
	//深度搜索
	
	public void dfs() {
		
		Stack theStack = new Stack() ;
		//所谓遍历是从第一个顶点开始的 也是 vertesList[0]开始的
		this.vertexList[0].isVisisted = true ;
		this.displayVertex(0) ;
		theStack.push(0) ;
		
		while(!theStack.isEmpty()) {
			int v = this.getAdjUnivisitedVertex((Integer) theStack.peek()) ;
			if (-1 == v) { //已经被访问过的
				theStack.pop() ;//弹出一个
				
			}
			else {
				this.vertexList[v].isVisisted = true ;
				this.displayVertex(v) ;
				theStack.push(v) ;
			}
			
		}
	
		//stack 是空的话，就做
		for(int i=0; i < this.nVerts; i++) {
			
			this.vertexList[i].isVisisted = false ; //重新初始化节点，为下次的使用
		}
		
	}
	
	
	
		/**
	 * 广度优先搜索
	 * 
	 *   正如深度优先搜索中看到的，算法表现得好像要尽快地远离起始点的。相反，在广度优先搜索中，算法好像要尽可能地靠近起始点
	 *   它首先访问的是顶点的所有邻接点，然后再访问较远的区域。这种搜索不能用栈，只能用到队列来实现
	 *   
	 *   一个例子
	 *   
	 *   A是起始点，所有访问它，并且标记为当前空的顶点。然后应用下面几条规则
	 *   
	 *   规则1
	 *      访问下一个未来访问的邻接点（如果存在）, 这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中
	 *      （当前节点为改变）
	 *   规则2
	 *      如果因为已经没有未访问顶点而不能执行规则1， 那么从队列头取一个顶点（如果有），并且使得成为当前的顶点。
	 *      （当前节点改变了）
	 *   规则3
	 *      如果因为队列为空而不能执行规则2.那么广度优先搜索的到此就结束了
	 *      
	 *      
	 *      A-------B--------C------D
	 *       \       |      X
	 *        \      |      |
	 *         \-----e------F----G
	 *                     |  
	                       Y----H
	 
	   
	      在每一个时刻队列中包含的顶点是那些本身已经被访问，而它的邻居还未被访问的顶点。（对比深度优先搜索，栈的内容是起始点
	      到当前顶点经过的所有顶点）顶点访问的顺序。
	      
	     深度优先遍历和广度优先遍历的异同点 
	       可以认为广度优先搜索就像往水中投入石块，水波纹扩展的过程===对于喜爱流行病学的人来说，就好比流感通过航空旅行客从一个城市
	       到另一个城市了。首先是相距起始点只有一条边的所有顶点被访问，然后是相距两条边的所有顶点被访问，一次类推
	       
	 */
	
	
	
	//广度搜索与深度类似的，只是用队列代替了栈，嵌套的循环代替了单层循环。外层循环等待队列为空，而内层循环依次寻找当前顶点的未访问邻接点
    //下面是代码
	
	public  void bfs() {
		
		Queue theQueue = new LinkedList();  
		
		this.vertexList[0].isVisisted = true ;
		this.displayVertex(0) ;
		theQueue.add(0) ;
		
		int v2 ;
		
		while (!theQueue.isEmpty()) {
			
			int v1 = (Integer) theQueue.remove() ;
			v2 = this.getAdjUnivisitedVertex(v1) ;
			while (v2 != -1) {
				
				this.vertexList[v2].isVisisted = true ;
				this.displayVertex(v2) ;
				theQueue.add(v2) ;
			}
			
		}
		
		for(int i=0; i < this.nVerts; i++) {
			
			this.vertexList[i].isVisisted = false ; //重新初始化节点，为下次的使用
		}
	}
	
	
	
	
	
	
	
	
	
	
	
}