數(shù)據(jù)結(jié)構(gòu)與算法：圖形結(jié)構(gòu)
圖
圖形結(jié)構(gòu)是一種比樹形結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)。在樹形結(jié)構(gòu)中，結(jié)點(diǎn)間具有分支層次關(guān)系，每一層上的結(jié)點(diǎn)只能和上一層中的至多一個(gè)結(jié)點(diǎn)相關(guān)，但可能和下一層的多個(gè)結(jié)點(diǎn)相關(guān)。而在圖形結(jié)構(gòu)中，任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)，即結(jié)點(diǎn)之間的鄰接關(guān)系可以是任意的。
因此，圖形結(jié)構(gòu)被用于描述各種復(fù)雜的數(shù)據(jù)對(duì)象，在自然科學(xué)、社會(huì)科學(xué)和人文科學(xué)等許多領(lǐng)域有著非常廣泛的應(yīng)用 。圖形結(jié)構(gòu)在計(jì)算機(jī)科學(xué)、人工智能、電子線路分析、最短路徑尋找、工程計(jì)劃、化學(xué)化合物分析統(tǒng)計(jì)力學(xué)、遺傳學(xué)、控制論語言學(xué)和社會(huì)科學(xué)等方面均有不同程度的應(yīng)用可以這樣說，圖形結(jié)構(gòu)在所有數(shù)據(jù)結(jié)構(gòu)中應(yīng)用最為廣泛。如在地鐵站中的線路圖：
圖的定義
圖是一種數(shù)據(jù)結(jié)構(gòu)，其中節(jié)點(diǎn)可以具有零個(gè)或多個(gè)相鄰元素，兩個(gè)節(jié)點(diǎn)的連接稱之為邊，節(jié)點(diǎn)在圖形結(jié)構(gòu)中也被稱為頂點(diǎn)，一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的經(jīng)過的的線路稱為路徑。
- 圖形結(jié)構(gòu)有3種類型：無向圖、有向圖、帶權(quán)圖
- 無向圖：頂點(diǎn)A與頂點(diǎn)B之間的邊是無方向的，可以從A到B，也可以從B到A
- 有向圖：頂點(diǎn)A與頂點(diǎn)B之間的邊是有方向的，可以從A到B，但不可以從B到A
- 帶權(quán)圖：頂點(diǎn)A與頂點(diǎn)B之間的邊是帶有屬性的，如A到B的 距離。
圖的表達(dá)方式
圖的表達(dá)方式有兩種：鄰接矩陣(使用二維數(shù)組)和鄰接表(使用數(shù)組+鏈表)
鄰接矩陣
鄰接矩陣是表示圖形中各頂點(diǎn)之間的關(guān)系，矩陣的行和列對(duì)應(yīng)各頂點(diǎn)，坐標(biāo)位置上的值對(duì)于它們之間的關(guān)系，1為連接, 0為沒有連接。在程序中用二維數(shù)組來實(shí)現(xiàn)。
鄰接表
鄰接表只關(guān)系存在的邊，不需要去為不存在的邊分配空間，因此比鄰接矩陣來說，避免了不必要的空間浪費(fèi)。在程序中用數(shù)組+鏈表的形式實(shí)現(xiàn)，數(shù)組存儲(chǔ)對(duì)應(yīng)的頂點(diǎn)，鏈表存儲(chǔ)該頂點(diǎn)連接的所有頂點(diǎn)。
圖的搜索算法
圖形結(jié)構(gòu)基礎(chǔ)屬性和方法
以下的代碼演示都是以鄰接矩陣表達(dá)方式來實(shí)現(xiàn)的
- //圖形結(jié)構(gòu)(鄰接矩陣)
- class Graph {
- //存儲(chǔ)圖中所有頂點(diǎn)
- private List<String> vertexes;
- //圖形結(jié)構(gòu)的鄰接矩陣
- private int[][] matrix;
- //各頂點(diǎn)訪問情況，true為已訪問，false為未訪問
- private boolean[] visited;
- /**
- * 根據(jù)傳入的頂點(diǎn)信息生成矩陣
- * @param s
- */
- public Graph(String s[]) {
- vertexes = new ArrayList<>();
- for (String vertex : s){
- vertexes.add(vertex);
- }
- matrix = new int[s.length][s.length];
- }
- /**
- * 將倆個(gè)頂點(diǎn)連接，即生成邊
- * @param index1 頂點(diǎn)在集合中的索引
- * @param index2
- */
- public void connect(int index1, int index2){
- if (index1 < 0 || index1 > matrix.length || index2 < 0 || index2 > matrix.length){
- throw new RuntimeException("該頂點(diǎn)未存在");
- }
- //將新的鄰接添加的鄰接矩陣中
- matrix[index1][index2] = 1;
- matrix[index2][index1] = 1;
- }
- /**
- * 展示鄰接矩陣
- */
- public void showGraphMatrix(){
- for (int arr[] : matrix){
- System.out.println(Arrays.toString(arr));
- }
- }
- /**
- * 獲取頂點(diǎn)在鄰接矩陣對(duì)應(yīng)行row中的第一個(gè)鄰接頂點(diǎn)下標(biāo)
- * @param row
- * @return 當(dāng)有鄰接頂點(diǎn)時(shí)返回鄰接頂點(diǎn)下標(biāo)，沒有則返回-1
- */
- public int getFirstNeighbor(int row){
- for(int i =0; i<matrix.length; i++){
- if (matrix[row][i] != 0){
- return i;
- }
- }
- return -1;
- }
- /**
- * 獲取頂點(diǎn)在鄰接矩陣對(duì)于行row中col列的下一個(gè)鄰接頂點(diǎn)
- * @param row
- * @param col
- * @return 當(dāng)有鄰接頂點(diǎn)時(shí)返回鄰接頂點(diǎn)下標(biāo)，沒有則返回-1
- */
- public int getNeighbor(int row, int col){
- for (int i=col+1; i<matrix.length; i++){
- if (matrix[row][i] != 0){
- return i;
- }
- }
- return -1;
- }
- }
深度優(yōu)先搜索
深度優(yōu)先搜索屬于圖算法的一種，英文縮寫為DFS即Depth First Search.其過程簡(jiǎn)要來說是對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問一次。這樣的訪問策略是優(yōu)先往縱向進(jìn)行深入挖掘，而不是對(duì)一個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)進(jìn)行橫線訪問。簡(jiǎn)單來說就是一條路走到死，不行再掉頭。
思路：從當(dāng)前頂點(diǎn)選一個(gè)與之連接而未訪問過的頂點(diǎn)，將當(dāng)前節(jié)點(diǎn)往該鄰接頂點(diǎn)移動(dòng)，如果鄰接頂點(diǎn)沒有未訪問的，則回溯到上一個(gè)頂點(diǎn)位置，繼續(xù)該步驟。直到所有頂點(diǎn)都訪問過。
往鄰接但未訪問過的頂點(diǎn)移動(dòng)
鄰接頂點(diǎn)沒有未訪問的，進(jìn)行回溯，直到遇到未訪問的鄰接頂點(diǎn)
當(dāng)所有頂點(diǎn)都被訪問過時(shí)，退出算法
下面是深度優(yōu)先搜索的過程動(dòng)畫
代碼演示
- public void dsf(){
- visited = new boolean[vertexes.size()];
- //以在集合中下標(biāo)為0的頂點(diǎn)，進(jìn)行深度搜索
- dsf(visited, 0);
- }
- /**
- * 深度優(yōu)先搜索
- * @param visited
- * @param row
- */
- public void dsf(boolean[] visited, int row){
- //輸出當(dāng)前頂點(diǎn)
- System.out.print(vertexes.get(row) + " -> ");
- //將當(dāng)前頂點(diǎn)設(shè)為已訪問
- visited[row] = true;
- //獲取當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)下標(biāo)
- int index = getFirstNeighbor(row);
- //如果當(dāng)前頂點(diǎn)有鄰接頂點(diǎn)則進(jìn)行深度搜索
- while (index != -1){
- //當(dāng)鄰接頂點(diǎn)未訪問時(shí)，則遞歸遍歷
- if (visited[index] != true){
- dsf(visited, index);
- }
- //當(dāng)鄰接頂點(diǎn)已訪問時(shí)，則尋找另一個(gè)鄰接頂點(diǎn)
- index = getNeighbor(row, index);
- }
- }
寬度優(yōu)先搜索
寬度優(yōu)先搜索算法(又稱廣度優(yōu)先搜索)是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。
寬度優(yōu)先搜索算法類似于一個(gè)分層搜索的過程，寬度優(yōu)先搜索算法需要一個(gè)隊(duì)列以保持訪問過頂點(diǎn)的順序，以便按這個(gè)順序來訪問這些頂點(diǎn)的鄰接頂點(diǎn)。
思路：依次訪問當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)，并按訪問順序?qū)⑦@些鄰接頂點(diǎn)存儲(chǔ)在隊(duì)列中，當(dāng)當(dāng)前頂點(diǎn)的所有鄰接頂點(diǎn)都被訪問后，從隊(duì)列中彈出一個(gè)頂點(diǎn)，以該頂點(diǎn)為當(dāng)前頂點(diǎn)繼續(xù)該步驟，直到所有頂點(diǎn)都被訪問過。
依次訪問當(dāng)前頂點(diǎn)的所有鄰接頂點(diǎn)，并把這些鄰接頂點(diǎn)按訪問順序存儲(chǔ)在隊(duì)列中
當(dāng)前頂點(diǎn)沒有未訪問的鄰接頂點(diǎn)，從隊(duì)列中彈出一個(gè)頂點(diǎn)，以該彈出頂點(diǎn)繼續(xù)訪問未訪問的鄰接頂點(diǎn)
注意，雖然圖中的頂點(diǎn)都已經(jīng)訪問過了，但還是要等隊(duì)列中的所有頂點(diǎn)彈出訪問后，算法才結(jié)束
下面時(shí)寬度優(yōu)先搜索的過程動(dòng)畫
代碼演示
- public void bfs(){
- visited = new boolean[vertexes.size()];
- ////以在集合中下標(biāo)為0的頂點(diǎn)，進(jìn)行廣度優(yōu)先搜索
- bfs(visited, 0);
- }
- /**
- * 廣度優(yōu)先搜索
- * @param visited
- * @param row
- */
- public void bfs(boolean[] visited, int row){
- //創(chuàng)建隊(duì)列，存儲(chǔ)遍歷鄰接頂點(diǎn)的順序
- LinkedList queue = new LinkedList();
- //輸出當(dāng)前頂點(diǎn)
- System.out.print(vertexes.get(row) + " -> ");
- //將當(dāng)前頂點(diǎn)設(shè)為已訪問
- visited[row] = true;
- //將當(dāng)前頂點(diǎn)加入隊(duì)列中
- queue.add(row);
- //當(dāng)隊(duì)列不為空時(shí)，即有未搜索的鄰接頂點(diǎn)，進(jìn)行搜索
- while (!queue.isEmpty()){
- //按順序從隊(duì)列中彈出鄰接頂點(diǎn)下標(biāo)
- int last = (Integer)queue.removeFirst();
- //獲取該彈出頂點(diǎn)的鄰接頂點(diǎn)下標(biāo)
- int index = getFirstNeighbor(last);
- //當(dāng)彈出頂點(diǎn)有鄰接頂點(diǎn)時(shí)，進(jìn)行廣度搜索
- while(index != -1){
- //當(dāng)鄰接頂點(diǎn)未訪問時(shí)
- if(visited[index] != true){
- //輸出該鄰接頂點(diǎn)
- System.out.print(vertexes.get(index) + " -> ");
- //把該鄰接頂點(diǎn)設(shè)為已訪問
- visited[index] = true;
- //將該鄰接頂點(diǎn)加入隊(duì)列
- queue.addLast(index);
- }
- //繼續(xù)尋找彈出頂點(diǎn)的另一個(gè)鄰接頂點(diǎn)
- index = getNeighbor(last, index);
- }
- }
- }
完整演示代碼
- public class GraphDemo {
- public static void main(String[] args) {
- String[] s = {"A","B","C","D","E","F","G"};
- Graph graph = new Graph(s);
- //A-B A-C A-G A-F F-D F-E D-E E-G
- graph.connect(0, 1);
- graph.connect(0, 2);
- graph.connect(0, 6);
- graph.connect(0, 5);
- graph.connect(5, 3);
- graph.connect(5, 4);
- graph.connect(3, 4);
- graph.connect(4, 6);
- graph.showGraphMatrix();
- graph.dsf();//A -> B -> C -> F -> D -> E -> G ->
- System.out.println();
- graph.bfs();//A -> B -> C -> F -> G -> D -> E ->
- }
- }
- //圖形結(jié)構(gòu)
- class Graph {
- //存儲(chǔ)圖中所有頂點(diǎn)
- private List<String> vertexes;
- //圖形結(jié)構(gòu)的鄰接矩陣
- private int[][] matrix;
- //各頂點(diǎn)訪問情況，true為已訪問，false為未訪問
- private boolean[] visited;
- /**
- * 根據(jù)傳入的頂點(diǎn)信息生成矩陣
- * @param s
- */
- public Graph(String s[]) {
- vertexes = new ArrayList<>();
- for (String vertex : s){
- vertexes.add(vertex);
- }
- matrix = new int[s.length][s.length];
- }
- /**
- * 將倆個(gè)頂點(diǎn)連接，即生成邊
- * @param index1 頂點(diǎn)在集合中的索引
- * @param index2
- */
- public void connect(int index1, int index2){
- if (index1 < 0 || index1 > matrix.length || index2 < 0 || index2 > matrix.length){
- throw new RuntimeException("該頂點(diǎn)未存在");
- }
- //將新的鄰接添加的鄰接矩陣中
- matrix[index1][index2] = 1;
- matrix[index2][index1] = 1;
- }
- /**
- * 展示鄰接矩陣
- */
- public void showGraphMatrix(){
- for (int arr[] : matrix){
- System.out.println(Arrays.toString(arr));
- }
- }
- public void dsf(){
- visited = new boolean[vertexes.size()];
- //以在集合中下標(biāo)為0的頂點(diǎn)，進(jìn)行深度優(yōu)先搜索
- dsf(visited, 0);
- }
- /**
- * 深度優(yōu)先搜索
- * @param visited
- * @param row
- */
- public void dsf(boolean[] visited, int row){
- //輸出當(dāng)前頂點(diǎn)
- System.out.print(vertexes.get(row) + " -> ");
- //將當(dāng)前頂點(diǎn)設(shè)為已訪問
- visited[row] = true;
- //獲取當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)下標(biāo)
- int index = getFirstNeighbor(row);
- //如果當(dāng)前頂點(diǎn)有鄰接頂點(diǎn)則進(jìn)行深度搜索
- while (index != -1){
- //當(dāng)鄰接頂點(diǎn)未訪問時(shí)，則遞歸遍歷
- if (visited[index] != true){
- dsf(visited, index);
- }
- //當(dāng)鄰接頂點(diǎn)已訪問時(shí)，則尋找另一個(gè)鄰接頂點(diǎn)
- index = getNeighbor(row, index);
- }
- }
- public void bfs(){
- visited = new boolean[vertexes.size()];
- ////以在集合中下標(biāo)為0的頂點(diǎn)，進(jìn)行廣度優(yōu)先搜索
- bfs(visited, 0);
- }
- /**
- * 廣度優(yōu)先搜索
- * @param visited
- * @param row
- */
- public void bfs(boolean[] visited, int row){
- //創(chuàng)建隊(duì)列，存儲(chǔ)遍歷鄰接頂點(diǎn)的順序
- Queue queue = new ArrayDeque();
- //輸出當(dāng)前頂點(diǎn)
- System.out.print(vertexes.get(row) + " -> ");
- //將當(dāng)前頂點(diǎn)設(shè)為已訪問
- visited[row] = true;
- //將當(dāng)前頂點(diǎn)加入隊(duì)列中
- queue.add(row);
- //當(dāng)隊(duì)列不為空時(shí)，即有未搜索的鄰接頂點(diǎn)，進(jìn)行搜索
- while (!queue.isEmpty()){
- //按順序從隊(duì)列中彈出鄰接頂點(diǎn)下標(biāo)
- int last = (Integer)queue.poll();
- //獲取該彈出頂點(diǎn)的鄰接頂點(diǎn)下標(biāo)
- int index = getFirstNeighbor(last);
- //當(dāng)彈出頂點(diǎn)有鄰接頂點(diǎn)時(shí)，進(jìn)行廣度搜索
- while(index != -1){
- //當(dāng)鄰接頂點(diǎn)未訪問時(shí)
- if(visited[index] != true){
- //輸出該鄰接頂點(diǎn)
- System.out.print(vertexes.get(index) + " -> ");
- //把該鄰接頂點(diǎn)設(shè)為已訪問
- visited[index] = true;
- //將該鄰接頂點(diǎn)加入隊(duì)列
- queue.add(index);
- }
- //繼續(xù)尋找彈出頂點(diǎn)的另一個(gè)鄰接頂點(diǎn)
- index = getNeighbor(last, index);
- }
- }
- }
- /**
- * 獲取頂點(diǎn)在鄰接矩陣對(duì)應(yīng)行row中的第一個(gè)鄰接頂點(diǎn)下標(biāo)
- * @param row
- * @return 當(dāng)有鄰接頂點(diǎn)時(shí)返回鄰接頂點(diǎn)下標(biāo)，沒有則返回-1
- */
- public int getFirstNeighbor(int row){
- for(int i =0; i<matrix.length; i++){
- if (matrix[row][i] != 0){
- return i;
- }
- }
- return -1;
- }
- /**
- * 獲取頂點(diǎn)在鄰接矩陣對(duì)于行row中col列的下一個(gè)鄰接頂點(diǎn)
- * @param row
- * @param col
- * @return 當(dāng)有鄰接頂點(diǎn)時(shí)返回鄰接頂點(diǎn)下標(biāo)，沒有則返回-1
- */
- public int getNeighbor(int row, int col){
- for (int i=col+1; i<matrix.length; i++){
- if (matrix[row][i] != 0){
- return i;
- }
- }
- return -1;
- }
- }
