# 用邻接表实现图的深度优先遍历、广度优先遍历、最短路径（无权图）

```import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Graph {

/**关键字：图 邻接表 深度优先遍历 广度优先遍历 最短路径
* 1.Graph is a collection of Vertex and Edge.
* When you want to implement 'Graph',you deal with two missions:how to implement 'Vertex' and 'Edge'
*  a.Vertex:
*    Type label-->Vertex's ID,to separate one Vertex from another,like 'A','B',or 0,1,2
*    ...<output omit>
*  b.Edge(as Inner class of Vertex):
*    endVertex-->(begin,end),the outer class is 'begin',endVertex is 'end'
*    ...<output omit>
* 2.In the following,we
*  a.use ArrayList to store Vertices
*  b.use 'char' as Vertex's ID
*/
private List<Vertex> vertices;
private int edgeCount;
private List<Vertex> depthFirstResult;

Vertex origin=this.getVertexByChar(beginLabel);
if(origin==null)return;
origin.setVisited(true);
Vertex curVertex=null;
while(!queue.isEmpty()){
curVertex=queue.remove(0);
while(curVertex.getFirstUnvisitedNeighbor()!=null){
Vertex tmpVertex=curVertex.getFirstUnvisitedNeighbor();
tmpVertex.setVisited(true);
}

}
}

public void depthFirstVisit(char beginLabel){

Vertex origin=this.getVertexByChar(beginLabel);
if(origin==null)return;
Stack<Vertex> stack=new Stack<Vertex>();
origin.setVisited(true);
stack.push(origin);
Vertex curVertex=null;
while(!stack.isEmpty()){
curVertex=stack.peek();
Vertex tmpVertex=curVertex.getFirstUnvisitedNeighbor();
if(tmpVertex!=null){
tmpVertex.setVisited(true);
stack.push(tmpVertex);
}else{
stack.pop();
}
}
printVertexList(depthFirstResult);
}

//getShortestPath.Base on breadthFirstVisit.the edge has no weight.
public double getShortestPath(char beginLabel,char endLabel,Stack<Vertex> stack){
resetVertices();
Vertex begin=this.getVertexByChar(beginLabel);
Vertex end=this.getVertexByChar(endLabel);
begin.setVisited(true);
boolean done=false;
while(!done&&!queue.isEmpty()){
Vertex curVertex=queue.remove(0);
while(!done&&curVertex.getFirstUnvisitedNeighbor()!=null){
Vertex tmpVertex=curVertex.getFirstUnvisitedNeighbor();
tmpVertex.setVisited(true);
double	tmpCost=curVertex.getCost()+1;
tmpVertex.setPreviousVertex(curVertex);
tmpVertex.setCost(tmpCost);
if(tmpVertex.equals(end)){
done=true;
}
}
}
double pathLength=end.getCost();
//find the path.traverse back from end
while(end!=null){
stack.push(end);
end=end.getPreviousVertex();
}
return pathLength;
}

public boolean addEdge(char beginLabel,char endLabel,double weight){
int beginIndex=vertices.indexOf(new Vertex(beginLabel));
int endIndex=vertices.indexOf(new Vertex(endLabel));
Vertex beginVertex=vertices.get(beginIndex);
Vertex endVertex=vertices.get(endIndex);
boolean result=beginVertex.connect(endVertex,weight);
edgeCount++;
return result;
}
}
boolean result=false;
Vertex newVertex=new Vertex(label);
if(!vertices.contains(newVertex)){
result=true;
}
return result;
}
public void printVertexList(List<Vertex> list){
for(int i=0,len=list.size();i<len;i++){
Vertex vertex=list.get(i);
System.out.print(vertex.getLabel()+" ");
}
System.out.println();
}

public void resetVertices(){
for(int i=0,len=vertices.size();i<len;i++){
Vertex vertex=vertices.get(i);
vertex.setPreviousVertex(null);
vertex.setVisited(false);
vertex.setCost(0);
}
}

public Vertex getVertexByChar(char target){
Vertex vertex=null;
for(int i=0,len=vertices.size();i<len;i++){
vertex=vertices.get(i);
Character xx=vertex.getLabel();
if(xx.charValue()==target){
return vertex;
}
}
return vertex;
}

public Graph(){
vertices=new ArrayList<Vertex>();
edgeCount=0;
depthFirstResult=new ArrayList<Vertex>();
}

public static void main(String[] args) {

Graph graph=createGapth();
graph.resetVertices();

//shortest path
Stack<Vertex> pathStack=new Stack<Vertex>();
//from '0' to '7'.
double pathLength=graph.getShortestPath('0','7',pathStack);
System.out.println(pathLength);
while(!pathStack.isEmpty()){
Vertex vertex=pathStack.pop();
System.out.print(vertex.getLabel()+" ");
}

//BasicGraphInterface<String> airMap=new UndirectedGraph<String>();
//airMap.

}

public static Graph createGapth(){
/*
0----1---2
| \  |	  |
|  \ |   |
|   \|   |
3	  4	  5
|	 /
|  /
| /
6---7
0-->4--3--1
1-->4--2--0
2-->5--1
3-->6--0
4-->6--1--0
5-->2
6-->7--4--3
7-->6
*/

Graph graph=new Graph();

return graph;
}
}

class Vertex{
private char label;
private List<Edge> edgeList;
private boolean isVisited;
private Vertex previousVertex;//use it in the method-'getShortestPath()'
private double cost;//the cost from beginning to this vertex

public Vertex(char label){
this.label=label;
edgeList=new ArrayList<Edge>();
isVisited=false;
previousVertex=null;
cost=0;
}
public boolean isVisited(){
return isVisited;
}
public void visit(){
System.out.println(this.label);
this.isVisited=true;
}

public void setPreviousVertex(Vertex vertex){
this.previousVertex=vertex;
}
public void setVisited(Boolean isVisited){
this.isVisited=isVisited;
}
public void setCost(double cost){
this.cost=cost;
}
public Vertex getFirstNeighbor(){
Vertex neighbor=this.edgeList.get(0).endVertex;
return neighbor;
}
public char getLabel(){
return this.label;
}

public double getCost(){
return this.cost;
}
public Vertex getPreviousVertex(){
return this.previousVertex;
}
public Vertex getFirstUnvisitedNeighbor(){
Vertex unVisitedNeighbor=null;
for(int i=0,len=edgeList.size();i<len;i++){
Vertex vertex=edgeList.get(i).endVertex;
if(!vertex.isVisited){
unVisitedNeighbor=vertex;
break;
}
}
return unVisitedNeighbor;
}
public boolean equals(Object object){
boolean result=false;
if(this==object)return true;
if(object instanceof Vertex){
Vertex otherVertex=(Vertex)object;
result=this.label==otherVertex.label;
}
return result;
}
public boolean connect(Vertex endVertex,double weight){

boolean result=false;//result=true if successful

if(!this.equals(endVertex)){//connections should occur in different Vertices
boolean isDuplicateEdge=false;
List<Edge> edgeList=this.edgeList;
if(edgeList.contains(endVertex)){
isDuplicateEdge=true;
}
if(!isDuplicateEdge){
//endVertex.previousVertex=this;
result=true;
}
}

return result;
}

public boolean hasNeighbor(){
return !edgeList.isEmpty();
}
protected  class Edge{
//A-->B,then the "outerClass" which invokes the method "getEndVertex"
//is "A",the "endVertex" is "B"
private Vertex endVertex;
private double weight;

protected Edge(Vertex endVertex,double weight){
this.endVertex=endVertex;
this.weight=weight;
}
protected Vertex getEndVertex(){
return endVertex;
}
protected double getWeight(){
return weight;
}

}
}
```

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

1.调用代码入口： using System; namespace 图_图的遍历 { internal class Program { private stati

// 无向图的广度优先搜索（采用邻接表存储）.cpp : Defines the entry point for the console appli
// 无向图的广度优先搜索（采用邻接表存储）.cpp : Defines the entry point for the console appli