列出两个给定朋友之间的所有 link 个朋友

Question

据说所有人之间平均只有六个或更少的社交关系。创建一个应用程序，帮助您找到任意两个人之间的分离程度。将其视为 select 在 Facebook 上访问两个用户并试图了解这两个人的情况已连接。

如果你 select 任何两个人，你应该能够看到它们之间的分离程度。例如，如果您在系统中添加了以下关系...

Sameer 是 Aayushi 的朋友
Aayushi 是 Bhaskar 的朋友
Sameer 是 Kamalnath Sharma 的朋友
Kamalnath Sharma 是 Shanti Kumar Saha 的朋友
Shanti Kumar Saha 是 Bhaskar 的朋友

如果你 select 两个人，比方说 Sameer 和 Bhaskar，应用程序应该显示学位分离如下。

Sameer > Aayushi > Bhaskar
Sameet > Kamalnath Sharma > Shanti Kumar Saha > Bhaskar

我必须在 Node.js 应用程序中实现这个逻辑！我尝试了使用图形链接列表的不同方法，但找不到实现此方法的解决方案。

Answer 1

我使用了递归我尝试了 DFS 但我无法实现它
我在基本 JSON 中获取数据并在旅途中更新它，因为如果问题没有指定你的目标值将在 6 个朋友连接下，这个函数可以处于无限循环中。

[
  {
    "name": "samer",
    "friends": ["aayushi", "kamalnath"]
  },
  {
    "name": "aayushi",
    "friends": ["bhaskar"]
  },
  {
    "name": "kamalnath",
    "friends": ["shanti"]
  },
  {
    "name": "shanti",
    "friends": ["bhaskar"]
  }
]

function find(value1,value2,path){
if(count > 6)
  while(true){
  for(var i in Data){
   if(Data[i].name == value1){
     for(var j in Data[i].friends){
        if(Data[i].friends[j] == value2){
            path.push(Data[i].friends[j])
            break;
           }
        else{
            find(Data[i].friends[j],value2,path)
           }
        }
      }
    }
  }
}}

var path = [];
find("samer","bhaskar",path,6)

//Output --> [[aayushi],[kamalnath,shanti]]

Answer 2

阅读您 post 的答案（将来您可能只需编辑 post），您几乎明白了。您可以通过将 JSON 预处理为邻接列表图来提高 DFS 的效率，并且可以通过跟踪您之前访问过的朋友来避免无限循环（这样您就不会多次访问他们并循环无限循环）。

邻接表 Graph 只是 Graph 的一种表示，您在对象中将顶点列表作为键存储，并将它们相邻（连接）的所有其他顶点的列表作为值存储。例如，Graph 会将键 "sameer" 映射到列表 ["aayushi", "kamalnath"]。这样一来，每次调用 find 时，就不必遍历所有 Data 来查找 value1。你可以通过 Graph[value1] 找到 value1 的朋友。（为了清楚起见，我在下面的代码中将 value1 重命名为 source，将 value2 重命名为 target 以及其他一些变量名称更改。

至于避免循环，您可以在一个简单的 javascript 对象（或集合）中跟踪您已经访问过的朋友，初始化为空并在您访问每个新朋友时添加到递归调用，然后只需将此对象传递给每个递归调用。您在每次调用开始时检查它以确保您没有进入循环。这对于您在树上执行的 DFS/BFS 搜索（根据定义是非循环图）不是必需的，但对于可能具有 loops/cycles.

的一般图来说是必需的

另一件小事是，当您找到目标时 value/friend，您

if(Data[i].friends[j] == value2){
  path.push(Data[i].friends[j])
  break;
}

在这种情况下你不递归是对的，但如果你想继续搜索你正在循环的其他朋友的替代路径（而不仅仅是打破并返回你找到的第一条路径）。

此外，我不确定这是否是故意的，但在示例数据中，友谊似乎是单向的（例如，shanti 是 bhaskar 的朋友，但 bhaskar 没有列出朋友）。如果它们是 2 种方式，您可能会稍微更改将连接列表预处理为图形的方式。无论如何，这是包含我提到的所有更改的代码。如果不清楚请告诉我：

// preprocess a JSON list of connections to an adjacency list Graph
function connectionsListToGraph(connections) {
  const Graph = {}
  for (let { name, friends } of connections) {
    Graph[name] = friends // allow fast lookup of a given person's friends
  }
  return Graph
}

// return the list of connections between source and target
function getConnections(source, target, connections) {

  const Graph = connectionsListToGraph(connections)
  const connectionPaths = []

  function findConnectionsDFS(source, target, path = [source], visited = {}) {
    // Don't search/visit the same friend twice (to avoid infinite loops)
    if (visited[source]) return; 

    // mark that we've searched the current source friend
    visited[source] = true; 

    for (let friend of Graph[source]) {
      if (friend === target) {
        connectionPaths.push(path.concat(target));
      } else {
        findConnectionsDFS(friend, target, path.concat(friend), visited)
      }
    }
  }
  findConnectionsDFS(source, target);
  return connectionPaths;
}

let connections = [
  {
    "name": "sameer",
    "friends": ["aayushi", "kamalnath"]
  },
  {
    "name": "aayushi",
    "friends": ["bhaskar"]
  },
  {
    "name": "kamalnath",
    "friends": ["shanti"]
  },
  {
    "name": "shanti",
    "friends": ["bhaskar"]
  }
]

console.log('Sameer to Bhaskar:', getConnections('sameer', 'bhaskar', connections))
console.log('Kamalnath to Bhaskar:', getConnections('kamalnath', 'bhaskar', connections))

列出两个给定朋友之间的所有 link 个朋友

List all link of friends between two given Friends

javascript

tree

graph

node.js