ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【图 - 遍历(BFS & DFS)】深度优先搜索算法(Depth First Search)， 广度优 [打印本页]

---

作者: 钜形不锈钢水箱    时间: 2024-6-14 21:43
标题: 【图 - 遍历(BFS & DFS)】深度优先搜索算法(Depth First Search)， 广度优


   图的深度优先搜索(Depth First Search)，和树的先序遍历比力类似; 广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"。 
  

• 深度优先搜索
  
  
  
  • 深度优先搜索介绍
    
  • 深度优先搜索图解
    
  • 有向图的深度优先搜索
    
  
  
• 广度优先搜索
  
  
  
  • 广度优先搜索介绍
    
  • 广度优先搜索图解
    
  
  
• 相关实现
  
  
  
  • 邻接矩阵实现无向图
    
  • 邻接表实现的无向图
    
  • 邻接矩阵实现的有向图
    
  • 邻接表实现的有向图
    
  
  

# 深度优先搜索

# 深度优先搜索介绍

它的思想: 假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
显然，深度优先搜索是一个递归的过程。
# 深度优先搜索图解

# 无向图的深度优先搜索

下面以"无向图"为例，来对深度优先搜索进行演示。

对上面的图G1进行深度优先遍历，从顶点A开始。

第1步: 访问A。
第2步: 访问(A的邻接点)C。 在第1步访问A之后，接下来应该访问的是A的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在"D和F"的前面，因此，先访问C。
第3步: 访问(C的邻接点)B。 在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。
第4步: 访问(C的邻接点)D。 在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。
第5步: 访问(A的邻接点)F。 前面已经访问了A，而且访问完了"A的邻接点B的所有邻接点(包罗递归的邻接点在内)"；因此，此时返回到访问A的另一个邻接点F。
第6步: 访问(F的邻接点)G。
第7步: 访问(G的邻接点)E。
因此访问顺序是: A -> C -> B -> D -> F -> G -> E
# 有向图的深度优先搜索

下面以"有向图"为例，来对深度优先搜索进行演示。

对上面的图G2进行深度优先遍历，从顶点A开始。

第1步: 访问A。
第2步: 访问B。 在访问了A之后，接下来应该访问的是A的出边的另一个顶点，即顶点B。
第3步: 访问C。 在访问了B之后，接下来应该访问的是B的出边的另一个顶点，即顶点C,E,F。在本文实现的图中，顶点ABCDEFG按照顺序存储，因此先访问C。
第4步: 访问E。 接下来访问C的出边的另一个顶点，即顶点E。
第5步: 访问D。 接下来访问E的出边的另一个顶点，即顶点B,D。顶点B已经被访问过，因此访问顶点D。
第6步: 访问F。 接下应该回溯"访问A的出边的另一个顶点F"。
第7步: 访问G。
因此访问顺序是: A -> B -> C -> E -> D -> F -> G
# 广度优先搜索

# 广度优先搜索介绍

广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。
它的思想是: 从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则必要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2...的顶点。
# 广度优先搜索图解

# 无向图的广度优先搜索

下面以"无向图"为例，来对广度优先搜索进行演示。照旧以上面的图G1为例进行说明。

第1步: 访问A。
第2步: 依次访问C,D,F。 在访问了A之后，接下来访问A的邻接点。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，C在"D和F"的前面，因此，先访问C。再访问完C之后，再依次访问D,F。
第3步: 依次访问B,G。 在第2步访问完C,D,F之后，再依次访问它们的邻接点。首先访问C的邻接点B，再访问F的邻接点G。
第4步: 访问E。 在第3步访问完B,G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。
因此访问顺序是: A -> C -> D -> F -> B -> G -> E
# 有向图的广度优先搜索

下面以"有向图"为例，来对广度优先搜索进行演示。照旧以上面的图G2为例进行说明。

第1步: 访问A。
第2步: 访问B。
第3步: 依次访问C,E,F。 在访问了B之后，接下来访问B的出边的另一个顶点，即C,E,F。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，因此会先访问C，再依次访问E,F。
第4步: 依次访问D,G。 在访问完C,E,F之后，再依次访问它们的出边的另一个顶点。照旧按照C,E,F的顺序访问，C的已经全部访问过了，那么就只剩下E,F；先访问E的邻接点D，再访问F的邻接点G。
因此访问顺序是: A -> B -> C -> E -> F -> D -> G
# 相关实现

# 邻接矩阵实现无向图

1. import java.io.IOException;
2. import java.util.Scanner;
4. public class MatrixUDG {
6.     private char[] mVexs;       // 顶点集合
7.     private int[][] mMatrix;    // 邻接矩阵
9.     /*
10.      * 创建图(自己输入数据)
11.      */
12.     public MatrixUDG() {
14.         // 输入"顶点数"和"边数"
15.         System.out.printf("input vertex number: ");
16.         int vlen = readInt();
17.         System.out.printf("input edge number: ");
18.         int elen = readInt();
19.         if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
20.             System.out.printf("input error: invalid parameters!\n");
21.             return ;
22.         }
23.         
24.         // 初始化"顶点"
25.         mVexs = new char[vlen];
26.         for (int i = 0; i < mVexs.length; i++) {
27.             System.out.printf("vertex(%d): ", i);
28.             mVexs[i] = readChar();
29.         }
31.         // 初始化"边"
32.         mMatrix = new int[vlen][vlen];
33.         for (int i = 0; i < elen; i++) {
34.             // 读取边的起始顶点和结束顶点
35.             System.out.printf("edge(%d):", i);
36.             char c1 = readChar();
37.             char c2 = readChar();
38.             int p1 = getPosition(c1);
39.             int p2 = getPosition(c2);
41.             if (p1==-1 || p2==-1) {
42.                 System.out.printf("input error: invalid edge!\n");
43.                 return ;
44.             }
46.             mMatrix[p1][p2] = 1;
47.             mMatrix[p2][p1] = 1;
48.         }
49.     }
51.     /*
52.      * 创建图(用已提供的矩阵)
53.      *
54.      * 参数说明：
55.      *     vexs  -- 顶点数组
56.      *     edges -- 边数组
57.      */
58.     public MatrixUDG(char[] vexs, char[][] edges) {
59.         
60.         // 初始化"顶点数"和"边数"
61.         int vlen = vexs.length;
62.         int elen = edges.length;
64.         // 初始化"顶点"
65.         mVexs = new char[vlen];
66.         for (int i = 0; i < mVexs.length; i++)
67.             mVexs[i] = vexs[i];
69.         // 初始化"边"
70.         mMatrix = new int[vlen][vlen];
71.         for (int i = 0; i < elen; i++) {
72.             // 读取边的起始顶点和结束顶点
73.             int p1 = getPosition(edges[i][0]);
74.             int p2 = getPosition(edges[i][1]);
76.             mMatrix[p1][p2] = 1;
77.             mMatrix[p2][p1] = 1;
78.         }
79.     }
81.     /*
82.      * 返回ch位置
83.      */
84.     private int getPosition(char ch) {
85.         for(int i=0; i<mVexs.length; i++)
86.             if(mVexs[i]==ch)
87.                 return i;
88.         return -1;
89.     }
91.     /*
92.      * 读取一个输入字符
93.      */
94.     private char readChar() {
95.         char ch='0';
97.         do {
98.             try {
99.                 ch = (char)System.in.read();
100.             } catch (IOException e) {
101.                 e.printStackTrace();
102.             }
103.         } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
105.         return ch;
106.     }
108.     /*
109.      * 读取一个输入字符
110.      */
111.     private int readInt() {
112.         Scanner scanner = new Scanner(System.in);
113.         return scanner.nextInt();
114.     }
116.     /*
117.      * 返回顶点v的第一个邻接顶点的索引，失败则返回-1
118.      */
119.     private int firstVertex(int v) {
121.         if (v<0 || v>(mVexs.length-1))
122.             return -1;
124.         for (int i = 0; i < mVexs.length; i++)
125.             if (mMatrix[v][i] == 1)
126.                 return i;
128.         return -1;
129.     }
131.     /*
132.      * 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
133.      */
134.     private int nextVertex(int v, int w) {
136.         if (v<0 || v>(mVexs.length-1) || w<0 || w>(mVexs.length-1))
137.             return -1;
139.         for (int i = w + 1; i < mVexs.length; i++)
140.             if (mMatrix[v][i] == 1)
141.                 return i;
143.         return -1;
144.     }
146.     /*
147.      * 深度优先搜索遍历图的递归实现
148.      */
149.     private void DFS(int i, boolean[] visited) {
151.         visited[i] = true;
152.         System.out.printf("%c ", mVexs[i]);
153.         // 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
154.         for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
155.             if (!visited[w])
156.                 DFS(w, visited);
157.         }
158.     }
160.     /*
161.      * 深度优先搜索遍历图
162.      */
163.     public void DFS() {
164.         boolean[] visited = new boolean[mVexs.length];       // 顶点访问标记
166.         // 初始化所有顶点都没有被访问
167.         for (int i = 0; i < mVexs.length; i++)
168.             visited[i] = false;
170.         System.out.printf("DFS: ");
171.         for (int i = 0; i < mVexs.length; i++) {
172.             if (!visited[i])
173.                 DFS(i, visited);
174.         }
175.         System.out.printf("\n");
176.     }
178.     /*
179.      * 广度优先搜索（类似于树的层次遍历）
180.      */
181.     public void BFS() {
182.         int head = 0;
183.         int rear = 0;
184.         int[] queue = new int[mVexs.length];            // 辅组队列
185.         boolean[] visited = new boolean[mVexs.length];  // 顶点访问标记
187.         for (int i = 0; i < mVexs.length; i++)
188.             visited[i] = false;
190.         System.out.printf("BFS: ");
191.         for (int i = 0; i < mVexs.length; i++) {
192.             if (!visited[i]) {
193.                 visited[i] = true;
194.                 System.out.printf("%c ", mVexs[i]);
195.                 queue[rear++] = i;  // 入队列
196.             }
198.             while (head != rear) {
199.                 int j = queue[head++];  // 出队列
200.                 for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) { //k是为访问的邻接顶点
201.                     if (!visited[k]) {
202.                         visited[k] = true;
203.                         System.out.printf("%c ", mVexs[k]);
204.                         queue[rear++] = k;
205.                     }
206.                 }
207.             }
208.         }
209.         System.out.printf("\n");
210.     }
212.     /*
213.      * 打印矩阵队列图
214.      */
215.     public void print() {
216.         System.out.printf("Martix Graph:\n");
217.         for (int i = 0; i < mVexs.length; i++) {
218.             for (int j = 0; j < mVexs.length; j++)
219.                 System.out.printf("%d ", mMatrix[i][j]);
220.             System.out.printf("\n");
221.         }
222.     }
224.     public static void main(String[] args) {
225.         char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
226.         char[][] edges = new char[][]{
227.             {'A', 'C'},
228.             {'A', 'D'},
229.             {'A', 'F'},
230.             {'B', 'C'},
231.             {'C', 'D'},
232.             {'E', 'G'},
233.             {'F', 'G'}};
234.         MatrixUDG pG;
236.         // 自定义"图"(输入矩阵队列)
237.         //pG = new MatrixUDG();
238.         // 采用已有的"图"
239.         pG = new MatrixUDG(vexs, edges);
241.         pG.print();   // 打印图
242.         pG.DFS();     // 深度优先遍历
243.         pG.BFS();     // 广度优先遍历
244.     }
245. }

复制代码

# 邻接表实现的无向图

1. import java.io.IOException;
2. import java.util.Scanner;
4. public class ListUDG {
5.     // 邻接表中表对应的链表的顶点
6.     private class ENode {
7.         int ivex;       // 该边所指向的顶点的位置
8.         ENode nextEdge; // 指向下一条弧的指针
9.     }
11.     // 邻接表中表的顶点
12.     private class VNode {
13.         char data;          // 顶点信息
14.         ENode firstEdge;    // 指向第一条依附该顶点的弧
15.     };
17.     private VNode[] mVexs;  // 顶点数组
20.     /*
21.      * 创建图(自己输入数据)
22.      */
23.     public ListUDG() {
25.         // 输入"顶点数"和"边数"
26.         System.out.printf("input vertex number: ");
27.         int vlen = readInt();
28.         System.out.printf("input edge number: ");
29.         int elen = readInt();
30.         if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
31.             System.out.printf("input error: invalid parameters!\n");
32.             return ;
33.         }
34.         
35.         // 初始化"顶点"
36.         mVexs = new VNode[vlen];
37.         for (int i = 0; i < mVexs.length; i++) {
38.             System.out.printf("vertex(%d): ", i);
39.             mVexs[i] = new VNode();
40.             mVexs[i].data = readChar();
41.             mVexs[i].firstEdge = null;
42.         }
44.         // 初始化"边"
45.         //mMatrix = new int[vlen][vlen];
46.         for (int i = 0; i < elen; i++) {
47.             // 读取边的起始顶点和结束顶点
48.             System.out.printf("edge(%d):", i);
49.             char c1 = readChar();
50.             char c2 = readChar();
51.             int p1 = getPosition(c1);
52.             int p2 = getPosition(c2);
53.             // 初始化node1
54.             ENode node1 = new ENode();
55.             node1.ivex = p2;
56.             // 将node1链接到"p1所在链表的末尾"
57.             if(mVexs[p1].firstEdge == null)
58.               mVexs[p1].firstEdge = node1;
59.             else
60.                 linkLast(mVexs[p1].firstEdge, node1);
61.             // 初始化node2
62.             ENode node2 = new ENode();
63.             node2.ivex = p1;
64.             // 将node2链接到"p2所在链表的末尾"
65.             if(mVexs[p2].firstEdge == null)
66.               mVexs[p2].firstEdge = node2;
67.             else
68.                 linkLast(mVexs[p2].firstEdge, node2);
69.         }
70.     }
72.     /*
73.      * 创建图(用已提供的矩阵)
74.      *
75.      * 参数说明：
76.      *     vexs  -- 顶点数组
77.      *     edges -- 边数组
78.      */
79.     public ListUDG(char[] vexs, char[][] edges) {
80.         
81.         // 初始化"顶点数"和"边数"
82.         int vlen = vexs.length;
83.         int elen = edges.length;
85.         // 初始化"顶点"
86.         mVexs = new VNode[vlen];
87.         for (int i = 0; i < mVexs.length; i++) {
88.             mVexs[i] = new VNode();
89.             mVexs[i].data = vexs[i];
90.             mVexs[i].firstEdge = null;
91.         }
93.         // 初始化"边"
94.         for (int i = 0; i < elen; i++) {
95.             // 读取边的起始顶点和结束顶点
96.             char c1 = edges[i][0];
97.             char c2 = edges[i][1];
98.             // 读取边的起始顶点和结束顶点
99.             int p1 = getPosition(edges[i][0]);
100.             int p2 = getPosition(edges[i][1]);
102.             // 初始化node1
103.             ENode node1 = new ENode();
104.             node1.ivex = p2;
105.             // 将node1链接到"p1所在链表的末尾"
106.             if(mVexs[p1].firstEdge == null)
107.               mVexs[p1].firstEdge = node1;
108.             else
109.                 linkLast(mVexs[p1].firstEdge, node1);
110.             // 初始化node2
111.             ENode node2 = new ENode();
112.             node2.ivex = p1;
113.             // 将node2链接到"p2所在链表的末尾"
114.             if(mVexs[p2].firstEdge == null)
115.               mVexs[p2].firstEdge = node2;
116.             else
117.                 linkLast(mVexs[p2].firstEdge, node2);
118.         }
119.     }
121.     /*
122.      * 将node节点链接到list的最后
123.      */
124.     private void linkLast(ENode list, ENode node) {
125.         ENode p = list;
127.         while(p.nextEdge!=null)
128.             p = p.nextEdge;
129.         p.nextEdge = node;
130.     }
132.     /*
133.      * 返回ch位置
134.      */
135.     private int getPosition(char ch) {
136.         for(int i=0; i<mVexs.length; i++)
137.             if(mVexs[i].data==ch)
138.                 return i;
139.         return -1;
140.     }
142.     /*
143.      * 读取一个输入字符
144.      */
145.     private char readChar() {
146.         char ch='0';
148.         do {
149.             try {
150.                 ch = (char)System.in.read();
151.             } catch (IOException e) {
152.                 e.printStackTrace();
153.             }
154.         } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
156.         return ch;
157.     }
159.     /*
160.      * 读取一个输入字符
161.      */
162.     private int readInt() {
163.         Scanner scanner = new Scanner(System.in);
164.         return scanner.nextInt();
165.     }
167.     /*
168.      * 深度优先搜索遍历图的递归实现
169.      */
170.     private void DFS(int i, boolean[] visited) {
171.         ENode node;
173.         visited[i] = true;
174.         System.out.printf("%c ", mVexs[i].data);
175.         node = mVexs[i].firstEdge;
176.         while (node != null) {
177.             if (!visited[node.ivex])
178.                 DFS(node.ivex, visited);
179.             node = node.nextEdge;
180.         }
181.     }
183.     /*
184.      * 深度优先搜索遍历图
185.      */
186.     public void DFS() {
187.         boolean[] visited = new boolean[mVexs.length];       // 顶点访问标记
189.         // 初始化所有顶点都没有被访问
190.         for (int i = 0; i < mVexs.length; i++)
191.             visited[i] = false;
193.         System.out.printf("DFS: ");
194.         for (int i = 0; i < mVexs.length; i++) {
195.             if (!visited[i])
196.                 DFS(i, visited);
197.         }
198.         System.out.printf("\n");
199.     }
201.     /*
202.      * 广度优先搜索（类似于树的层次遍历）
203.      */
204.     public void BFS() {
205.         int head = 0;
206.         int rear = 0;
207.         int[] queue = new int[mVexs.length];            // 辅组队列
208.         boolean[] visited = new boolean[mVexs.length];  // 顶点访问标记
210.         for (int i = 0; i < mVexs.length; i++)
211.             visited[i] = false;
213.         System.out.printf("BFS: ");
214.         for (int i = 0; i < mVexs.length; i++) {
215.             if (!visited[i]) {
216.                 visited[i] = true;
217.                 System.out.printf("%c ", mVexs[i].data);
218.                 queue[rear++] = i;  // 入队列
219.             }
221.             while (head != rear) {
222.                 int j = queue[head++];  // 出队列
223.                 ENode node = mVexs[j].firstEdge;
224.                 while (node != null) {
225.                     int k = node.ivex;
226.                     if (!visited[k])
227.                     {
228.                         visited[k] = true;
229.                         System.out.printf("%c ", mVexs[k].data);
230.                         queue[rear++] = k;
231.                     }
232.                     node = node.nextEdge;
233.                 }
234.             }
235.         }
236.         System.out.printf("\n");
237.     }
239.     /*
240.      * 打印矩阵队列图
241.      */
242.     public void print() {
243.         System.out.printf("List Graph:\n");
244.         for (int i = 0; i < mVexs.length; i++) {
245.             System.out.printf("%d(%c): ", i, mVexs[i].data);
246.             ENode node = mVexs[i].firstEdge;
247.             while (node != null) {
248.                 System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
249.                 node = node.nextEdge;
250.             }
251.             System.out.printf("\n");
252.         }
253.     }
255.     public static void main(String[] args) {
256.         char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
257.         char[][] edges = new char[][]{
258.             {'A', 'C'},
259.             {'A', 'D'},
260.             {'A', 'F'},
261.             {'B', 'C'},
262.             {'C', 'D'},
263.             {'E', 'G'},
264.             {'F', 'G'}};
265.         ListUDG pG;
267.         // 自定义"图"(输入矩阵队列)
268.         //pG = new ListUDG();
269.         // 采用已有的"图"
270.         pG = new ListUDG(vexs, edges);
272.         pG.print();   // 打印图
273.         pG.DFS();     // 深度优先遍历
274.         pG.BFS();     // 广度优先遍历
275.     }
276. }

复制代码

# 邻接矩阵实现的有向图

1. import java.io.IOException;
2. import java.util.Scanner;
4. public class MatrixDG {
6.     private char[] mVexs;       // 顶点集合
7.     private int[][] mMatrix;    // 邻接矩阵
9.     /*
10.      * 创建图(自己输入数据)
11.      */
12.     public MatrixDG() {
14.         // 输入"顶点数"和"边数"
15.         System.out.printf("input vertex number: ");
16.         int vlen = readInt();
17.         System.out.printf("input edge number: ");
18.         int elen = readInt();
19.         if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
20.             System.out.printf("input error: invalid parameters!\n");
21.             return ;
22.         }
23.         
24.         // 初始化"顶点"
25.         mVexs = new char[vlen];
26.         for (int i = 0; i < mVexs.length; i++) {
27.             System.out.printf("vertex(%d): ", i);
28.             mVexs[i] = readChar();
29.         }
31.         // 初始化"边"
32.         mMatrix = new int[vlen][vlen];
33.         for (int i = 0; i < elen; i++) {
34.             // 读取边的起始顶点和结束顶点
35.             System.out.printf("edge(%d):", i);
36.             char c1 = readChar();
37.             char c2 = readChar();
38.             int p1 = getPosition(c1);
39.             int p2 = getPosition(c2);
41.             if (p1==-1 || p2==-1) {
42.                 System.out.printf("input error: invalid edge!\n");
43.                 return ;
44.             }
46.             mMatrix[p1][p2] = 1;
47.         }
48.     }
50.     /*
51.      * 创建图(用已提供的矩阵)
52.      *
53.      * 参数说明：
54.      *     vexs  -- 顶点数组
55.      *     edges -- 边数组
56.      */
57.     public MatrixDG(char[] vexs, char[][] edges) {
58.         
59.         // 初始化"顶点数"和"边数"
60.         int vlen = vexs.length;
61.         int elen = edges.length;
63.         // 初始化"顶点"
64.         mVexs = new char[vlen];
65.         for (int i = 0; i < mVexs.length; i++)
66.             mVexs[i] = vexs[i];
68.         // 初始化"边"
69.         mMatrix = new int[vlen][vlen];
70.         for (int i = 0; i < elen; i++) {
71.             // 读取边的起始顶点和结束顶点
72.             int p1 = getPosition(edges[i][0]);
73.             int p2 = getPosition(edges[i][1]);
75.             mMatrix[p1][p2] = 1;
76.         }
77.     }
79.     /*
80.      * 返回ch位置
81.      */
82.     private int getPosition(char ch) {
83.         for(int i=0; i<mVexs.length; i++)
84.             if(mVexs[i]==ch)
85.                 return i;
86.         return -1;
87.     }
89.     /*
90.      * 读取一个输入字符
91.      */
92.     private char readChar() {
93.         char ch='0';
95.         do {
96.             try {
97.                 ch = (char)System.in.read();
98.             } catch (IOException e) {
99.                 e.printStackTrace();
100.             }
101.         } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
103.         return ch;
104.     }
106.     /*
107.      * 读取一个输入字符
108.      */
109.     private int readInt() {
110.         Scanner scanner = new Scanner(System.in);
111.         return scanner.nextInt();
112.     }
114.     /*
115.      * 返回顶点v的第一个邻接顶点的索引，失败则返回-1
116.      */
117.     private int firstVertex(int v) {
119.         if (v<0 || v>(mVexs.length-1))
120.             return -1;
122.         for (int i = 0; i < mVexs.length; i++)
123.             if (mMatrix[v][i] == 1)
124.                 return i;
126.         return -1;
127.     }
129.     /*
130.      * 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
131.      */
132.     private int nextVertex(int v, int w) {
134.         if (v<0 || v>(mVexs.length-1) || w<0 || w>(mVexs.length-1))
135.             return -1;
137.         for (int i = w + 1; i < mVexs.length; i++)
138.             if (mMatrix[v][i] == 1)
139.                 return i;
141.         return -1;
142.     }
144.     /*
145.      * 深度优先搜索遍历图的递归实现
146.      */
147.     private void DFS(int i, boolean[] visited) {
149.         visited[i] = true;
150.         System.out.printf("%c ", mVexs[i]);
151.         // 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
152.         for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
153.             if (!visited[w])
154.                 DFS(w, visited);
155.         }
156.     }
158.     /*
159.      * 深度优先搜索遍历图
160.      */
161.     public void DFS() {
162.         boolean[] visited = new boolean[mVexs.length];       // 顶点访问标记
164.         // 初始化所有顶点都没有被访问
165.         for (int i = 0; i < mVexs.length; i++)
166.             visited[i] = false;
168.         System.out.printf("DFS: ");
169.         for (int i = 0; i < mVexs.length; i++) {
170.             if (!visited[i])
171.                 DFS(i, visited);
172.         }
173.         System.out.printf("\n");
174.     }
176.     /*
177.      * 广度优先搜索（类似于树的层次遍历）
178.      */
179.     public void BFS() {
180.         int head = 0;
181.         int rear = 0;
182.         int[] queue = new int[mVexs.length];            // 辅组队列
183.         boolean[] visited = new boolean[mVexs.length];  // 顶点访问标记
185.         for (int i = 0; i < mVexs.length; i++)
186.             visited[i] = false;
188.         System.out.printf("BFS: ");
189.         for (int i = 0; i < mVexs.length; i++) {
190.             if (!visited[i]) {
191.                 visited[i] = true;
192.                 System.out.printf("%c ", mVexs[i]);
193.                 queue[rear++] = i;  // 入队列
194.             }
196.             while (head != rear) {
197.                 int j = queue[head++];  // 出队列
198.                 for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) { //k是为访问的邻接顶点
199.                     if (!visited[k]) {
200.                         visited[k] = true;
201.                         System.out.printf("%c ", mVexs[k]);
202.                         queue[rear++] = k;
203.                     }
204.                 }
205.             }
206.         }
207.         System.out.printf("\n");
208.     }
210.     /*
211.      * 打印矩阵队列图
212.      */
213.     public void print() {
214.         System.out.printf("Martix Graph:\n");
215.         for (int i = 0; i < mVexs.length; i++) {
216.             for (int j = 0; j < mVexs.length; j++)
217.                 System.out.printf("%d ", mMatrix[i][j]);
218.             System.out.printf("\n");
219.         }
220.     }
222.     public static void main(String[] args) {
223.         char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
224.         char[][] edges = new char[][]{
225.             {'A', 'B'},
226.             {'B', 'C'},
227.             {'B', 'E'},
228.             {'B', 'F'},
229.             {'C', 'E'},
230.             {'D', 'C'},
231.             {'E', 'B'},
232.             {'E', 'D'},
233.             {'F', 'G'}};
234.         MatrixDG pG;
236.         // 自定义"图"(输入矩阵队列)
237.         //pG = new MatrixDG();
238.         // 采用已有的"图"
239.         pG = new MatrixDG(vexs, edges);
241.         pG.print();   // 打印图
242.         pG.DFS();     // 深度优先遍历
243.         pG.BFS();     // 广度优先遍历
244.     }
245. }

复制代码

# 邻接表实现的有向图

1. import java.io.IOException;
2. import java.util.Scanner;
4. public class ListDG {
5.     // 邻接表中表对应的链表的顶点
6.     private class ENode {
7.         int ivex;       // 该边所指向的顶点的位置
8.         ENode nextEdge; // 指向下一条弧的指针
9.     }
11.     // 邻接表中表的顶点
12.     private class VNode {
13.         char data;          // 顶点信息
14.         ENode firstEdge;    // 指向第一条依附该顶点的弧
15.     };
17.     private VNode[] mVexs;  // 顶点数组
20.     /*
21.      * 创建图(自己输入数据)
22.      */
23.     public ListDG() {
25.         // 输入"顶点数"和"边数"
26.         System.out.printf("input vertex number: ");
27.         int vlen = readInt();
28.         System.out.printf("input edge number: ");
29.         int elen = readInt();
30.         if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
31.             System.out.printf("input error: invalid parameters!\n");
32.             return ;
33.         }
34.         
35.         // 初始化"顶点"
36.         mVexs = new VNode[vlen];
37.         for (int i = 0; i < mVexs.length; i++) {
38.             System.out.printf("vertex(%d): ", i);
39.             mVexs[i] = new VNode();
40.             mVexs[i].data = readChar();
41.             mVexs[i].firstEdge = null;
42.         }
44.         // 初始化"边"
45.         //mMatrix = new int[vlen][vlen];
46.         for (int i = 0; i < elen; i++) {
47.             // 读取边的起始顶点和结束顶点
48.             System.out.printf("edge(%d):", i);
49.             char c1 = readChar();
50.             char c2 = readChar();
51.             int p1 = getPosition(c1);
52.             int p2 = getPosition(c2);
53.             // 初始化node1
54.             ENode node1 = new ENode();
55.             node1.ivex = p2;
56.             // 将node1链接到"p1所在链表的末尾"
57.             if(mVexs[p1].firstEdge == null)
58.               mVexs[p1].firstEdge = node1;
59.             else
60.                 linkLast(mVexs[p1].firstEdge, node1);
61.         }
62.     }
64.     /*
65.      * 创建图(用已提供的矩阵)
66.      *
67.      * 参数说明：
68.      *     vexs  -- 顶点数组
69.      *     edges -- 边数组
70.      */
71.     public ListDG(char[] vexs, char[][] edges) {
72.         
73.         // 初始化"顶点数"和"边数"
74.         int vlen = vexs.length;
75.         int elen = edges.length;
77.         // 初始化"顶点"
78.         mVexs = new VNode[vlen];
79.         for (int i = 0; i < mVexs.length; i++) {
80.             mVexs[i] = new VNode();
81.             mVexs[i].data = vexs[i];
82.             mVexs[i].firstEdge = null;
83.         }
85.         // 初始化"边"
86.         for (int i = 0; i < elen; i++) {
87.             // 读取边的起始顶点和结束顶点
88.             char c1 = edges[i][0];
89.             char c2 = edges[i][1];
90.             // 读取边的起始顶点和结束顶点
91.             int p1 = getPosition(edges[i][0]);
92.             int p2 = getPosition(edges[i][1]);
94.             // 初始化node1
95.             ENode node1 = new ENode();
96.             node1.ivex = p2;
97.             // 将node1链接到"p1所在链表的末尾"
98.             if(mVexs[p1].firstEdge == null)
99.               mVexs[p1].firstEdge = node1;
100.             else
101.                 linkLast(mVexs[p1].firstEdge, node1);
102.         }
103.     }
105.     /*
106.      * 将node节点链接到list的最后
107.      */
108.     private void linkLast(ENode list, ENode node) {
109.         ENode p = list;
111.         while(p.nextEdge!=null)
112.             p = p.nextEdge;
113.         p.nextEdge = node;
114.     }
116.     /*
117.      * 返回ch位置
118.      */
119.     private int getPosition(char ch) {
120.         for(int i=0; i<mVexs.length; i++)
121.             if(mVexs[i].data==ch)
122.                 return i;
123.         return -1;
124.     }
126.     /*
127.      * 读取一个输入字符
128.      */
129.     private char readChar() {
130.         char ch='0';
132.         do {
133.             try {
134.                 ch = (char)System.in.read();
135.             } catch (IOException e) {
136.                 e.printStackTrace();
137.             }
138.         } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
140.         return ch;
141.     }
143.     /*
144.      * 读取一个输入字符
145.      */
146.     private int readInt() {
147.         Scanner scanner = new Scanner(System.in);
148.         return scanner.nextInt();
149.     }
151.     /*
152.      * 深度优先搜索遍历图的递归实现
153.      */
154.     private void DFS(int i, boolean[] visited) {
155.         ENode node;
157.         visited[i] = true;
158.         System.out.printf("%c ", mVexs[i].data);
159.         node = mVexs[i].firstEdge;
160.         while (node != null) {
161.             if (!visited[node.ivex])
162.                 DFS(node.ivex, visited);
163.             node = node.nextEdge;
164.         }
165.     }
167.     /*
168.      * 深度优先搜索遍历图
169.      */
170.     public void DFS() {
171.         boolean[] visited = new boolean[mVexs.length];       // 顶点访问标记
173.         // 初始化所有顶点都没有被访问
174.         for (int i = 0; i < mVexs.length; i++)
175.             visited[i] = false;
177.         System.out.printf("DFS: ");
178.         for (int i = 0; i < mVexs.length; i++) {
179.             if (!visited[i])
180.                 DFS(i, visited);
181.         }
182.         System.out.printf("\n");
183.     }
185.     /*
186.      * 广度优先搜索（类似于树的层次遍历）
187.      */
188.     public void BFS() {
189.         int head = 0;
190.         int rear = 0;
191.         int[] queue = new int[mVexs.length];            // 辅组队列
192.         boolean[] visited = new boolean[mVexs.length];  // 顶点访问标记
194.         for (int i = 0; i < mVexs.length; i++)
195.             visited[i] = false;
197.         System.out.printf("BFS: ");
198.         for (int i = 0; i < mVexs.length; i++) {
199.             if (!visited[i]) {
200.                 visited[i] = true;
201.                 System.out.printf("%c ", mVexs[i].data);
202.                 queue[rear++] = i;  // 入队列
203.             }
205.             while (head != rear) {
206.                 int j = queue[head++];  // 出队列
207.                 ENode node = mVexs[j].firstEdge;
208.                 while (node != null) {
209.                     int k = node.ivex;
210.                     if (!visited[k])
211.                     {
212.                         visited[k] = true;
213.                         System.out.printf("%c ", mVexs[k].data);
214.                         queue[rear++] = k;
215.                     }
216.                     node = node.nextEdge;
217.                 }
218.             }
219.         }
220.         System.out.printf("\n");
221.     }
223.     /*
224.      * 打印矩阵队列图
225.      */
226.     public void print() {
227.         System.out.printf("List Graph:\n");
228.         for (int i = 0; i < mVexs.length; i++) {
229.             System.out.printf("%d(%c): ", i, mVexs[i].data);
230.             ENode node = mVexs[i].firstEdge;
231.             while (node != null) {
232.                 System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
233.                 node = node.nextEdge;
234.             }
235.             System.out.printf("\n");
236.         }
237.     }
239.     public static void main(String[] args) {
240.         char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
241.         char[][] edges = new char[][]{
242.             {'A', 'B'},
243.             {'B', 'C'},
244.             {'B', 'E'},
245.             {'B', 'F'},
246.             {'C', 'E'},
247.             {'D', 'C'},
248.             {'E', 'B'},
249.             {'E', 'D'},
250.             {'F', 'G'}};
251.         ListDG pG;
253.         // 自定义"图"(输入矩阵队列)
254.         //pG = new ListDG();
255.         // 采用已有的"图"
256.         pG = new ListDG(vexs, edges);
258.         pG.print();   // 打印图
259.         pG.DFS();     // 深度优先遍历
260.         pG.BFS();     // 广度优先遍历
261.     }
262. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4