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

邻接表的基本概念

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 EFpublic 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-1insert(0,1,vNodeList);//A->C 0-2insert(0,2,vNodeList);//B->D 1-3insert(1,3,vNodeList);//D->F 3-5insert(3,5,vNodeList);//E->F 4-5insert(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();}
}