Java实现顺序表、链表、栈、队列、二叉树、图

待我称王封你为后i 2023-07-03 10:40 33阅读 0赞

### 文章目录 ###

*   *  1 顺序表
     *  2 链表
     *  3 栈
     *  4 队列
     *  5 二叉树
     *  6 图

## 1 顺序表 ##

import java.util.Scanner;
    
    //此示例顺序表下标从 1 开始，不是 0
    
    class DATA { 
        String key;
        String name;
        int age;
    }
    
    class SLType { 
        static final int MAXLENGTH = 100;
        DATA[] ListData = new DATA[MAXLENGTH + 1];
        int ListLen;
    
        void SLInit(SLType SL) { 
            SL.ListLen = 0;
        }
    
        int SLLength(SLType SL) { 
            return SL.ListLen;
        }
    
        int SLInsert(SLType SL, int n, DATA data) { 
            int i;
            if (SL.ListLen >= MAXLENGTH) { 
                System.out.print("顺序表已满，不能插入节点！\n");
                return 0;
            }
            if (n < 1 || n > SL.ListLen - 1) { 
                System.out.println("插入元素序号错误，不能插入元素！");
                return 0;
            }
            for (int j = SL.ListLen; j >= n; j--) { 
                SL.ListData[j+1] = SL.ListData[j];
            }
            SL.ListData[n] = data;
            SL.ListLen++;
    
            return 1;
        }
    
        int SLAdd(SLType SL, DATA data) { 
            if (SL.ListLen >= MAXLENGTH) { 
                System.out.println("顺序表已满，不能再添加节点！");
                return 0;
            }
            SL.ListData[++SL.ListLen] = data;
            return 1;
        }
    
        int SLDelete(SLType SL, int n) { 
            if (n < 1 || n > SL.ListLen + 1) { 
                System.out.println("删除节点序号错误，不能删除节点！");
                return 0;
            }
            for(int i = n; i < SL.ListLen; i++) { 
              SL.ListData[i] = SL.ListData[i+1];
            }
    
            SL.ListLen--;
            return 1;
        }
    
        // 按序号查询节点
        DATA SLFindByNum(SLType SL, int n) { 
            if (n < 1 || n > SL.ListLen + 1) { 
                System.out.println("节点序号错误，不能返回节点！");
                return null;
            }
            return SL.ListData[n];
        }
    
        // 按关键字查询节点
        int SLFindByCont(SLType SL, String key) { 
            for (int i = 1; i <= SL.ListLen; i++) { 
                if (SL.ListData[i].key.compareTo(key) == 0)
                    return i;
            }
            return 0;
        }
    
        int SLAll(SLType SL) { 
            for (int i = 1; i <= SL.ListLen; i++) { 
                System.out.printf("(%s,%s,%d)\n",
                        SL.ListData[i].key, SL.ListData[i].name, SL.ListData[i].age);
            }
            return 0;
        }
    }
    
    public class SequenceList { 
        public static void main(String[] args) { 
            int i;
            SLType SL = new SLType();
            DATA pdata;
            String key;
            System.out.println("顺序表操作演示！");
    
            SL.SLInit(SL);
            System.out.println("顺序表初始化完成！");
    
            Scanner input = new Scanner(System.in);
            do { 
                System.out.print("输入添加的节点（学号 姓名 年龄）：");
                DATA data = new DATA();
                data.key = input.next();
                data.name = input.next();
                data.age = input.nextInt();
    
                if (data.age != 0) { 
                    if (SL.SLAdd(SL, data) == 0)
                        break;
                } else { //若年龄为0，退出死循环
                    break;
                }
            } while (true);
    
            System.out.println("\n顺序表的节点顺序为：");
            SL.SLAll(SL);
    
            System.out.print("要取出节点的序号：");
            i = input.nextInt();
            pdata = SL.SLFindByNum(SL, i);
            if (pdata != null) { 
                System.out.printf("第%d个节点为：(%s,%s,%d)\n", i, pdata.key, pdata.name, pdata.age);
            }
    
            System.out.print("要查找节点的关键字：");
            key = input.next();
            i = SL.SLFindByCont(SL, key);
            pdata = SL.SLFindByNum(SL, i);
            if (pdata != null) { 
                System.out.printf("第%d个节点为：(%s,%s,%d)\n", i, pdata.key, pdata.name, pdata.age);
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]

## 2 链表 ##

import java.util.Scanner;
    
    // 此例为不带头结点的链表
    class Node { 
        String key;
        String name;
        int age;
    }
    
    class LType { 
        Node nodeData = new Node();
        LType nextNode;
    
        // 在尾部追加节点
        LType AddEnd(LType head, Node nodeData) { 
            LType node, htemp;
            if ((node = new LType()) == null) { 
                System.out.println("申请内存失败！");
                return null;
            } else { 
                node.nodeData = nodeData;
                node.nextNode = null;
                if (head == null) { 
                    head = node;
                    return head;
                }
                htemp = head;
                while (htemp.nextNode != null) { 
                    htemp = htemp.nextNode;
                }
                htemp.nextNode = node;
                return head;
            }
        }
    
        // 在首部追加节点
        LType AddFirst(LType head, Node nodeData) { 
            LType node;
            if ((node = new LType()) == null) { 
                System.out.println("申请内存失败！");
                return null;
            } else { 
                node.nodeData = nodeData;
                node.nextNode = head;
                head = node;
                return head;
            }
        }
    
        LType FindNode(LType head, String key) { 
            LType htemp;
            htemp = head;
            while (htemp != null) { 
                if (htemp.nodeData.key.compareTo(key) == 0) { 
                    return htemp;
                }
                htemp = htemp.nextNode;
            }
    
            return null;
        }
    
        LType InsertNode(LType head, String findKey, Node nodeData) { 
            LType node, nodetemp;
            if ((node = new LType()) == null) { 
                System.out.println("申请内存失败！");
                return null;
            }
            node.nodeData = nodeData;
            nodetemp = FindNode(head, findKey);
            if (nodetemp != null) { 
                node.nextNode = nodetemp.nextNode;
                nodetemp.nextNode = node;
            } else { 
                System.out.println("未找到正确的插入位置！");
                node = null;
            }
    
            return head;
        }
    
        LType DeleteNode(LType head, String key) { 
            LType node, htemp;
            htemp = head;
            node = head;
    
            // 若待删除节点为头节点
            if (head != null && head.nodeData.key.compareTo(key) == 0) { 
                head = head.nextNode;
                htemp = null;
                return head;
            }
    
            // 若待删除节点不是头节点
            while (htemp != null) { 
                if (htemp.nodeData.key.compareTo(key) == 0) { 
                    node.nextNode = htemp.nextNode;
                    htemp = null;
                    return  head;
                } else { 
                    node = htemp;
                    htemp = htemp.nextNode;
                }
            }
    
            return head;
        }
    
        int LLength(LType head) { 
            LType htemp;
            int len = 0;
            htemp = head;
            while (htemp != null) { 
                len++;
                htemp = htemp.nextNode;
            }
            return len;
        }
    
        void AllNode(LType head) { 
            LType htemp;
            Node nodeData;
            htemp = head;
            System.out.printf("当前链表共 %d 个节点。如下：\n", LLength(head));
            while (htemp != null) { 
                nodeData = htemp.nodeData;
                System.out.printf("节点（%s,%s,%d）\n", nodeData.key, nodeData.name, nodeData.age);
                htemp = htemp.nextNode;
            }
        }
    }
    public class LinkedList { 
        public static void main(String[] args) { 
            LType node, head = null;
            LType list = new LType();
            String key, findkey;
    
            Scanner input = new Scanner(System.in);
            System.out.println("链表测试。");
            do { 
                System.out.print("请输入数据，格式为（关键字 姓名 年龄）：");
                Node nodeData = new Node();
                nodeData.key = input.next();
                if (nodeData.key.equals("0")) { 
                    break;//输入 0 ，则退出
                } else { 
                    nodeData.name = input.next();
                    nodeData.age = input.nextInt();
                    head = list.AddEnd(head, nodeData);
                }
            } while (true);
            list.AllNode(head);
    
            System.out.print("演示插入节点，请输入插入位置的关键字：");
            findkey = input.next();
            System.out.print("输入插入节点的数据（关键字 姓名 年龄）：");
            Node nodeData = new Node();
            nodeData.key = input.next();
            nodeData.name = input.next();
            nodeData.age = input.nextInt();
            head = list.InsertNode(head, findkey, nodeData);
            // 插入后遍历链表
            list.AllNode(head);
    
            System.out.print("演示删除节点，请输入删除节点的关键字：");
            key = input.next();
            head = list.DeleteNode(head, key);
            // 删除后遍历链表
            list.AllNode(head);
    
            System.out.print("演示在链表中查找，输入查找关键字：");
            key = input.next();
            node = list.FindNode(head, key);
            if (node != null) { 
                // nodeData = node.nodeData;
                System.out.printf("关键字 %s 对应的节点为（%s,%s,%d)\n",
                        key, node.nodeData.key, (node.nodeData).name, (node.nodeData).age);
            } else { 
                System.out.printf("链表中找不到关键字为 %s 的节点\n", key);
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2]

## 3 栈 ##

import java.util.Scanner;
    
    // 此例为顺序栈：栈是用数组实现的
    class Data2 { 
        String name;
        int age;
    }
    
    class SqStackType { 
        static int MAXLENGTH = 50;
        Data2[] data = new Data2[MAXLENGTH + 1];
        int top; // 栈顶：总是指向栈顶元素的下一位置
    
        SqStackType initSqStack() { 
            SqStackType stack;
            if ((stack = new SqStackType())  != null) { 
                stack.top = 0; // 设置栈顶为 0
                return stack;
            }
            return null;
        }
    
        boolean isEmpty(SqStackType stack) { 
            return stack.top == 0 ? true : false;
        }
    
        boolean isFull(SqStackType stack) { 
            return stack.top == MAXLENGTH ? true : false;
        }
    
        void clear(SqStackType stack) { 
            stack.top = 0;
        }
    
        void free(SqStackType stack) { 
            if (stack != null) { 
                stack = null;
            }
        }
    
        // JAVA只有按值调用, 参数是什么都会复制一份再操作, 就算是对象的引用也会复制一份新的引用,
        // 只不过指向的是同一个对象
        /*int push(SqStackType stack, Data data) { if (stack.top + 1 > MAXLENGTH) { Data[] old = stack.data; // 空间不够时，增加 MAXLENGTH 个空间 stack.data = new Data[MAXLENGTH * 2]; MAXLENGTH *= 2; for (int i = 0; i < stack.top; i++) { stack.data[i] = old[i]; } } stack.data[++stack.top] = data; return 1; }*/
    
        // 若想实现栈的动态增长，可将 Data 数组使用 ArrayList 替换
        int push(SqStackType stack, Data2 data) { 
            if (stack.top + 1 > MAXLENGTH) { 
                System.out.println("栈溢出！");
                return 0;
            }
            stack.data[++stack.top] = data;
            return 1;
        }
    
        Data2 pop(SqStackType stack) { 
            if (stack.top == 0) { 
                System.out.println("栈为空！");
                System.exit(0);
            }
            return stack.data[stack.top--];
        }
    
        // 读取栈顶数据
        Data2 peek(SqStackType stack) { 
            if (stack.top == 0) { 
                System.out.println("栈为空！");
                System.exit(0);
            }
            return stack.data[stack.top];
        }
    }
    public class SequentialStack { 
        public static void main(String[] args) { 
            SqStackType st = new SqStackType();
            Data2 data = new Data2();
    
            SqStackType stack = st.initSqStack();
            Scanner input = new Scanner(System.in);
            System.out.println("入栈操作...");
            do { 
                System.out.print("请输入数据，格式为（姓名 年龄）：");
                Data2 data1 = new Data2();
                data1.name = input.next();
                if (data1.name.equals("0")) { 
                    break; // 若输入 0 ，则退出
                }
                else { 
                    data1.age = input.nextInt();
                    st.push(stack, data1);
                }
            } while (true);
    
            System.out.println("出栈操作...");
            String temp = "y";
            while (!temp.equals("n")) { 
                System.out.print("是否继续出栈（y/n）：");
                temp = input.next();
    
                data = st.pop(stack);
                System.out.printf("出栈的数据是（%s,%d）\n", data.name, data.age);
            }
    
            System.out.println("测试结束！");
            st.free(st);
        }
    }

## 4 队列 ##

// 此例是用数组实现的队列
    
    import java.util.Scanner;
    
    class Data { 
        String name;
        int age;
    }
    
    class SQType { 
        static final int QUEUELENGTH = 15;
        Data[] data = new Data[QUEUELENGTH];
        int head;
        int tail;
    
        SQType initSQueue() { 
            SQType q;
            if ((q = new SQType()) != null) { 
                q.head = 0;
                q.tail = 0;
                return q;
            } else { 
                return null;
            }
        }
    
        boolean isEmpty(SQType q) { 
            return q.head == q.tail ? true : false;
        }
    
        boolean isFull(SQType q) { 
            return QUEUELENGTH == q.tail ? true : false;
        }
    
        void clear(SQType q) { 
            q.head = 0;
            q.tail = 0;
        }
    
        void free(SQType q) { 
            if (q != null) { 
                q = null;
            }
        }
    
        boolean inQueue(SQType q, Data data) { 
            if (q.tail == QUEUELENGTH) { 
                System.out.println("队列已满！操作失败！");
                return false;
            } else { 
                q.data[q.tail++] = data;
                return true;
            }
        }
        Data outQueue(SQType q) { 
            if (q.head == q.tail) { 
                System.out.println("队列已空！操作失败！");
                System.exit(0);
            } else { 
                return q.data[q.head++];
            }
            
            return null;
        }
        
        Data peek(SQType q) { 
            if (q.head == q.tail) { 
                System.out.println("空队列！");
                return null;
            } else { 
                return q.data[q.head];
            }
        }
        
        int len(SQType q) { 
            return q.tail - q.head;
        }
    }
    public class SequentialQueue { 
        public static void main(String[] args) { 
            SQType sq = new SQType();
            Data data;
            
            Scanner input = new Scanner(System.in);
            SQType queue = sq.initSQueue();
            System.out.println("入队列操作...");
            do { 
                System.out.print("请输入数据，格式（姓名 年龄）：");
                Data data1 = new Data();
                data1.name = input.next();
                data1.age = input.nextInt();
                if (data1.name.equals("0")) { 
                    break;
                } else { 
                    sq.inQueue(queue, data1);
                }
            } while (true);
    
            System.out.println("出队列操作...");
            String temp = "y";
            while (!temp.equals("n")) { 
                System.out.print("是否继续出队列（y/n）：");
                temp = input.next();
                data = sq.outQueue(queue);
                System.out.printf("出队列的数据是（%s,%d）\n", data.name, data.age);
            }
    
            System.out.println("测试结束！");
            sq.free(queue);
        }
    }

## 5 二叉树 ##

import java.io.IOException;
    import java.util.Scanner;
    
    class BiTreeType { 
        String data;
        BiTreeType left;
        BiTreeType right;
    }
    
    public class BiTree { 
        static final int MAXLENGTH = 20;
        static Scanner input = new Scanner(System.in);
    
        BiTreeType initBiTree() { 
            BiTreeType tree;
            String inputdata;
    
            // System.out.print("请输入节点数据：");
            if ((inputdata = input.next()).equals("#")) { 
                tree = null;
            } else { 
                if ((tree = new BiTreeType()) == null) { 
                    System.out.println("内存分配失败！");
                    System.exit(0);
                }
                tree.data = inputdata;
                tree.left = initBiTree();
                tree.right = initBiTree();
            }
    
            return tree;
        }
    
        void addNode(BiTreeType root) { 
            BiTreeType pnode, parent;
            String data;
            int choice;
    
            if ((pnode = new BiTreeType()) != null) { 
                System.out.print("请输入待插入二叉树节点数据：");
                pnode.data = input.next();
                pnode.left = null;
                pnode.right = null;
    
                System.out.print("请输入该节点父节点数据：");
                data = input.next();
                parent = findBiTreeNode(root, data);
    
                // 该节点不存在
                if (parent == null) { 
                    System.out.println("未找到该父节点！");
                    pnode = null;
                    return;
                }
    
                // 该节点存在
                System.out.println("*****************");
                System.out.print("1 添加该节点到左子树\n2 添加该节点到右子树\n0 退出\n");
                System.out.println("*****************");
                while (true) { 
                    System.out.printf("请输入您的选择（1 / 2 / 0）：");
                    choice = input.nextInt();
    
                    switch (choice) { 
                        case 1:
                            if (parent.left != null) { 
                                System.out.println("左子树不为空！");
                            } else { 
                                parent.left = pnode;
                            }
                            break;
                        case 2:
                            if (parent.right != null) { 
                                System.out.println("右子树不为空！");
                            } else { 
                                parent.right = pnode;
                            }
                            break;
                        case 0:
                            return;
                        default:
                            System.out.println("输入无效！");
                    }
                }
            }
        }
    
        BiTreeType findBiTreeNode(BiTreeType root, String data) { 
            BiTreeType node;
    
            if (root == null) { 
                return null;
            } else { 
                if (root.data.equals(data)) { 
                    return root;
                } else { 
                    if ((node = findBiTreeNode(root.left, data)) != null) { 
                        return node;
                    } else if ((node = findBiTreeNode(root.right, data)) != null) { 
                        return node;
                    } else { 
                        return null;
                    }
                }
            }
        }
    
        BiTreeType getLeftBiTree(BiTreeType root) { 
            if (root != null) { 
                return root.left;
            } else { 
                return null;
            }
        }
    
        BiTreeType getRightBiTree(BiTreeType root) { 
            if (root != null) { 
                return root.right;
            } else { 
                return null;
            }
        }
    
        boolean isEmpty(BiTreeType root) { 
            return root == null ? true : false;
        }
    
        // 计算二叉树深度
        int BiTreeDepth(BiTreeType root) { 
            int ldepth, rdepth;
    
            if (root == null) { 
                return 0;
            } else { 
                ldepth = BiTreeDepth(root.left);
                rdepth = BiTreeDepth(root.right);
                if (ldepth > rdepth) { 
                    return ldepth + 1;
                } else { 
                    return rdepth + 1;
                }
            }
        }
    
        void clearTree(BiTreeType root) { 
            if (root != null) { 
                clearTree(root.left);
                clearTree(root.right);
                root = null;
            }
        }
    
        // 显示节点数据
        void displayTreeNode(BiTreeType node) { 
            System.out.printf("%s ", node.data);
        }
    
        void preOrderTraverse(BiTreeType root) { 
            if (root != null) { 
                displayTreeNode(root);
                preOrderTraverse(root.left);
                preOrderTraverse(root.right);
            }
        }
    
        void inOrderTraverse(BiTreeType root) { 
            if (root != null) { 
                inOrderTraverse(root.left);
                displayTreeNode(root);
                inOrderTraverse(root.right);
            }
        }
    
        void postOrderTraverse(BiTreeType root) { 
            if (root != null) { 
                postOrderTraverse(root.left);
                postOrderTraverse(root.right);
                displayTreeNode(root);
            }
        }
    
        // 借助循环队列，按层次从左向右遍历二叉树
        void levelTraverse(BiTreeType root) { 
            BiTreeType node;
            // 循环队列
            BiTreeType[] circularQueue = new BiTreeType[MAXLENGTH];
            int head = 0; // 队首指针，始终指向队列首元素前一位置
            int tail = 0; // 队尾指针，始终指向队列中最后一个元素
    
            if (root != null) { 
                tail = (tail + 1) % MAXLENGTH;
                circularQueue[tail] = root;
            }
            // 队列不为空，进行循环
            while (head != tail) { 
                head = (head + 1) % MAXLENGTH;
                node = circularQueue[head];
                displayTreeNode(node);
    
                if (node.left != null) { 
                    tail = (tail + 1) % MAXLENGTH;
                    circularQueue[tail] = node.left;
                }
                if (node.right != null) { 
                    tail = (tail + 1) % MAXLENGTH;
                    circularQueue[tail] = node.right;
                }
            }
        }
    
        public static void main(String[] args) { 
            BiTreeType root = null;
            char choice;
            BiTree t = new BiTree();
            System.out.println("请按先序顺序输入节点值，输入 # 代表节点为空...");
            root = t.initBiTree();
    
            System.out.print("先序遍历二叉树：");
            t.preOrderTraverse(root);
            System.out.println();
    
            System.out.print("中序遍历二叉树：");
            t.inOrderTraverse(root);
            System.out.println();
    
            t.addNode(root);
    
            System.out.print("后序遍历二叉树：");
            t.postOrderTraverse(root);
            System.out.println();
    
            System.out.print("层次遍历二叉树：");
            t.levelTraverse(root);
            System.out.println();
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 4]

## 6 图 ##

import java.util.Scanner;
    
    class GraphMatrix { 
        static final int MAXVERTEXNUM = 20;     // 最大顶点数
        static final int MAXVALUE = 65535;      // 边上最大权值
        char[] vertex = new char[MAXVERTEXNUM]; // 顶点数组
        int GType;                              // 图的类型。1-有向图，0-无向图
        int vertexNum;                          // 实际顶点数
        int edgeNum;                            // 实际边数
        int[][] edgeWeight = new int[MAXVERTEXNUM][MAXVERTEXNUM];   // 保存边的权值
        int[] isTraverse = new int[MAXVERTEXNUM];                   // 遍历标志
    }
    public class Graph { 
        static Scanner input = new Scanner(System.in);
    
        int getIndexOfChar(char[] array, char c) { 
            for (int i = 0; i < array.length; i++) { 
                if (c == array[i])
                    return i;
            }
            return -1;
        }
        void createGraph(GraphMatrix g) { 
            int weight;
            char sVex, eVex;// 边的起始、结束顶点
    
            System.out.print("创建图，请输入图的类型（1：有向图/0：无向图)：");
            g.GType = input.nextInt();
    
            System.out.println("创建图，请输入各顶点信息...");
            System.out.print("请输入顶点个数：");
            g.vertexNum = input.nextInt();
            for (int l = 0; l < g.vertexNum; l++) { 
                System.out.printf("第 %d 个顶点：", l+1);
                g.vertex[l] = (input.next().toCharArray())[0];
            }
    
            System.out.println("创建图，请输入各边顶点及权值...");
            System.out.print("请输入边条数：");
            g.edgeNum = input.nextInt();
            for (int i = 0; i < g.edgeNum; i++) { 
                System.out.printf("第 %d 条边...\n", i+1);
                System.out.print("起始顶点：");
                sVex = input.next().charAt(0);
                System.out.print("结束顶点：");
                eVex = input.next().charAt(0);
                System.out.print("权值：");
                weight = input.nextInt();
    
                // 保存边 E（j，k）的权值
               /* int indexOfsVex = String.valueOf(g.vertex).indexOf(sVex); int indexOfeVex = String.valueOf(g.vertex).indexOf(eVex); g.edgeWeight[indexOfsVex][indexOfeVex] = weight;*/
    
                int indexOfsVex = getIndexOfChar(g.vertex, sVex);
                int indexOfeVex = getIndexOfChar(g.vertex, eVex);
                g.edgeWeight[indexOfsVex][indexOfeVex] = weight;
                // 若是无向图，保存边 E（k，j）的权值
                if (g.GType == 0) { 
                    g.edgeWeight[indexOfeVex][indexOfsVex]= weight;
                }
            }
        }
        
        // 清空矩阵
        void clearMatrix(GraphMatrix g) { 
            for (int i = 0; i < g.vertexNum; i++) { 
                for (int j = 0; j < g.vertexNum; j++) { 
                    g.edgeWeight[i][j] = g.MAXVALUE;
                }
            }
        }
    
        // 输出邻接矩阵
        void displayAdjacencyMatrix(GraphMatrix g) { 
            int i, j;
    
            // 先输出顶点信息
            for (i = 0; i < g.vertexNum; i++) { 
                System.out.printf("\t%c", g.vertex[i]);
            }
            System.out.println();
    
            // 输出邻接矩阵
            for (j = 0; j < g.vertexNum; j++) { 
                System.out.printf("%c", g.vertex[j]);
                for (i = 0; i < g.vertexNum; i++) { 
                    if (g.edgeWeight[j][i] >= g.MAXVALUE || g.edgeWeight[j][i] == 0) { 
                        // 权值大于等于最大权值时，输出无穷大的符号
                        System.out.print("\t∞");
                    } else { 
                        System.out.printf("\t%d", g.edgeWeight[j][i]);
                    }
                }
                System.out.println();
            }
        }
    
        // 从第 n 个节点开始，深度遍历图
        void DepthFirstTravOne(GraphMatrix g, int n) { 
            g.isTraverse[n] = 1;            // 标记该顶点已被遍历
            System.out.printf("->%c", g.vertex[n]);
    
            // 添加处理节点的操作
            for (int i = 0; i < g.vertexNum; i++) { 
                if (g.edgeWeight[n][i] != g.MAXVALUE && g.isTraverse[n] == 0)
                    DepthFirstTravOne(g, i); // 递归进行遍历
            }
        }
    
        void DepthFirstTraverse(GraphMatrix g) { 
            // 清除各顶点遍历标志
            for (int i = 0; i < g.vertexNum; i++) { 
                g.isTraverse[i] = 0;
            }
            System.out.println("深度优先遍历节点...");
            for (int i = 0; i < g.vertexNum; i++) { 
                if (g.isTraverse[i] == 0)
                    DepthFirstTravOne(g, i);
            }
            System.out.println();
        }
    
        public static void main(String[] args) { 
            Graph graph = new Graph();
            GraphMatrix gMatrix = new GraphMatrix();
            graph.clearMatrix(gMatrix);
            graph.createGraph(gMatrix);
            System.out.println("该图的邻接矩阵如下：");
            graph.displayAdjacencyMatrix(gMatrix);
            System.out.println("深度优先遍历该图：");
            graph.DepthFirstTraverse(gMatrix);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 5]  
运行结果：

创建图，请输入图的类型（1：有向图/0：无向图)：0
    创建图，请输入各顶点信息...
    请输入顶点个数：5
    第 1 个顶点：A
    第 2 个顶点：B
    第 3 个顶点：C
    第 4 个顶点：D
    第 5 个顶点：E
    创建图，请输入各边顶点及权值...
    请输入边条数：7
    第 1 条边...
    起始顶点：A
    结束顶点：B
    权值：9
    第 2 条边...
    起始顶点：A
    结束顶点：C
    权值：6
    第 3 条边...
    起始顶点：A
    结束顶点：D
    权值：3
    第 4 条边...
    起始顶点：B
    结束顶点：C
    权值：4
    第 5 条边...
    起始顶点：B
    结束顶点：D
    权值：5
    第 6 条边...
    起始顶点：C
    结束顶点：E
    权值：5
    第 7 条边...
    起始顶点：D
    结束顶点：E
    权值：6
    该图的邻接矩阵如下：
    	A	B	C	D	E
    A	∞	9	6	3	∞
    B	9	∞	4	5	∞
    C	6	4	∞	∞	5
    D	3	5	∞	∞	6
    E	∞	∞	5	6	∞
    深度优先遍历该图：
    深度优先遍历节点...
    ->A->B->C->D->E
    
    Process finished with exit code 0

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200205160622641.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200205160717468.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200205160731777.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200205160930203.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200205160953484.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200209104206223.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg==,size_16,color_FFFFFF,t_70