1 package com.gxf.graph;  2   3 /**  4  * 定义一个图类  5  * 包过构造方法  6  * 插入顶点  7  * 插入边  8  * 深度优先遍历  9  * 广度优先遍历 10  * @author Administrator 11  * 12  */ 13 public class Graph { 14     int n; 15     int max;//当前顶点数和最大定点数 16     VexNode adjlist[];//邻接链表存储结构 17     boolean visited[];//标记顶点访问状态 18      19     /** 20      * 构造一个长度为l的邻接链表 21      * @param l 22      */ 23     public Graph(int l){ 24         n = 0; 25         max = l; 26         adjlist = new VexNode[l]; 27         visited = new boolean[l]; 28     } 29      30     /** 31      * 递归调用实现深度优先遍历 32      * @param v0待遍历结点 33      * @param vs访问函数类对象 34      */ 35     public void dfs0(int v0, Visit vs){ 36         ArcNode p = adjlist[v0].firstArc;//node边结点 37          38         if(!visited[v0]){//结点没有被访问过 39             vs.visit(v0);//访问这个结点 40             visited[v0] = true;//标记结点已经被访问 41         } 42         while(null != p){ 43             int v = p.adjvex; 44             if(!visited[v])  45                 dfs0(v, vs);//邻接顶点没有被访问，深度访问该顶点 46             p = p.next;//深度访问结束，回退访问下一个邻接顶点 47         } 48     } 49      50     /** 51      * 向类的调用者提供一个调用接口 52      * 初始化visited[] 53      * 调用dfs0(int, vs) 54      * @param v0 55      * @param vs 56      */ 57     public void dfs(int v0, Visit vs){ 58         for(int i = 0; i < max; i++){ 59             visited[i] = false; 60         }//初始化visited[]数组 61         dfs0(v0, vs); 62     } 63      64     /** 65      * 广度优先遍历 66      * 邻接链表用的是数组存储，只要用int节可以找到v0对应的顶点 67      * @param v0 68      * @param vs 69      */ 70     public void bfs(int v0, Visit vs){ 71         int front = 0; 72         int rear = 0;//队列头尾指针初始化为0 73         int queue[] = new int[100];//队列 74         int headVex; 75          76         //没有递归调用可以初始化visited[]数组 77         for(int i = 0; i < max; i++){ 78             visited[i] = false; 79         } 80          81         vs.visit(v0); 82         visited[v0] = true;//访问v0顶点，访问过的顶点入队，队列里所有顶点都是访问过的  83         queue[rear++] = v0;//顶点入队 84          85         while(front != rear){//队列不为空 86             headVex = queue[front++];//出队 队列里面都是访问过的顶点 87             ArcNode firstArc = adjlist[headVex].firstArc;//第一条边结点 88             while(null != firstArc){//边结点不为空，有邻接点 89                 if(!visited[firstArc.adjvex]){//邻接顶点没有被访问过 90                     vs.visit(firstArc.adjvex);//访问邻接顶点 91                     visited[firstArc.adjvex] = true; 92                     queue[rear++] = firstArc.adjvex;//入队 93                 } 94                 firstArc = firstArc.next;//下一个邻接顶点 95             } 96         } 97     } 98     /** 99      * 向图中插入一个顶点100      * @param data101      */102     public void insertVex(int data){103         if(n < max){//没有超过最大定点数104             VexNode vexInsert = new VexNode();105             vexInsert.data =http://www.mamicode.com/ data;106             adjlist[n++] = vexInsert;107             vexInsert.firstArc = null;108             //n++;109         }110     }111     112     /**113      * 在顶点v0和v1中间插入一条边结点114      * 在v0和v1的链表中都需要插入一个边结点115      * @param v0116      * @param v1117      */118     public void insertEdge(int v0, int v1){119         ArcNode arcNode0 = new ArcNode();//插入v0链表中的边结点120         ArcNode arcNode1 = new ArcNode();//插入v1链表中的边结点121         122         VexNode vex0 = adjlist[v0];123         124         VexNode vex1 = adjlist[v1];125         126         arcNode0.next = vex0.firstArc;127         arcNode1.next = vex1.firstArc;128         129         vex0.firstArc = arcNode0;130         vex1.firstArc = arcNode1;//采用头插法插入到链表中131         132         arcNode0.adjvex = v1;133         arcNode1.adjvex = v0;134     }135 }

 1 package com.gxf.graph; 2  3 /** 4  * 邻接链表中顶点类 5  * data结点内容 6  * firstArc第一条边结点 7  * @author Administrator 8  * 9  */10 public class VexNode {11     int data;12     ArcNode firstArc;13 14 }15 /**16  * 邻接链表中边结点类17  * 一条边对应一个ArcNode18  * adjnode邻接顶点19  * next下一条边20  * @author Administrator21  *22  */23 class ArcNode{24     int adjvex;25     ArcNode next;26 }

 1 package com.gxf.graph; 2  3 public class Visit { 4     public String nodeString; 5     public Visit(){ 6         nodeString = new String(); 7     } 8      9     public void visit(int v){10         nodeString += v + " ";11 //        System.out.print(v + " ");12     }13     public String toString(){14         return nodeString;15     }16 }

 1 package com.gxf.graph; 2  3 /** 4  * 测试图的DFS和BFS 5  * 插入四个顶点 6  * 插入边形成连通图 7  * @author Administrator 8  * 9  */10 public class Test {11 12     public static void main(String[] args) {13         Graph graph = new Graph(10);//创建四个顶点的图14         Visit visit = new Visit();15         //插入四个顶点16         for(int i = 0; i < 4; i++){17             graph.insertVex(i);18         }19         //插入边20         graph.insertEdge(0, 1);21         graph.insertEdge(1, 2);22         graph.insertEdge(2, 3);23         graph.insertEdge(3, 0);//插入四条边，形成连通图24         System.out.println("深度优先遍历:");25         graph.dfs(0, visit);26 //        System.out.println();27         System.out.println(visit.toString());28         System.out.println("广度优先遍历：");29         visit = new Visit();30         graph.bfs(0, visit);31         System.out.println(visit.toString());32 33     }34 35 }