Java数据结构之图的原理与实现

第Java数据结构之图的原理与实现*深度优先搜索遍历图的递归实现,类似于树的先序遍历

*因此模仿树的先序遍历,同样借用栈结构,这里使用的是方法的递归,隐式的借用栈

*@parami顶点索引

*@paramvisited访问标志数组

privatevoidDFS(inti,boolean[]visited){

//索引索引标记为true,表示已经访问了

visited[i]=true;

System.out.print(vertexs[i].data+"");

//获取该顶点的边表头结点

LNodenode=vertexs[i].firstEdge;

//循环遍历该顶点的邻接点,采用同样的方式递归搜索

while(node!=null){

if(!visited[node.vertex]){

DFS(node.vertex,visited);

node=node.nextEdge;

*深度优先搜索遍历图,类似于树的前序遍历,

publicvoidDFS(){

//新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点

boolean[]visited=newboolean[vertexs.length];

//初始化所有顶点都没有被访问

for(inti=0;ivertexs.length;i++){

visited[i]=false;

System.out.println("DFS:");

/*循环搜索*/

for(inti=0;ivertexs.length;i++){

//如果对应索引的顶点的访问标记为false,则搜索该顶点

if(!visited[i]){

DFS(i,visited);

/*走到这一步,说明顶点访问标记数组全部为true,说明全部都访问到了,深度搜索结束*/

System.out.println();

*广度优先搜索图,类似于树的层序遍历

*因此模仿树的层序遍历,同样借用队列结构

publicvoidBFS(){

//辅组队列

QueueIntegerindexLinkedList=newLinkedList();

//新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点

boolean[]visited=newboolean[vertexs.length];

//初始化所有顶点都没有被访问

for(inti=0;ivertexs.length;i++){

visited[i]=false;

System.out.println("BFS:");

for(inti=0;ivertexs.length;i++){

//如果访问方剂为false,则设置为true,表示已经访问,然后开始访问

if(!visited[i]){

visited[i]=true;

System.out.print(vertexs[i].data+"");

indexLinkedList.add(i);

//判断队列是否有值,有就开始遍历

if(!indexLinkedList.isEmpty()){

//出队列

Integerj=indexLinkedList.poll();

LNodenode=vertexs[j].firstEdge;

while(node!=null){

intk=node.vertex;

if(!visited[k]){

visited[k]=true;

System.out.print(vertexs[k].data+"");

//继续入队列

indexLinkedList.add(k);

node=node.nextEdge;

System.out.print("\n");

@Override

publicStringtoString(){

StringBuilderstringBuilder=newStringBuilder();

for(inti=0;ivertexs.length;i++){

stringBuilder.append(i).append("(").append(vertexs[i].data).append("):");

LNodenode=vertexs[i].firstEdge;

while(node!=null){

stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append(")");

node=node.nextEdge;

if(node!=null){

stringBuilder.append("-

}else{

break;

stringBuilder.append("\n");

returnstringBuilder.toString();

publicstaticvoidmain(String[]args){

//顶点数组添加的先后顺序对于遍历结果有影响

Character[]vexs={'A','B','C','D','E','F','G'};

//边二维数组添加的先后顺序对于遍历结果有影响

Character[][]edges={

{'A','C'},

//对于无向图来说是多余的边关系,在linkLast方法中做了判断,并不会重复添加

{'A','D'},

{'A','D'},

{'D','A'},

{'A','F'},

{'B','C'},

{'C','D'},

{'E','G'},

{'E','B'},

{'D','B'},

{'F','G'}};

//构建图

UndirectedAdjacencyListCharacterundirectedAdjacencyList=newUndirectedAdjacencyList(vexs,edges);

//输出图

System.out.println(undirectedAdjacencyList);

//深度优先遍历

undirectedAdjacencyList.DFS();

//广度优先遍历

undirectedAdjacencyList.BFS();

}

测试无向图对应的逻辑结构如下：

测试图的遍历结果如下：

4.2有向图的邻接表实现

/**

*有向图邻接链表简单实现

*{@linkAdjacencyList#AdjacencyList(E[],E[][])}构建有向图

*{@linkAdjacencyList#DFS()}深度优先遍历有向图

*{@linkAdjacencyList#BFS()}广度优先遍历有向图

*{@linkAdjacencyList#toString()}()}输出有向图

*@authorlx

publicclassAdjacencyListE{

*顶点类

*@paramE

privateclassNodeE{

*顶点信息

Edata;

*指向第一条依附该顶点的边

LNodefirstEdge;

publicNode(Edata,LNodefirstEdge){

this.data=data;

this.firstEdge=firstEdge;

*边表节点类

privateclassLNode{

*该边所指向的顶点的索引位置

intvertex;

*指向下一条弧的指针

LNodenextEdge;

*顶点数组

privateNodeE[]vertexs;

*创建图

*@paramvexs顶点数组

*@paramedges边二维数组

publicAdjacencyList(E[]vexs,E[][]edges){

/*初始化顶点数组,并添加顶点*/

vertexs=newNode[vexs.length];

for(inti=0;ivertexs.length;i++){

vertexs[i]=newNode(vexs[i],null);

/*初始化边表,并添加边节点到边表尾部,即采用尾插法*/

for(E[]edge:edges){

//读取一条边的起始顶点和结束顶点索引值

intp1=getPosition(edge[0]);

intp2=getPosition(edge[1]);

//初始化lnode1边节点即表示p1指向p2的边

LNodelnode1=newLNode();

lnode1.vertex=p2;

//将LNode链接到"p1所在链表的末尾"

if(vertexs[p1].firstEdge==null){

vertexs[p1].firstEdge=lnode1;

}else{

linkLast(vertexs[p1].firstEdge,