学步园

一个图包括两部分信息：顶点的信息以及描述顶点之间关系的信息。

图的邻接矩阵存储也称数组表示法，其方法是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。

用邻接矩阵存储图

1. 确定图的顶点个数和边的个数

2. 输入顶点信息存储在一维数组 vertex 中

3. 初始化邻接矩阵；

4. 依次输入每条边存储在邻接矩阵 arc 中

1.  

   1. 输入边依附的两个顶点的序号 i,j;

   2. 将邻接矩阵的第 i 行第 j 列的元素值置为 1 ；

   3. 将邻接矩阵的第 j 行第 i 列的元素值置为 1 ；

由于大部分图都是稀疏图利用邻接矩阵存储开销会很大。 n 条边的用二维数组来表示的话，开销就是 n*n, 对于这种情况，对邻接矩阵做一下变化，用一个一维数组 vertex[] 来存储顶点的集合 , 再用一个一维数组来存储边的信息，数组的每一个元素都记录边的起始点，终点的相关信息，这样就能将边的存储开销降为 n 。

利用上述方法来构造，在查找的时候每次都得查找一次，则最坏的效率为 e （边数）的 n 次方，查找比较快捷的方式可以采用链表来实现。对于图的每个顶点 v ，将所有邻接于 v 的顶点链成一个单链表，所有边表的头指针和存储顶点信息的一维数组构成了顶点表，所以，在邻接表中存在两种结点结构：顶点表结构和边表结构。

利用一个一维数组来保存来保存顶点信息。给每一个顶点分配一个 vector 。 Vector 的每一个元素都保存着与顶点有关的一条边信息，这样，对于无向图来说，得到的存储效率为 n+2e, 而对于有向图来说，得到的存储效率为 n+e;再可以分配一个规则，对于无向图来说，每次记录边的时候都可以采用从顶点位置低的向顶点位置高的记录，这样能使无向图的存储效率达到 n+e 。

<!-- @page { margin: 2cm } P { margin-bottom: 0.21cm } -->

图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。

图的遍历通常有深度优先遍历与广度优先遍历两种方式，这两种遍历次序对无向图和有向图都适用。

深度优先递归方法实现：

1. 访问顶点 v; visited[v]=1;

2.w= 顶点 v 的第一个邻接点

3.while(w 存在 )

1.  

   1. if(w 未被访问 ) 从顶点 w 出发递归执行该算法

   2. w= 顶点 v 的下一个邻接点

广度优先遍历实现：

1. 初始化队列 Q

2. 访问顶点 v ； visited[v]=1; 顶点 v 入队 Q;

3.while( 队列 Q 非空 )

1.  

   1. v= 队列 Q 的队头元素出队；

   2. w= 顶点 v 的第一个邻接点

   3. while(w 存在 )

      3.3.1
      如果 w 未被访问，则访问顶点 w;visited[w]=1; 顶点 w 入队列 Q

      3.3.2 w= 顶点 v 的下一个邻接点

以下是利用vector来存储图的遍历实现：

Stack类：

Java代码  

1. package com.javaeye.rsrt;  
2.   
3. /** 
4.  * 栈，遵循先进后出的原则，用来保存元素 
5.  *  
6.  * @author nishiting 
7.  *  
8.  */  
9. public class Stack {  
10.   
11.     private int[] st;  
12.     private int top;  
13.     private int count;  
14.   
15.     /** 
16.      * 构造一个栈 
17.      *  
18.      * @param size 
19.      *            栈的大小 
20.      */  
21.     public Stack(int size) {  
22.         st = new int[size];  
23.         top = -1;  
24.         count = 0;  
25.     }  
26.   
27.     /** 
28.      * 元素进栈 
29.      *  
30.      * @param j 
31.      *            要进栈的元素 
32.      */  
33.   
34.     public void push(int j) {  
35.         count++;  
36.         st[++top] = j;  
37.     }  
38.   
39.     /** 
40.      * 元素出栈 
41.      *  
42.      * @return 出栈的元素 
43.      */  
44.   
45.     public int pop() {  
46.   
47.         return st[top--];  
48.     }  
49.   
50.     /** 
51.      * 查询栈顶元素 
52.      *  
53.      * @return 栈顶元素 
54.      */  
55.   
56.     public int peek() {  
57.         return st[top];  
58.     }  
59.   
60.     /** 
61.      * 查询栈是否为空 
62.      *  
63.      * @return 栈是否为空 
64.      */  
65.   
66.     public boolean isEmpty() {  
67.         count--;  
68.         return (top == -1);  
69.     }  
70.   
71.     /** 
72.      * 查看栈里的所有元素 
73.      */  
74.   
75.     public void list() {  
76.   
77.         for (int i = 0; i < count; i++) {  
78.   
79.             System.out.print(st[i] + "   ");  
80.   
81.         }  
82.         System.out.println();  
83.     }  
84.   
85.     /** 
86.      * 得到栈里一共有多少元素 
87.      *  
88.      * @return 栈里的元素个数 
89.      */  
90.     public int getCount() {  
91.         return count;  
92.     }  
93.   
94.     /** 
95.      * 查看栈里是否包含某个元素 
96.      *  
97.      * @param i 
98.      *            要查询的元素 
99.      * @return 是否包含了要查询的元素 
100.      */  
101.   
102.     public boolean isContains(int i) {  
103.         for (int k = 0; k < st.length; k++) {  
104.   
105.             System.out.print("开始比较" + i + "此时的result:");  
106.             list();  
107.             System.out.println();  
108.             if (st[k] == i) {  
109.                 return true;  
110.             }  
111.         }  
112.         return false;  
113.     }  
114.       
115.     /** 
116.      * 得到栈里的元素集 
117.      * @return 栈里的元素集合 
118.      */  
119.     public int[] getSt(){  
120.         return st;  
121.     }  
122.   
123. }  

Queue类：

Java代码  

1. package com.javaeye.rsrt;  
2.   
3. public class Queue {  
4.   
5.     private int[] values;  
6.     private int begin = -1;  
7.     private int end = -1;  
8.       
9.     Queue(int size){  
10.         values = new int[size];  
11.     }  
12.       
13.     void push(int value){  
14.         values[++begin] = value;  
15.     }  
16.       
17.     int pop(){  
18.         return values[++end];  
19.     }  
20.       
21.     boolean isEmpty(){  
22.         return begin == end;  
23.     }  
24. }  

 Graph类：

Java代码  

1. package com.javaeye.rsrt;  
2.   
3. import java.util.Vector;  
4.   
5. /** 
6.  *  
7.  * @author nishiting 
8.  *  
9.  */  
10.   
11. public class Graph {  
12.   
13.     int vertexNum;  
14.     Vector[] vector;  
15.     int[] visited;  
16.     Stack stack;  
17.     Stack result;  
18.     Queue queue;  
19.   
20.     /** 
21.      *  
22.      * 构造一个图 
23.      *  
24.      * @param num 
25.      *            图的顶点数 
26.      *  
27.      */  
28.     public Graph(int num) {  
29.   
30.         vertexNum = num;  
31.         vector = new Vector[vertexNum];  
32.   
33.         visited = new int[vertexNum];  
34.         for (int i = 0; i < num; i++) {  
35.             visited[i] = 0;  
36.         }  
37.         stack = new Stack(num);  
38.         result = new Stack(num);  
39.         queue = new Queue(num);  
40.   
41.     }  
42.   
43.     /** 
44.      * 向图中添加无向边 
45.      *  
46.      * @param I 
47.      *            边的一个顶点 
48.      * @param J 
49.      *            边的另一个顶点 
50.      * @return 是否添加成功 
51.      */  
52.     public boolean addEdge(int I, int J) {  
53.   
54.         /** 
55.          * 判断用户输入的是否是一个顶点，如果是，则返回flase,添加不成功 
56.          */  
57.         if (J == I) {  
58.             return false;  
59.         }  
60.   
61.         /** 
62.          * 判断所输入的顶点值是否在图所顶点范围值内，如果不在，则提示顶点不存在 
63.          *  
64.          */  
65.         if (I < vertexNum && J < vertexNum && I >= 0 && J >= 0) {  
66.   
67.             int k;  
68.               
69.             /** 
70.              * 如果i比j大，则将i与j交换 
71.              */  
72.   
73.             if (I > J) {  
74.                 k = I;  
75.                 I = J;  
76.                 J = k;  
77.             }  
78.   
79.             /** 
80.              *  
81.              * 判断边是否存在 
82.              */  
83.   
84.             if (isEdgeExists(I, J)) {  
85.   
86.                 return false;  
87.             }  
88.               
89.             /** 
90.              * 添加边 
91.              */  
92.   
93.             vector[I].add(J);  
94.             return true;  
95.         }  
96.         return false;  
97.     }  
98.   
99.     /** 
100.      * 判断无向边是否存在 
101.      *  
102.      * @param i 
103.      *            要查询的无向边的一个顶点 
104.      * @param j 
105.      *            要查询的无向边的另一个顶点 
106.      * @return 边是否存在，false:不存在，true:存在 
107.      */  
108.   
109.     public boolean isEdgeExists(int i, int j) {  
110.   
111.         /** 
112.          * 判断所输入的顶点值是否在图所顶点范围值内，如果不在，则提示顶点不存在 
113.          *  
114.          */  
115.         if (i < vertexNum && j < vertexNum && i >= 0 && j >= 0) {  
116.   
117.             if (i == j) {  
118.                 return false;  
119.             }  
120.   
121.             int k;  
122.   
123.             /** 
124.              * 如果i比j大的话，i与j进行交换 
125.              */  
126.   
127.             if (i > j) {  
128.                 k = i;  
129.                 i = j;  
130.                 j = k;  
131.             }  
132.   
133.             /** 
134.              * 判断i的邻接结点集是否为空 
135.              */  
136.   
137.             if (vector[i] == null) {  
138.                 vector[i] = new Vector(8);  
139.             }  
140.   
141.             /** 
142.              * 判断这条边是否存在，如果存在，则提示边已经存在 
143.              */  
144.             for (int q = 0; q < vector[i].size(); q++) {  
145.   
146.                 if (((Integer) vector[i].get(q)).intValue() == j) {  
147.                     System.out.println("顶点" + i + "和" + "顶点" + j + "这两点之间存在边");  
148.                     return true;  
149.   
150.                 }  
151.             }  
152.         }  
153.         return false;  
154.     }  
155.   
156.     /** 
157.      * 进行深度优先遍历 
158.      */  
159.     public void dfs() {  
160.           
161.         /** 
162.          * 从顶点0开始遍历 
163.          */  
164.   
165.         visited[0] = 1;  
166.         stack.push(0);  
167.           
168.         /** 
169.          * 如果栈不为空的话，进行循环查询 
170.          */  
171.   
172.         while (!stack.isEmpty()) {  
173.   
174.             int v = getAdjUnvisitedVertex(stack.peek());  
175.               
176.             /** 
177.              * 没找到未被访问的邻接点，元素出栈，如果找到的话，将这个结点标记为访问过，将其未被访问的邻接点入栈 
178.              */  
179.   
180.             if (v == -1) {  
181.                 result.push(stack.peek());  
182.                 stack.pop();  
183.   
184.             } else {  
185.                 visited[v] = 1;  
186.                 stack.push(v);  
187.   
188.             }  
189.         }  
190.   
191.         System.out.println("进行深度优先的遍历顺序为：");  
192.         result.list();  
193.   
194.     }  
195.       
196.     /** 
197.      * 进行广度优先遍历 
198.      */  
199.       
200.     public void bsf(){  
201.           
202.         /** 
203.          * 从顶点0开始遍历 
204.          */  
205.         visited[0] = 1;  
206.         queue.push(0);  
207.           
208.         while(!queue.isEmpty()){  
209.             int v = queue.pop();  
210.             result.push(v);  
211.             int i;  
212.             while((i = getAdjUnvisitedVertex(v))!=-1){  
213.                 visited[i]=1;  
214.                 queue.push(i);  
215.             }  
216.               
217.         }  
218.         System.out.println("广度优先的遍历顺序为：");  
219.         result.list();  
220.           
221.     }  
222.   
223.     /** 
224.      * 得到指定结点的一个未被访问的邻接点位置 
225.      *  
226.      * @param v 
227.      *            要查询的顶点 
228.      * @return 顶点的下一个未被访问的邻接结点 
229.      */  
230.   
231.     public int getAdjUnvisitedVertex(int v) {  
232.         int temp;  
233.   
234.         /** 
235.          * 判断邻接结点是否为空 
236.          */  
237.   
238.         if (vector[v] != null) {  
239.   
240.             /** 
241.              * 遍历所有的邻接结点 
242.              */  
243.             for (int j = 0; j < vector[v].size(); j++) {  
244.                 temp = ((Integer) vector[v].get(j )).intValue();  
245.                 /** 
246.                  * 判断邻接结点是否被访问过 
247.                  */  
248.                 if (visited[temp] == 0)  
249.                     return ((Integer) vector[v].get(j)).intValue();  
250.   
251.             }  
252.   
253.         }  
254.   
255.         return -1;  
256.     }  
257.       
258.       
259.   
260.     /** 
261.      * 得到图的遍历顺序 
262.      *  
263.      * @return 图的遍历顺序 
264.      */  
265.   
266.     public Stack getResult() {  
267.         return result;  
268.     }  
269.   
270. }  

 测试类：

Java代码  

1. package com.javaeye.rsrt;  
2.   
3. import junit.framework.TestCase;  
4.   
5. public class GraphTest extends TestCase {  
6.   
7.     public void testAddEdge(){  
8.           
9. //      Graph graph = new Graph(10);  
10. //        
11. //      /**  
12. //       * 测试向两个相同的顶点添加边  
13. //       */  
14. //      assertEquals(false,graph.addEdge(1, 1));  
15. //      assertEquals(false,graph.isEdgeExists(1, 1));  
16. //        
17. //      /**  
18. //       * 测试向不存在的点添加边  
19. //       */  
20. //      assertEquals(false,graph.addEdge(-1, 1));  
21. //      assertEquals(false,graph.isEdgeExists(-1, 1));  
22. //      assertEquals(false,graph.addEdge(1, 15));  
23. //      assertEquals(false,graph.isEdgeExists(1, 15));  
24. //      assertEquals(false,graph.addEdge(-1, 15));  
25. //      assertEquals(false,graph.isEdgeExists(-1, 15));  
26. //        
27. //      /**  
28. //       * 测试向两个合理的点添加边  
29. //       */  
30. //      assertEquals(true,graph.addEdge(1,6));  
31. //      assertEquals(true,graph.isEdgeExists(1, 6));  
32. //        
33. //      /**  
34. //       * 测试向已有班的顶点添加  
35. //       */  
36. //      assertEquals(true,graph.isEdgeExists(1, 6));  
37. //      assertEquals(false,graph.addEdge(1,6));  
38. //      /**  
39. //       * 测试向边缘的点添加边  
40. //       *   
41. //       */  
42. //      assertEquals(true,graph.addEdge(0, 9));  
43. //      assertEquals(true,graph.isEdgeExists(0, 9));  
44. //        
45. //      /**  
46. //       * 测试无向图由位置大的点向位置小的点添加  
47. //       */  
48. //      assertEquals(true,graph.addEdge(8, 4));  
49. //      assertEquals(true,graph.isEdgeExists(8, 4));  
50.           
51.           
52.         /** 
53.          * 测试一个简单的连通图 
54.          */  
55.           
56.         Graph graph = new Graph(6);  
57.         graph.addEdge(0, 1);  
58.         graph.addEdge(0, 5);  
59.         graph.addEdge(0, 2);  
60.         graph.addEdge(1, 2);  
61.         graph.addEdge(2, 3);  
62.         graph.addEdge(1, 4);  
63.         graph.addEdge(2, 4);  
64.           
65.         graph.bsf();  
66.           
67. //      graph.dfs();  
68. //      int[] values = {3,4,2,1,5,0};  
69. //      int[] result = graph.getResult().getSt();  
70. //      for(int i = 0;i < values.length;i++){  
71. //          assertEquals(values[i],result[i]);  
72. //      }  
73.           
74.         /** 
75.          * 测试一个非连通图 
76.          *  
77.          */  
78. //      graph = new Graph(6);  
79. //  
80. //      graph.addEdge(0, 1);  
81. //      graph.addEdge(0, 5);  
82. //      graph.addEdge(0, 2);  
83. //      graph.addEdge(1, 2);  
84. //      graph.addEdge(1, 4);  
85. //      graph.addEdge(2, 4);  
86. //        
87. //      graph.dfs();  
88. //        
89. //      values = new int[] {4,2,1,5,0};  
90. //      result = graph.getResult().getSt();  
91. //      for(int i = 0;i < values.length;i++){  
92. //          assertEquals(values[i],result[i]);  
93. //      }  
94.     }  
95. }