Java中广度优先搜索（BFS）如何将字符串顶点转换为整数顶点

核心思路是用哈希表（字典）给每个字符串顶点分配唯一整数ID，建立字符串和整数的双向映射，既满足图算法对整数顶点的要求，又能随时还原回原字符串。

具体步骤： #

1. 建立字符串-整数映射

   • 遍历所有TXT数据，收集所有出现的顶点字符串，给每个字符串分配唯一整数ID（比如从0或1开始递增）。
   • 维护两个字典：
     • str_to_id：键为顶点字符串，值为对应整数ID
     • id_to_str：键为整数ID，值为对应顶点字符串，用于后续把BFS结果转回原名字

2. 构建图结构

   • 用邻接表存储图，比如列表的列表，每个索引对应一个整数ID，列表里存储（邻居ID，边权）的元组。

3. 实现BFS

   • BFS完全基于整数ID进行遍历，和普通整数顶点的BFS逻辑一致。如果需要输出遍历结果，用id_to_str把ID转回原字符串即可。

代码示例（Python）： #

# 初始化映射字典和图
str_to_id = {}
id_to_str = {}
adjacency_list = []
current_id = 0

# 读取TXT文件构建映射和图
with open('graph_data.txt', 'r') as f:
    for line in f:
        # 拆分每行数据，假设格式是"Vertex1 Vertex2 EdgeWeight"
        v1_str, v2_str, weight = line.strip().split()
        weight = int(weight)
        
        # 处理顶点v1
        if v1_str not in str_to_id:
            str_to_id[v1_str] = current_id
            id_to_str[current_id] = v1_str
            adjacency_list.append([])
            current_id += 1
        # 处理顶点v2
        if v2_str not in str_to_id:
            str_to_id[v2_str] = current_id
            id_to_str[current_id] = v2_str
            adjacency_list.append([])
            current_id += 1
        
        # 添加边到邻接表（无向图加双向边，有向图只加单向）
        v1_id = str_to_id[v1_str]
        v2_id = str_to_id[v2_str]
        adjacency_list[v1_id].append((v2_id, weight))
        adjacency_list[v2_id].append((v1_id, weight))

# BFS实现（以从John开始为例）
def bfs(start_str):
    start_id = str_to_id[start_str]
    visited = [False] * len(adjacency_list)
    queue = [start_id]
    visited[start_id] = True
    
    while queue:
        current_id = queue.pop(0)
        # 输出原字符串名字
        print(id_to_str[current_id], end=' ')
        
        for neighbor_id, _ in adjacency_list[current_id]:
            if not visited[neighbor_id]:
                visited[neighbor_id] = True
                queue.append(neighbor_id)

# 调用BFS
bfs("John")

关键点说明： #

• 映射过程仅在读取数据时执行一次，后续所有图操作都用整数ID，完全不影响BFS逻辑。
• 若为有向图，只需添加单向边；无向图则添加双向边。
• 该方法适配所有需要整数顶点的图算法，包括DFS、Dijkstra等。

内容的提问来源于stack exchange，提问作者Anon