【数据结构与算法之图结构】邻接表的实现

小咪咪 2024-03-25 16:37 67阅读 0赞

#### 【数据结构与算法之图结构】邻接表的实现 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之图结构】邻接表的实现
         *   *   *  1 邻接表的定义
                 *  2 图的创建

###### 1 邻接表的定义 ######

邻接表包含由顶点节点构成的数组以及依附于每个顶点的边链表。

图的顶点类 VNode

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: VNode
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 16:08
     */
    
    public class VNode {
        
    
        int data; // 数据信息
        ArcNode firstArc; // 指向单链表, 即指向该顶点的第1条边
    
    }

边节点类ArcNode，即邻接表中单链表的节点类型

// 边节点类型
    class ArcNode {
        
        int adjvex; // 该边指向的顶点在数组中的位置(数组下标)
        ArcNode next; // 指向下一条边的指针
    
        ArcNode(int adjvex) {
        
            this.adjvex = adjvex;
        }
    }

图类

public class MyGragh {
        
    
        private VNode[] vNodes; // 存放图中全部顶点
    
        public void createGragh(int v[], int arc[]) {
        
            // 创建图结构的邻接表
    
        }
    
        public void travelByDFS() {
        
            // 深度优先搜索遍历图
        }
    
        public void travelBFS() {
        
            // 广度优先搜索遍历图
        }
    
    }

###### 2 图的创建 ######

v 0 = 2 , v 1 = 9 , v 2 = 6 , v 3 = 3 , v 4 = 7 v\_0 = 2,v\_1 = 9,v\_2 = 6,v\_3 = 3, v\_4 = 7 v0=2,v1=9,v2=6,v3=3,v4=7

创建邻接表的过程：

1.  创建图的顶点数组
2.  创建顶点之间的边，即创建每个顶点节点指向的单链表

Java代码实现：

public void createGragh(int v[], int arc[]) {
        
        // 创建图结构的邻接表(顶点元素由数组v指定，边由数组arc指定)
        vNodes = new VNode[v.length];
    
        // 初始化图中的顶点
        for (int i = 0; i < v.length; i++) {
        
            vNodes[i] = new VNode();
            vNodes[i].data = v[i]; // 给第i个顶点赋值
            vNodes[i].firstArc = null;
        }
    
        // 创建邻接表中的链表(建立顶点之间表的关系)
        int index = 0;
        ArcNode p, q = null;
        for (int i = 0; i < v.length; i++) {
        
            // 内层for循环负责为顶点vNodes[i] 创建存放边信息的链表
            for (; index < arc.length && arc[index] != -1; index++) {
        
                p = new ArcNode(arc[index]);
                if (vNodes[i].firstArc == null) {
        
                    vNodes[i].firstArc = p; // 顶点vNodes[i] 的第1条边
                } else {
        
                    q.next = p; // 其他边
                }
                q = p;
            }
            index++;
        }
    
    }