度到社交图

Question

我试图找出一个社交图2层的实体之间的连接度，其中

• 1跳2个节点之间的连接：1级，
• 2一跳：第二学位
• 3跳：3度 依此类推。

顶点是实体，边是两个实体之间的友谊。鉴于这样一个图我想分析图并回答查询关于什么是实体之间的连接类型。它可以是断开连接图。如果没有连接，它将返回0.

它需要输入原样

Number_of_vertices Number_of_Edges 
Edge 1 
Edge 2 
(So on.) 

查询

输出

程度连接的

例

Input 

5 4 

Abhs Krax // Edge 1 

Harry Idrina // Edge 2 

Harry Jigma // Edge 3 

Harry Krax // Edge 4 

Abhs Jigma // Query 

输出

Degree : 3 

我使用BFS找出2个节点之间的深度，但我的程序只适用程度1.无法测试一个后续成员的队列因此停留在仅测试队列的第一个成员。我在代码中错过了什么？问题在于我无法追踪的Connection()函数。

#include <iostream> 
#include <list> 
#include <string> 
using namespace std; 

class Vertex // Each vertex of the graph is represented by the object of the Vertex class 
{ 
    public: 
     // Fields in every vertex node 
     string name; 
     std::list<Vertex*> adjacencyList; 
     bool status; 
     int depth; 

     // Constructor which initializes the node 
     Vertex(string id) 
     { 
      name = id; 
      adjacencyList = list<Vertex*>(); 
      status = false; 
      depth =0; 
     } 

     // Function to add edges by pushing the vertices to its adjacency list 
     void addEdge(Vertex *v) 
     { 
      adjacencyList.push_back(v); 
     } 

}; 

class Graph{ 
    public: 
      // Fields of the Graph node 
     int N; 
     std::list<Vertex> vertexList; 

       // Functions to be implemented 

     int Connection(Vertex,Vertex); 


     Graph(int n){ // Constructor 
      N = n; 
      vertexList = list<Vertex>(); 
     } 

       /* This function first checks whether the vertex has been already added 
       to Vertex List of the Graph. If not found it would create the vertex 
      node and push the node into Vertex List. Then the edges are added by 
      updating the adjacency list of respective vertices. */ 
     void addEdge(string to, string from){ 

       if(find(to)) 
      { 
       Vertex entity_1 = Vertex(to); // New vertex node creation 
       vertexList.push_back(entity_1); // Pushing to the Vertex List 
      } 

      if(find(from)) 
      { 
       Vertex entity_2 = Vertex(from); 
       vertexList.push_back(entity_2); 
      } 
      Vertex *v1 = &(*(find_it(to))); 
      Vertex *v2 = &(*(find_it(from))); 

      v1->addEdge(v2); // Updating respective adjacency list 
      v2->addEdge(v1); 

     } 

     // Function to check whether the vertex is already added in the Vertex List 
     int find(string check) 
     {  
      list<Vertex>::iterator it; 
      it = find_it(check); 
      if(it==vertexList.end()) 
       return 1; 
      else 
       return 0; 
     } 

     // Function which returns pointer to a Vertex in the Vertex List 
     list<Vertex>::iterator find_it(string check) 
     { 
      list<Vertex>::iterator it; 
      for (it = vertexList.begin(); it != vertexList.end(); it++) 
       if((check.compare(it->name))==0) 
        break; 

      return it; 
     } 
}; 


int main() 
{ 
    int numVertices,numEdges,i,result; 
    string to,from,querryTo,querryFrom; 

    cin>>numVertices>>numEdges; 

    Graph G = Graph(numVertices); // Creating the Graph object 

    for(i=0;i<numEdges;i++) 
    { 
     cin>>to>>from; 
     G.addEdge(to,from); // Adding Edges to Graph 
    } 

    cin>>querryTo>>querryFrom; 

     // The function you have to write is called here where the address of vertex 
     // node is passed. 


    result = G.Connection((*(G.find_it(querryTo))),(*(G.find_it(querryFrom)))); 

    if(!result) 
     cout<<"No Connection"; 
    else 
     cout<<"Degree : "<<result; 


    return 0; 
} 


int Graph::Connection(Vertex v1,Vertex v2) 
{ 
    // Mark all the vertices as not visited 
    Vertex s=Vertex("xx"); 
    int i=0; 
    //list<Vertex>::iterator it; 
    Vertex *temp=&(*(vertexList.begin())); 
    while(!temp) 
     temp->status = false,++temp; 

    // Create a queue for BFS 
    list<Vertex> queue; 

    // Mark the current node as visited and enqueue it 
    v1.status=true; 
    queue.push_back(v1); 

    // it will be used to get all adjacent vertices of a vertex 
    int depth; 
    while (!queue.empty()) 
    { 
     depth=0; 
     // Dequeue a vertex from queue and print it 
     s = queue.front(); 
     queue.pop_front(); 

     // Get all adjacent vertices of the dequeued vertex s 
     // If a adjacent has not been visited, then mark it visited 
     // and enqueue it 
     temp=s.adjacencyList.front(); 
     while(temp!=NULL) 
     { 
      ++depth; 
      // If this adjacent node is the destination node, then return true 
      if ((v2.name.compare(temp->name))==0) 
      { 
       v2.depth=depth; 
       return v2.depth; 
      } 
      // Else, continue to do BFS 
      if(temp->status==false) 
       { 
        temp->status = true; 
        queue.push_back(*temp); 
       } 
      ++temp; 
     } 
    } 
    return 0; 
} 

Answer 1

我打算假设您尝试计算的连接程度是节点之间的最短路径距离（具有统一的边缘成本）。您可以使用Floyd-Warshall预处理图形并在O（1）时间内回答查询。这很容易实现。

int a[N][N]; /* adjacency matrix where N is max node count */ 

/* build graph here and init distances between distinct nodes to +INFINITY */ 

/* n is number of nodes */ 
for(int k = 0; k < n; k++) 
    for(int i = 0; i < n; i++) 
    for(int j = 0; j < n; j++) 
     dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]); 

要回答查询（x，y），请打印dist [x] [y]。

你BFS解决方案看起来过于复杂。使用vector<in> g[N]来表示您的图形。添加边x->y与g[x].push_back(y)。 BFS看起来像：

queue<int> Q; 
Q.push(s); /* start node */ 

for(int i = 0; i < n; i++) 
{ dist[i] = INFINITY; 
} 

dist[s] = 0; /* distance to s is set to 0 */ 
while(Q.empty() == false) 
{ int x = Q.front(); Q.pop(); 
    for(int i = 0; i < g[x].size(); i++) 
    { int y = g[x][i]; 
     /* process edge x->y */ 
     if(dist[y] == INFINITY) 
     { dist[y] = dist[x] + 1; 
     Q.push(y); 
     } 
    } 
} 

s和任何其他节点之间的距离t是dist [s] [t]。

Answer 2

如果您尝试查找与度数1的连接，则您的代码也会在段错误中崩溃。给定您的图尝试查找“Harry Krax”。

我认为这个错误是使用指针Vertex * temp = temp=s.adjacencyList.front();，后来尝试访问下一个顶点++temp;。

这不是如何std::list结合指针的工作。 如果要使用++temp访问下一个顶点，那么可能需要使用迭代器std::list<x>::iterator temp。

因为数组的元素在内存中相邻，所以您试图执行的操作与int a[N]这样的数组有关。 With int * aptr = a。 ++aptr表示temp将移动到内存中另一个距离较远的int的大小。 std::list<x>不这样做。这里的元素可以分散在内存中的不同位置。 （简体）它的价值和存储指向前一个和下一个元素的指针。