R语言igraph绘图优化及类TSP多访问路径求解求助

一、igraph绘图优化方案 #

当前绘图杂乱的核心原因是布局拥挤、元素重叠，可通过以下调整优化：

• 更换布局算法：默认布局易导致节点堆积，改用Kamada-Kawai或Fruchterman-Reingold布局，能更合理分散节点：

  layout = layout_with_kk(g1) # 或 layout_with_fr(g1)
  

• 突出核心节点：将Seoul设置为不同颜色和大小，明确图的中心：

  vertex.color = ifelse(V(g1)$name == "Seoul", "#FF4500", "#1E90FF"),
  vertex.size = ifelse(V(g1)$name == "Seoul", 10, 5)
  

• 简化边与标签：减少不必要的边标签，调整边的透明度和曲率避免重叠：

  edge.color = adjustcolor("gray80", alpha.f = 0.6), # 降低边的透明度
  edge.curved = 0.1, # 轻微弯曲边，减少交叉
  edge.label = ifelse(E(g1)$distance > 20, E(g1)$distance, NA), # 只显示较长距离的标签
  edge.label.cex = 0.5 # 缩小标签字号
  

• 完整优化后的绘图代码：

  library(igraph)
  
  # 原图构建代码
  g1 <- graph( c("Seoul","Incheon","Seoul","Goyang","Seoul","Seongnam","Seoul",
                "Bucheon","Seoul","Uijeongbu","Seoul","Gimpo",
                "Seoul","Gwangmyeong", "Seoul", "Hanam","Seoul", "Guri",
                "Seoul","Gwacheon","Busan","Changwon","Busan","Gimhae",
                "Busan","Jeju","Busan","Yangsan","Busan","Geoje",
                "Incheon","Goyang","Incheon","Bucheon","Incheon","Siheung",
                "Incheon","Jeju","Incheon","Gimpo","Daegu","Gumi",
                "Daegu","Gyeongsan","Daegu","Yeongcheon","Daejeon",
                "Cheongju","Daejeon","Nonsan","Daejeon","Gongju",
                "Daejeon","Gyeryong","Gwangju","Naju","Suwon","Yongin",
                "Suwon","Seongnam","Suwon","Hwaseong","Suwon","Ansan",
                "Suwon","Gunpo","Suwon","Osan","Suwon","Uiwang",
                "Ulsan","Yangsan","Ulsan","Gyeongju","Ulsan","Miryang",
                "Yongin","Seongnam","Yongin","Hwaseong","Yongin","Pyeongtaek",
                "Yongin","Gwangju-si","Yongin","Icheon","Yongin","Anseong",
                "Yongin","Uiwang","Goyang","Gimpo","Goyang","Paju","Goyang",
                "Yangju","Changwon","Gimhae","Changwon","Jinju","Changwon",
                "Miryang","Seongnam","Gwangju-si","Seongnam","Hanam","Seongnam",
                "Uiwang","Seongnam","Gwacheon","Hwaseong","Ansan","Hwaseong",
                "Pyeongtaek","Hwaseong","Gunpo","Hwaseong","Osan","Cheongju",
                "Cheonan","Cheongju","Sejong","Bucheon","Siheung","Bucheon",
                "Gwangmyeong","Ansan","Anyang","Ansan","Siheung","Ansan",
                "Gunpo","Namyangju","Uijeongbu","Namyangju","Chuncheon",
                "Namyangju","Hanam","Namyangju","Guri","Cheonan","Pyeongtaek",
                "Cheonan","Sejong","Cheonan","Asan","Cheonan","Anseong",
                "Jeonju","Gimje","Gimhae","Yangsan","Gimhae","Miryang",
                "Pyeongtaek","Asan","Pyeongtaek","Osan","Pyeongtaek","Anseong",
                "Pyeongtaek","Dangjin","Anyang","Siheung","Anyang","Gwangmyeong",
                "Anyang","Gunpo","Anyang","Gwacheon","Siheung","Gwangmyeong",
                "Siheung","Gunpo","Pohang","Yeongcheon","Pohang","Gyeongju",
                "Jeju","Gimpo","Jeju","Mokpo","Jeju","Seogwipo","Uijeongbu",
                "Yangju","Uijeongbu","Pocheon","Paju","Yangju","Gumi","Gimcheon",
                "Gumi","Sangju","Gwangju-si","Hanam","Gwangju-si","Icheon",
                "Gwangju-si","Yeoju","Sejong","Gongju","Wonju","Chungju",
                "Wonju","Jecheon","Wonju","Yeoju","Jinju","Sacheon", "Yangsan",
                "Miryang","Asan","Gongju","Iksan","Gunsan","Iksan","Nonsan",
                "Iksan","Gimje","Chuncheon","Pocheon","Gyeongsan","Yeongcheon",
                "Gunpo","Uiwang","Suncheon","Yeosu","Suncheon","Gwangyang",
                "Gunsan","Gimje","Gyeongju","Yeongcheon","Geoje","Tongyeong",
                "Osan","Anseong","Yangju","Pocheon","Yangju","Dongducheon",
                "Icheon","Anseong","Icheon","Yeoju","Mokpo","Naju","Chungju",
                "Jecheon","Chungju","Yeoju","Chungju","Mungyeong","Gangneung",
                "Donghae","Gangneung","Sokcho","Seosan","Dangjin","Andong",
                "Yeongju","Pocheon","Dongducheon","Gimcheon","Sangju","Tongyeong",
                "Sacheon","Nonsan","Gongju","Nonsan","Boryeong","Nonsan",
                "Gyeryong","Gongju","Boryeong","Gongju","Gyeryong","Jeongeup",
                "Gimje","Yeongju","Mungyeong","Yeongju","Taebaek","Sangju",
                "Mungyeong","Sokcho","Samcheok","Samcheok","Taebaek",
                "Suncheon","Gwangju"), directed=F)
  
  E(g1)$distance <- c(27, 16, 20, 19, 20, 24, 14, 20, 15, 15, 36, 18, 299, 18, 53,
                      25, 8, 12, 440, 18, 36, 13, 33, 33, 31, 26, 15, 20, 13, 20,
                      19, 18, 13, 16, 10, 33, 36, 51, 24, 31, 28, 21, 23, 27, 22,
                      11, 12, 24, 18, 52, 27, 11, 13, 19, 13, 14, 34, 20, 23, 38,
                      18, 12, 9, 12, 7, 10, 19, 53, 11, 8, 20, 27, 11, 26, 24, 18,
                      33, 25, 18, 15, 44, 14, 12, 4, 5, 12, 12, 37, 21, 458, 146,
                      27, 10, 23, 24, 21, 36, 14, 23, 36, 21, 39, 33, 26, 20, 32, 
                      40, 20, 29, 18, 47, 24, 4, 27, 19, 22, 29, 17, 24, 18, 13, 
                      32, 18, 37, 28, 43, 51, 33, 56, 20, 28, 12, 30, 38, 29, 47,
                      17, 47, 22, 26, 46, 51, 20, 10, 36,63)
  
  # 优化后的绘图
  plot(g1,
       layout = layout_with_kk(g1),
       vertex.color = ifelse(V(g1)$name == "Seoul", "#FF4500", "#1E90FF"),
       vertex.size = ifelse(V(g1)$name == "Seoul", 10, 5),
       vertex.label.cex = 0.7,
       vertex.label.color = "black",
       edge.color = adjustcolor("gray80", alpha.f = 0.6),
       edge.width = E(g1)$distance / 10,
       edge.curved = 0.1,
       edge.label = ifelse(E(g1)$distance > 20, E(g1)$distance, NA),
       edge.label.cex = 0.5,
       edge.label.color = "darkred",
       margin = c(0,0,0,0)
  )
  

二、遍历所有城市的最短闭合路径求解（类TSP问题） #

你的需求是从Seoul出发遍历所有城市并返回，允许重复访问，可通过以下步骤实现：

核心思路 #

1. 先计算所有城市对之间的最短路径距离，将原图转换为完全图（任意两城市间都有直达的最短路径）；
2. 使用TSP算法求解完全图的最短闭合路径，自动处理需要重复访问城市的情况。

实现代码（使用TSP包） #

# 安装依赖包
install.packages(c("igraph", "TSP"))
library(igraph)
library(TSP)

# 1. 计算所有城市对的最短路径距离矩阵
city_names <- V(g1)$name
dist_matrix <- shortest.paths(g1, weights = E(g1)$distance, mode = "all")

# 2. 构建TSP对象并求解
# 插入dummy节点处理闭合路径要求
tsp_obj <- TSP(dist_matrix)
tsp_obj <- insert_dummy(tsp_obj, label = "dummy")

# 用任意插入法求解，起始点设为Seoul
order_tsp <- solve_TSP(tsp_obj, method = "arbitrary_insertion", start = which(city_names == "Seoul"))

# 3. 提取并整理路径
# 去掉dummy节点，补充返回Seoul形成闭合路径
path <- city_names[order_tsp][order_tsp != "dummy"]
final_path <- c(path, "Seoul")

# 计算总距离
total_distance <- sum(dist_matrix[cbind(final_path[-length(final_path)], final_path[-1])])

# 输出结果
cat("最短闭合路径：\n", paste(final_path, collapse = " -> "), "\n\n")
cat("总距离：", total_distance, "\n")

说明 #

• 若需要更精确的结果，可安装concorde包（需依赖外部Concorde求解器），将solve_TSP的method参数设为"concorde"；
• 算法返回的路径会自动包含必要的重复访问城市，以保证遍历所有节点的总距离最短。

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