算法-数据布局-图-毗邻表构建

毗邻表的根本概念

• 极点（Vertex）：
  
  
  
  • 图中的每个极点用一个节点表示。
    
  • 每个极点存储一个链表或数组，用于记载与该极点直接相连的其他极点。
    
  
  
• 边（Edge）：
  
  
  
  • 如果极点 A 和极点 B 之间有一条边，那么在 A 的毗邻表中会记载 B，同时在 B 的毗邻表中也会记载 A（如果是无向图）。
    
  
  
• 存储方式：
  
  
  
  • 毗邻表可以用多种方式实现，比如：
    
    
    
    • 链表：每个极点对应一个链表，链表中存储与该极点相连的其他极点。
      
    • 动态数组：每个极点对应一个动态数组（如 ArrayList），数组中存储与该极点相连的其他极点。
      
    • 哈希表：每个极点对应一个哈希表，键是相邻极点，值可以是边的权重（适用于带权图）。
      
    
    
  
  
• 代码实现
  

极点界说

1. public class Node {
2.     //节点位置
3.     int data;
4.     //下一个节点
5.     Node nextNode;
6.     //节点默认空值
7.     Node() {
9.     }
10.     ;
11.     //节点变量
12.     Node(int val)
13.     {
14.         data=val;
15.     }
16.     //节点初始化
17.     Node(int val,Node node)
18.     {
19.         data=val;
20.         nextNode=node;
21.     }
22. }

复制代码

毗邻表创建与打印

1. import java.util.ArrayList;
2. import java.util.List;
4. public class GraphTest {
5.     //创建领接表
6.     //顶点 A B C D E F
7.     //边 AB AC BD DF EF
8.     public static void creatGraph()
9.     {
10.         //创建顶点
11.         List<Character> vList=new ArrayList<>();
12.         for(int i=0;i<6;i++)
13.         {
14.             vList.add((char)('A'+i));
15.         }
16.         //创建空列表存储空节点,表示相互领接关系
17.         List<Node> vNodeList=new ArrayList<>();
18.         for(int i=0;i<vList.size();i++)
19.         {
20.             vNodeList.add(null);
21.         }
22.         //插入领接关系
23.         //A->B 0-1
24.         insert(0,1,vNodeList);
25.         //A->C 0-2
26.         insert(0,2,vNodeList);
27.         //B->D 1-3
28.         insert(1,3,vNodeList);
29.         //D->F 3-5
30.         insert(3,5,vNodeList);
31.         //E->F 4-5
32.         insert(4,5,vNodeList);
33.         //领接表打印
35.         for(int i=0;i<vNodeList.size();i++)
36.         {
37.             System.out.print(vList.get(i));
38.             System.out.print("-->");
39.             Node curNode=vNodeList.get(i);
40.             while (curNode!=null)
41.                 {
42.                     System.out.print(vList.get(curNode.data));
43.                     System.out.print(" ");
44.                     System.out.print(curNode.data);
45.                     System.out.print(" ");
46.                     curNode=curNode.nextNode;
47.                 }
48.             System.out.println();
50.         }
51.     }
52.     //头插入法插入相互领接数据
53.     //v1为顶点位置，v2为相互领接顶点的位置
54.     public static void insert(int v1,int v2,List<Node> list){
55.         //创建一个节点
56.         Node newNode=new Node(v2);
57.         //新的节点指向列表里的节点
58.         newNode.nextNode=list.get(v1);
59.         //存储当前节点在列表里
60.         list.set(v1,newNode);
61.     }
63.     public static void main(String[] args) {
64.         creatGraph();
65.     }
66. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。