图的存储，搜索，遍历，广度优先算法和深度优先算法，最小生成树-Java实现

1）用邻接矩阵方式进行图的存储。如果一个图有n个节点，则可以用n*n的二维数组来存储图中的各个节点关系。

对上面图中各个节点分别编号，ABCDEF分别设置为012345。那么AB AC AD 关系可以转换为01 02 03， BC BE BF 可以转换为12 14 15， EF可以转换为45。换句话所，我们将各个节点关系存储在一个n*n的二位数组中，数组下标分别对应A-F，有关系的两个节点，在数组中用1表示，否则用0表示。这上图关系可以用6*6数组表示为：

图的存储，搜索，遍历，广度优先算法和深度优先算法，最小生成树-Java实现

2）深度优先进行图的遍历以及将图转换为最小生成树

深度优先的原则是从根节点开始，依次寻找后继的第一个子节点，直到没有后继为止。然后回到根节点，寻找根的第二个子节点，然后再依次寻找他的后继，直到没有后继为止。以此类推，直到所有节点都被遍历为止。实现深度优先遍历，有一个回朔的过程，所以需要用栈这种数据结构。

3）广度优先进行图的遍历以及将图转换为最小生成树

广度优先原则是从根节点开始，先将根的所有后继找出来，然后依次将所有后继的后继再找出来。以此类推，直到所有元素节点都被遍历。实现广度优先，是一个顺序过程，所以这里需要用到队列或者链表这种数据结构。

下面是代码实现:

  1 package org.lyk.impl;
  2 
  3 import java.util.ArrayList;
  4 import java.util.Queue;
  5 import java.util.Stack;
  6 
  7 public class Graph
  8 {
  9     private class Node
 10     {
 11         private boolean wasVisited;
 12         private char data;
 13         
 14         public Node(char data)
 15         {
 16             this.data = data;
 17             this.wasVisited= false;
 18         }
 19     }
 20     
 21     private Node[] nodes;
 22     private int[][] adjMetrix;
 23     private int maxSize;
 24     private int index;
 25     public Graph()
 26     {
 27         this.maxSize = 6;
 28         this.index = 0;
 29         this.nodes= new Node[this.maxSize];
 30         this.adjMetrix = new int[this.maxSize][this.maxSize];
 31     }
 32     
 33     /**
 34      * 增加节点
 35      * @param data
 36      * @throws Exception
 37      */
 38     public void add(char data) throws Exception
 39     {
 40         if(this.index >= this.maxSize)
 41         {
 42             throw new Exception("数组已满");
 43         }
 44         else
 45         {
 46             this.nodes[index++]= new Node(data);
 47         }
 48     }
 49     
 50     /**
 51      * 设置图中各个节点关系
 52      * @param x
 53      * @param y
 54      * @throws Exception
 55      */
 56     public void setRelation(int x,int y) throws Exception
 57     {
 58         if(x < this.maxSize && y < this.maxSize)
 59         {
 60             this.adjMetrix[x][y] = 1;
 61             this.adjMetrix[y][x] = 1;
 62         }
 63         else
 64         {
 65             throw new Exception("下标错误!");
 66         }
 67     }
 68     
 69     /**
 70      * 广度优先对图进行遍历
 71      * @param x
 72      * @throws Exception
 73      */
 74     public void showBreathFirst(int x) throws Exception
 75     {
 76         if(x >= 0 && x < this.index)
 77         {
 78             java.util.List<Integer> list = new java.util.ArrayList<>();
 79             int current = 0;
 80             list.add(x); 
 81             this.nodes[list.get(current)].wasVisited = true;
 82             while(current < list.size())
 83             {
 84                 System.out.println(this.nodes[list.get(current)].data); 
 85                 
 86                 int nextSuccessor = this.getNextSuccessor(list.get(current));
 87                 while(nextSuccessor != -1)
 88                 {
 89                     list.add(nextSuccessor);
 90                     this.nodes[nextSuccessor].wasVisited = true;
 91                     nextSuccessor = this.getNextSuccessor(list.get(current));
 92                 }
 93                 current++;
 94             }
 95             
 96             this.resetNodes();
 97         }
 98         else
 99         {
100             throw new Exception("下标越界");
101         }
102     }
103     
104     /**
105      * 深度优先对图进行遍历
106      * @param x
107      * @throws Exception
108      */
109     public void showDeepFirst(int x) throws Exception
110     { 
111         if(x < this.index && x >= 0)
112         {
113             Stack<Integer> stack = new Stack<>();
114             stack.push(x);
115             System.out.println(this.nodes[x].data);
116             this.nodes[x].wasVisited = true;
117             while(!stack.isEmpty())
118             {
119                 int temp = stack.peek();
120                 int nextSuccessor = this.getNextSuccessor(temp);
121                 if(nextSuccessor == -1)
122                 {
123                     stack.pop();
124                 }
125                 else
126                 {
127                     stack.push(nextSuccessor);
128                     System.out.println(this.nodes[nextSuccessor].data);
129                     this.nodes[nextSuccessor].wasVisited = true;
130                 }
131             }
132             this.resetNodes();
133         }
134         else
135         {
136             throw new Exception("下标错误");
137         }
138         
139         
140     }
141     
142     /**
143      * 广度优先-最小生成树
144      * @param x
145      * @throws Exception
146      */
147     public void toMSTBreathFirst(int x ) throws Exception
148     {
149         if(x >= 0 && x < this.index)
150         {
151             java.util.List<Integer> list = new java.util.ArrayList();
152             int current = 0;
153             list.add(x);
154             this.nodes[list.get(current)].wasVisited = true;
155             while(current < this.index)
156             {
157                 int successor = this.getNextSuccessor(list.get(current));
158                 while(successor != -1)
159                 {
160                     list.add(successor);
161                     System.out.println(this.nodes[list.get(current)].data + "->" + this.nodes[successor].data);
162                     this.nodes[successor].wasVisited = true;
163                     successor = this.getNextSuccessor(list.get(current));
164                 }
165                 current++;
166             }
167         }
168         else
169         {
170             throw new Exception("下标错误");
171         }
172     }
173     
174     /**
175      * 深度优先求最小生成树
176      * @param x
177      * @throws Exception
178      */
179     public void toMSTDeepFirst(int x) throws Exception
180     {
181         if(x < this.index && x >=0)
182         {
183             Stack<Integer> stack = new Stack<Integer>();
184             stack.push(x);
185             this.nodes[x].wasVisited = true;
186             while(!stack.isEmpty())
187             {
188                 int current = stack.peek();
189                 int nextSuccessor = this.getNextSuccessor(current);
190                 if(nextSuccessor == -1)
191                 {
192                     stack.pop();
193                 }
194                 else
195                 {
196                     stack.push(nextSuccessor);
197                     this.nodes[nextSuccessor].wasVisited = true;
198                     System.out.print(this.nodes[current].data);
199                     System.out.print("-");
200                     System.out.print(this.nodes[nextSuccessor].data);
201                     System.out.print(" ");
202                 }
203             }
204             
205             this.resetNodes();
206         }
207         else
208         {
209             throw new Exception("下标错误");
210         }
211     }
212     
213     private int getNextSuccessor(int x)
214     { 
215         for(int i = 0; i <this.maxSize; i++)
216         {
217             if(this.adjMetrix[x][i] != 0 && this.nodes[i].wasVisited == false)
218             {
219                 return i;
220             }
221         }
222         return -1;
223     }
224     
225     private void resetNodes()
226     {
227         for(int i = 0; i < this.index; i++)
228         {
229             this.nodes[i].wasVisited = false;
230         }
231     }
232 }

Graph

秒客网

图的存储，搜索，遍历，广度优先算法和深度优先算法，最小生成树-Java实现

相关文章