算法-数据结构-图-邻接表构建

邻接表的基本概念

1. 顶点（Vertex）：

   • 图中的每个顶点用一个节点表示。

   • 每个顶点存储一个链表或数组，用于记录与该顶点直接相连的其他顶点。

2. 边（Edge）：

   • 如果顶点 A 和顶点 B 之间有一条边，那么在 A 的邻接表中会记录 B，同时在 B 的邻接表中也会记录 A（如果是无向图）。

3. 存储方式：

   • 邻接表可以用多种方式实现，比如：

     • 链表：每个顶点对应一个链表，链表中存储与该顶点相连的其他顶点。

     • 动态数组：每个顶点对应一个动态数组（如 ArrayList），数组中存储与该顶点相连的其他顶点。

     • 哈希表：每个顶点对应一个哈希表，键是相邻顶点，值可以是边的权重（适用于带权图）。

4. 代码实现

顶点定义

public class Node {
    //节点位置
    int data;
    //下一个节点
    Node nextNode;
    //节点默认空值
    Node() {

    }
    ;
    //节点变量
    Node(int val)
    {
        data=val;
    }
    //节点初始化
    Node(int val,Node node)
    {
        data=val;
        nextNode=node;
    }
}

邻接表创建与打印

import java.util.ArrayList;
import java.util.List;

public class GraphTest {
    //创建领接表
    //顶点 A B C D E F
    //边 AB AC BD DF EF
    public static void creatGraph()
    {
        //创建顶点
        List<Character> vList=new ArrayList<>();
        for(int i=0;i<6;i++)
        {
            vList.add((char)('A'+i));
        }
        //创建空列表存储空节点,表示相互领接关系
        List<Node> vNodeList=new ArrayList<>();
        for(int i=0;i<vList.size();i++)
        {
            vNodeList.add(null);
        }
        //插入领接关系
        //A->B 0-1
        insert(0,1,vNodeList);
        //A->C 0-2
        insert(0,2,vNodeList);
        //B->D 1-3
        insert(1,3,vNodeList);
        //D->F 3-5
        insert(3,5,vNodeList);
        //E->F 4-5
        insert(4,5,vNodeList);
        //领接表打印

        for(int i=0;i<vNodeList.size();i++)
        {
            System.out.print(vList.get(i));
            System.out.print("-->");
            Node curNode=vNodeList.get(i);
            while (curNode!=null)
                {
                    System.out.print(vList.get(curNode.data));
                    System.out.print(" ");
                    System.out.print(curNode.data);
                    System.out.print(" ");
                    curNode=curNode.nextNode;
                }
            System.out.println();

        }
    }
    //头插入法插入相互领接数据
    //v1为顶点位置，v2为相互领接顶点的位置
    public static void insert(int v1,int v2,List<Node> list){
        //创建一个节点
        Node newNode=new Node(v2);
        //新的节点指向列表里的节点
        newNode.nextNode=list.get(v1);
        //存储当前节点在列表里
        list.set(v1,newNode);
    }

    public static void main(String[] args) {
        creatGraph();
    }
}