浅谈数据结构之图的数据结构实现（二）

￡神魔★判官ぃ 2023-06-16 04:53 32阅读 0赞

[上一篇][Link 1]

### 浅谈数据结构之图的数据结构实现（二） ###

*   *  无向邻接矩阵
     *  有向邻接矩阵
     *  无向邻接表
     *  有向邻接表

## 无向邻接矩阵 ##

public class MatrixNDG { 
    
        /** * 图顶点个数 */
        int size;
    
        /** * 图顶点名称 */
        char[] vertexs;
    
        /** * 图的关系矩阵 */
        int[][] matrix;
    
        /** * 构造图 * @param vertexs 图的所有顶点 * @param edges 图的关系数组 */
        public MatrixNDG(char[] vertexs, char[][] edges) { 
            size = vertexs.length;
            matrix = new int[size][size];
            this.vertexs = vertexs;
            for (char[] c : edges) { 
                // 根据顶点名称确定对应的矩阵下标
                int p1 = getPosition(c[0]);
                int p2 = getPosition(c[1]);
                // 无向图在对称位置存储
                matrix[p1][p2] = 1;
                matrix[p2][p1] = 1;
            }
        }
    
        private int getPosition(char ch) { 
            for (int i = 0; i < vertexs.length; i++) { 
                if (vertexs[i] == ch) { 
                    return i;
                }
            }
            return -1;
        }
    
        private void print() { 
            System.out.print(" ");
            for (char c : vertexs) { 
                System.out.print(c + " ");
            }
            System.out.println();
            int k = 0;
            for (int[] i : matrix) { 
                System.out.print(vertexs[k++] + " ");
                for (int j : i) { 
                    System.out.print(j + " ");
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) { 
            char[] vexs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'};
            char[][] edges = new char[][]{ { 'A', 'C'},
                    { 'A', 'D'},
                    { 'A', 'F'},
                    { 'B', 'C'},
                    { 'C', 'D'},
                    { 'E', 'G'},
                    { 'D', 'G'},
                    { 'I', 'J'},
                    { 'J', 'G'},
                    { 'E', 'H'},
                    { 'H', 'K'}};
            MatrixNDG pG = new MatrixNDG(vexs, edges);
            pG.print();
        }
    }

输出图：
      A B C D E F G H I J K 
    A 0 0 1 1 0 1 0 0 0 0 0 
    B 0 0 1 0 0 0 0 0 0 0 0 
    C 1 1 0 1 0 0 0 0 0 0 0 
    D 1 0 1 0 0 0 1 0 0 0 0 
    E 0 0 0 0 0 0 1 1 0 0 0 
    F 1 0 0 0 0 0 0 0 0 0 0 
    G 0 0 0 1 1 0 0 0 0 1 0 
    H 0 0 0 0 1 0 0 0 0 0 1 
    I 0 0 0 0 0 0 0 0 0 1 0 
    J 0 0 0 0 0 0 1 0 1 0 0 
    K 0 0 0 0 0 0 0 1 0 0 0

## 有向邻接矩阵 ##

public class MatrixDG { 
    
        /** * 图顶点个数 */
        int size;
    
        /** * 图顶点名称 */
        char[] vertexs;
    
        /** * 图的关系矩阵 */
        int[][] matrix;
    
        /** * 构造图 * @param vertexs 图的所有顶点 * @param edges 图的关系数组 */
        public MatrixDG(char[] vertexs, char[][] edges) { 
            size = vertexs.length;
            matrix = new int[size][size];
            this.vertexs = vertexs;
            for (char[] c : edges) { 
                // 根据顶点名称确定对应的矩阵下标
                int p1 = getPosition(c[0]);
                int p2 = getPosition(c[1]);
                // 无向图在对称位置存储
                matrix[p1][p2] = 1;
                // 这行代码打开就是无向邻接矩阵
                //matrix[p2][p1] = 1;
            }
        }
    
        private int getPosition(char ch) { 
            for (int i = 0; i < vertexs.length; i++) { 
                if (vertexs[i] == ch) { 
                    return i;
                }
            }
            return -1;
        }
    
        private void print() { 
            System.out.print(" ");
            for (char c : vertexs) { 
                System.out.print(c + " ");
            }
            System.out.println();
            int k = 0;
            for (int[] i : matrix) { 
                System.out.print(vertexs[k++] + " ");
                for (int j : i) { 
                    System.out.print(j + " ");
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) { 
            char[] vexs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'};
            char[][] edges = new char[][]{ { 'A', 'C'},
                    { 'A', 'D'},
                    { 'A', 'F'},
                    { 'B', 'C'},
                    { 'C', 'D'},
                    { 'E', 'G'},
                    { 'D', 'G'},
                    { 'I', 'J'},
                    { 'J', 'G'},
                    { 'E', 'H'},
                    { 'H', 'K'}};
            MatrixDG pG = new MatrixDG(vexs, edges);
            pG.print();
        }
    }

输出图
      A B C D E F G H I J K 
    A 0 0 1 1 0 1 0 0 0 0 0 
    B 0 0 1 0 0 0 0 0 0 0 0 
    C 0 0 0 1 0 0 0 0 0 0 0 
    D 0 0 0 0 0 0 1 0 0 0 0 
    E 0 0 0 0 0 0 1 1 0 0 0 
    F 0 0 0 0 0 0 0 0 0 0 0 
    G 0 0 0 0 0 0 0 0 0 0 0 
    H 0 0 0 0 0 0 0 0 0 0 1 
    I 0 0 0 0 0 0 0 0 0 1 0 
    J 0 0 0 0 0 0 1 0 0 0 0 
    K 0 0 0 0 0 0 0 0 0 0 0

## 无向邻接表 ##

public class ListNDG { 
    
        /** * 邻接表节点类， 单链表数据结构 */
        Vertex[] vertesLists;
    
        /** * 链表大小 */
        int size;
    
        class Vertex { 
            char ch;
            Vertex next;
    
            Vertex (char ch) { 
                this.ch = ch;
            }
            void add(char ch) { 
                Vertex node = this;
                while (node.next != null) { 
                    node = node.next;
                }
                node.next = new Vertex(ch);
            }
        }
    
        public ListNDG(char[] vertexs, char[][] edges) { 
            size = vertexs.length;
            //确定邻接表大小
            this.vertesLists = new Vertex[size];
            //设置邻接表每一个信息
            for (int i = 0; i < size; i++) { 
                this.vertesLists[i] = new Vertex(vertexs[i]);
            }
            //存储信息
            for (char[] c : edges) { 
                int p1 = getPosition(c[0]);
                vertesLists[p1].add(c[1]);
                int p2 = getPosition(c[1]);
                vertesLists[p2].add(c[0]);
            }
        }
    
        private int getPosition(char c) { 
            for (int i = 0; i < size; i++) { 
                if (vertesLists[i].ch == c) { 
                    return i;
                }
            }
            return -1;
        }
    
        public void print() { 
            for (int i = 0; i < size; i++) { 
                Vertex temp = vertesLists[i];
                while (temp != null) { 
                    System.out.print(temp.ch + " ");
                    temp = temp.next;
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) { 
            char[] vexs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'};
            char[][] edges = new char[][]{ { 'A', 'C'},
                    { 'A', 'D'},
                    { 'A', 'F'},
                    { 'B', 'C'},
                    { 'C', 'D'},
                    { 'E', 'G'},
                    { 'D', 'G'},
                    { 'I', 'J'},
                    { 'J', 'G'},
                    { 'E', 'H'},
                    { 'H', 'K'}};
            ListNDG pG = new ListNDG(vexs, edges);
            pG.print();
        }
    }

输出：
    A C D F 
    B C 
    C A B D 
    D A C G 
    E G H 
    F A 
    G E D J 
    H E K 
    I J 
    J I G 
    K H

## 有向邻接表 ##

public class ListDG { 
    
        /** * 邻接表节点类， 单链表数据结构 */
        Vertex[] vertesLists;
    
        /** * 链表大小 */
        int size;
    
        class Vertex { 
            char ch;
            Vertex next;
    
            Vertex (char ch) { 
                this.ch = ch;
            }
            void add(char ch) { 
                Vertex node = this;
                while (node.next != null) { 
                    node = node.next;
                }
                node.next = new Vertex(ch);
            }
        }
    
        public ListDG(char[] vertexs, char[][] edges) { 
            size = vertexs.length;
            //确定邻接表大小
            this.vertesLists = new Vertex[size];
            //设置邻接表每一个信息
            for (int i = 0; i < size; i++) { 
                this.vertesLists[i] = new Vertex(vertexs[i]);
            }
            //存储信息
            for (char[] c : edges) { 
                int p1 = getPosition(c[0]);
                vertesLists[p1].add(c[1]);
                // 此处打开就是无相邻接表
                //int p2 = getPosition(c[1]);
                //vertesLists[p2].add(c[0]);
            }
        }
    
        private int getPosition(char c) { 
            for (int i = 0; i < size; i++) { 
                if (vertesLists[i].ch == c) { 
                    return i;
                }
            }
            return -1;
        }
    
        public void print() { 
            for (int i = 0; i < size; i++) { 
                Vertex temp = vertesLists[i];
                while (temp != null) { 
                    System.out.print(temp.ch + " ");
                    temp = temp.next;
                }
                System.out.println();
            }
        }
    
        public static void main(String[] args) { 
            char[] vexs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'};
            char[][] edges = new char[][]{ { 'A', 'C'},
                    { 'A', 'D'},
                    { 'A', 'F'},
                    { 'B', 'C'},
                    { 'C', 'D'},
                    { 'E', 'G'},
                    { 'D', 'G'},
                    { 'I', 'J'},
                    { 'J', 'G'},
                    { 'E', 'H'},
                    { 'H', 'K'}};
            ListDG pG = new ListDG(vexs, edges);
            pG.print();
        }
    }

输出：
    A C D F 
    B C 
    C D 
    D G 
    E G H 
    F 
    G 
    H K 
    I J 
    J G 
    K

[Link 1]: https://blog.csdn.net/cuixhao110/article/details/103224797