目录
图的创建和常用方法
深度优先遍历（Depth First Search）
广度优先遍历（Broad First Search）
图的创建和常用方法
//无向图
public class Graph {
//顶点集合
private ArrayList<String> vertexList;
//存储对应的邻接矩阵
private int[][] edges;
//边数
private int numOfEdges;
//构造方法
//传入顶点数
public Graph(int numOfVertex) {
this.vertexList = new ArrayList<>(numOfVertex);
this.edges = new int[numOfVertex][numOfVertex];
this.numOfEdges = 0;//边数初始为0
}
//添加顶点
public void interVertex(String vertex){
vertexList.add(vertex);
}
//添加边
public void interEdge(int v1,int v2,int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
//图中常用方法：
//返回节点的个数
public int getNumOfVertex(){
return vertexList.size();
}
//得到边的数目
public int getNumOfEdges(){
return numOfEdges;
}
//返回节点i对应的数据，以添加的顺序为准
public String getValueByIndex(int i){
return vertexList.get(i);
}
//返回v1，v2的权值
public int getWeight(int v1,int v2){
return edges[v1][v2];
}
//显示图所对应的矩阵
public void showGraph(){
for(int[] link:edges){
System.out.println(Arrays.toString(link));
}
}
//测试
public static void main(String[] args) {
int n = 5;
String[] vertexs={"A","B","C","D","E"};
Graph graph = new Graph(n);
//添加顶点
for(String vertex:vertexs){
graph.interVertex(vertex);
}
//添加边：A-C A-B A-E B-D
graph.interEdge(0,2,1);
graph.interEdge(0,1,1);
graph.interEdge(0,4,1);
graph.interEdge(1,3,1);
graph.showGraph();
}
}
邻接矩阵：
深度优先遍历（Depth First Search）
深度优先：每次访问当前节点后，首先访问当前节点的第一个邻接矩阵
添加标记顶点是否访问的数组：
private boolean[] isVisted;在构造方法中初始化：
this.isVisted = new boolean[numOfVertex];得到第一个邻接节点的下标w：
//得到第一个邻接节点的下标w
public int getFirstNeighbor(int index){
for (int j = 0; j< vertexList.size(); j++) {
if (edges[index][j]>0){
return j;
}
}
return -1;
}根据前一个节点的坐标获取下一个邻接节点：
//根据前一个节点的坐标获取下一个邻接节点
public int getNextNeighbor(int v1,int v2){
for (int j = v2+1; j < vertexList.size(); j++) {
if (edges[v1][j]>0)return j;
}
return -1;
}深度优先遍历：
//深度优先遍历
private void dfs(boolean[] isVisted,int i){
//首先访该节点，输出
System.out.print(getValueByIndex(i)+"->");
//访问标记
isVisted[i] = true;
//访问节点的第一个邻接节点
int w = getFirstNeighbor(i);
while (w!=-1){
//有的话并且没有被访问过，就遍历该节点
if (!isVisted[w]){
dfs(isVisted,w);
}
//如果已经被访问过，就访问下一个
w = getNextNeighbor(i,w);
}
}若是非连通图（有孤立点），需要将每个顶点深度遍历：
//若是非连通图，需要将每个顶点深度遍历
public void dfs(){
for (int i = 0; i < vertexList.size(); i++) {
if (!isVisted[i]){
dfs(isVisted,i);
}
}
}如下图的深度遍历：
//测试
public static void main(String[] args) {
int n = 6;
String[] vertexs={"A","B","C","D","E","F"};
Graph graph = new Graph(n);
//添加顶点
for(String vertex:vertexs){
graph.interVertex(vertex);
}
//添加边：A-C A-B A-E B-D
graph.interEdge(0,2,1);
graph.interEdge(0,1,1);
graph.interEdge(0,4,1);
graph.interEdge(1,3,1);
graph.showGraph();
graph.dfs();
}
广度优先遍历（Broad First Search）
广度优先：先访问所有直接相邻的节点，然后访问所有与这些节点相邻的节点，以此类推，直到遍历完整个图。
//广度优先遍历
//对一个节点进行广度优先算法
private void bfs(boolean[] isVisted,int i){
int u;//队列头结点的下标
int w;//邻接节点
LinkedList queue = new LinkedList();
// 访问节点，输出
System.out.print (getValueByIndex(i)+"=>");
// 标记已访问
isVisted[i]=true;
// 添加到队列
queue.addLast(i);
while (!queue.isEmpty()){
u = (Integer) queue.removeFirst();
//得到第一个邻接节点的下标
w = getFirstNeighbor(u);
while (w!=-1){
if (!isVisted[w]){
//没有访问过
System.out.print(getValueByIndex(w)+"=>");
isVisted[w] = true;
queue.addLast(w);
}
//以u为前一个节点，访问过去下一个节点
w = getNextNeighbor(u, w);
}
}
}
//非连通图 广度优先遍历
public void bfs(){
this.isVisted = new boolean[vertexList.size()];
for (int i = 0; i < vertexList.size(); i++) {
if (!isVisted[i]){
bfs(isVisted,i);
}
}
}测试：
System.out.println("广度优先");
graph.bfs();
深度和广度测试：
public static void main(String[] args) {
int n = 8;
String[] vertexs={"1","2","3","4","5","6","7","8"};
Graph graph = new Graph(n);
//添加顶点
for(String vertex:vertexs){
graph.interVertex(vertex);
}
//添加边：1-2 1-3 2-4 2-5 4-8 5-8 3-6 3-7
graph.interEdge(0,1,1);
graph.interEdge(0,2,1);
graph.interEdge(1,3,1);
graph.interEdge(1,4,1);
graph.interEdge(3,7,1);
graph.interEdge(4,7,1);
graph.interEdge(2,5,1);
graph.interEdge(2,6,1);
graph.showGraph();
System.out.println("深度优先");
graph.dfs();
System.out.println();
System.out.println("广度优先");
graph.bfs();
} 
