图是用于对数据间关系进行编码的一种机制，是与树有些相似的数据结构。
图分为：
有向图、无向图。
连通图、非连通图。
带权图、无全图。
图的搜索：
深度优先搜索（DFS）
广度优先搜索（BFS）
二、下面用代码来实现
1、先将图的基本构成实现了
/**
* Created by xi on 2017/8/19.
* 图
*/
public class Graph {
private final int MAX_VERTS=20;//最大顶点树
private Vertex[] vertexList;//顶点数组
private int adjMat[][];//邻接矩阵，即顶点之间的关系矩阵
private int nVerts;//当前顶点数量
private StackGraph theStack;//深度优先搜索用的栈
private QueueGraph theQueue;//广度优先搜索用的队列
public Graph(){
//初始化上述对象
vertexList=new Vertex[MAX_VERTS];
adjMat=new int[MAX_VERTS][MAX_VERTS];
for(int j=0;j<MAX_VERTS;j++){
for(int k=0;k<MAX_VERTS;k++){
adjMat[j][k]=0;
}
}
theStack=new StackGraph(MAX_VERTS);
theQueue=new QueueGraph(MAX_VERTS);
}
/**
* 添加顶点
*/
public void addVertex(char lab){
vertexList[nVerts++]=new Vertex(lab);
}
/**
* 添加边
*/
public void addEdge(int start,int end){
adjMat[start][end]=1;
adjMat[end][start]=1;
}
/**
* 展示顶点
*/
public void displayVertex(int v){
Log.v("Graph",vertexList[v].label+"");
}
/**
* 获取指定顶点相邻的一个未被访问过的顶点
* @param v
* @return
*/
private int getAdjUnvisitedVertex(int v){
for(int j=0;j<nVerts;j++)
if(adjMat[v][j]==1&&vertexList[j].wasVisited==false)
return j;//找到一个与v顶点相邻接的未访问的顶点位置
return -1;//未找到
}
｝
package com.tool.wpn.quicksort;
/**
* Created by Xi on 2017/7/29.
* 栈-图深度搜索用
*/
public class StackGraph {
private int[] stackArray;
private int maxSize;//栈最大容量
private int top;//栈顶
public StackGraph(int size){
maxSize=size;
stackArray=new int[maxSize];
top=-1;
}
/**
* 添加元素
*/
public void push(int element){
stackArray[++top]=element;
}
/**
* 查看并删除
*/
public int pop(){
return stackArray[top--];
}
/**
* 查看
*/
public int peek(){
return stackArray[top];
}
/**
* 是否为空
*/
public boolean isEmpty(){
return top==-1;
}
}
package com.tool.wpn.quicksort;
import android.util.Size;
/**
* Created by Xi on 2017/7/29.
* 队列-图广度搜索用
*/
public class QueueGraph {
private int[] queArray;
private int maxSize;//队列最大值
private int front;//队首
private int rear;//队尾
public QueueGraph(int size){//用户指定队列最大数
maxSize=size;
queArray=new int[maxSize];
front=0;//默认对首为0，因为队列里没有元素
rear=-1;//默认队尾为-1
}
/**
* 插入元素，调用该接口之前需判断队列是否已满。
*/
public void insert(int element){
if(rear==maxSize-1)
rear=-1;//若元素以插到数组最后一位，则重置rear;
queArray[++rear]=element;
}
/**
* 删除元素，调用该接口之前需判断队列是否有元素
*/
public int remove(){
int temp=queArray[front++];//取出被删除的元素放入临时变量中，
if(front==maxSize)
front=0;//若以将队列中元素删除完，就重置front;
return temp;
}
/**
* 访问元素
*/
public long peekFront(){
return queArray[front];
}
/**
* 队列是否为空
*/
public boolean isEmpty(){
return (rear+1==front||front+ maxSize-1==rear);
}
}
2、下面在Graph类中实现深度优先搜索方法，代码如下
/**
* 深度优化搜索
*/
public void dfs(){
vertexList[0].wasVisited=true;//第一个顶点被访问后将标志修改为访问过
displayVertex(0);//显示访问的顶点
theStack.push(0);//将访问过的顶点放入栈中
while(!theStack.isEmpty()){//栈不为空
int v=getAdjUnvisitedVertex(theStack.peek());
if(v==-1)//未找到
theStack.pop();//从栈中移除
else{
vertexList[v].wasVisited=true;
displayVertex(v);
theStack.push(v);//添加到栈中，继续找
}
}
//深度搜索完毕后，将图中各个顶点状态恢复为未被访问过
for(int j=0;j<nVerts;j++){
vertexList[j].wasVisited=false;
}
}
3、下面在Graph类中实现广度优先搜索方法，代码如下
/**
* 广度优先搜索
*/
public void bfs(){
vertexList[0].wasVisited=true;//第一个顶点被访问后将标志修改为访问过
displayVertex(0);//显示访问的顶点
theQueue.insert(0);//将访问过的顶点放入栈中
int v2;
while(!theQueue.isEmpty()){//队列不为空
int v1=theQueue.remove();
while((v2=getAdjUnvisitedVertex(v1))!=-1){
vertexList[v2].wasVisited=true;
displayVertex(v2);
theQueue.insert(v2);
}
}
//广度搜索完毕后，将图中各个顶点状态恢复为未被访问过
for(int j=0;j<nVerts;j++){
vertexList[j].wasVisited=false;
}
}
3、下面在Graph类中实现最小生成树方法，代码如下
/**
* 最小生成树
*/
public void mst(){
vertexList[0].wasVisited=true;
theStack.push(0);
while(!theStack.isEmpty()){
int currentVertex=theStack.peek();
int v=getAdjUnvisitedVertex(currentVertex);
if(v==-1)//没有找到邻接的没有访问过的顶点
theStack.pop();
else{
vertexList[v].wasVisited=true;
theStack.push(v);
displayVertex(currentVertex);
displayVertex(v);
Log.v("Graph"," ");
}
}
//最小生成树完毕后，将图中各个顶点状态恢复为未被访问过
for(int j=0;j<nVerts;j++){
vertexList[j].wasVisited=false;
}
}
三、测试上述功能，在主函数中的调用如下：
private void graph(){
Graph theGraph=new Graph();//创建图
//添加顶点
theGraph.addVertex('A');
theGraph.addVertex('B');
theGraph.addVertex('C');
theGraph.addVertex('D');
//添加边
theGraph.addEdge(0,1);//AB边
theGraph.addEdge(0,2);//AC边
theGraph.addEdge(0,3);//AD边
theGraph.addEdge(1,3);//BD边
Log.v(TAG,"Visits深度优先搜索结果:");
theGraph.dfs();//深度搜索
Log.v(TAG,"Visits广度优先搜索结果:");
theGraph.bfs();
//最小生成树
Graph myGraph=new Graph();
//添加顶点
myGraph.addVertex('A');
myGraph.addVertex('B');
myGraph.addVertex('C');
myGraph.addVertex('D');
myGraph.addVertex('E');
//添加边
myGraph.addEdge(0,1);//AB边
myGraph.addEdge(0,2);//AC边
myGraph.addEdge(0,3);//AD边
myGraph.addEdge(0,4);//AE边
myGraph.addEdge(1,2);//BC边
myGraph.addEdge(1,3);//BD边
myGraph.addEdge(1,4);//BE边
myGraph.addEdge(2,3);//CD边
myGraph.addEdge(2,4);//CE边
myGraph.addEdge(3,4);//DE边
Log.v(TAG,"Minimu spanning tree:");
myGraph.mst();
}
日志打印如下：
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/MainActivity: Visits深度优先搜索结果:
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: A
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: B
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: D
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: C
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/MainActivity: Visits广度优先搜索结果:
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: A
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: B
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: C
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: D
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/MainActivity: Minimu spanning tree:
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: A
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: B
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph:
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: B
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: C
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph:
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: C
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: D
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph:
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: D
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph: E
08-20 16:52:19.328 8297-8297/com.tool.wpn.quicksort V/Graph:
源码下载地址：点击打开链接