度到社交圖

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>不這樣做。這裏的元素可以分散在內存中的不同位置。 （簡體）它的價值和存儲指向前一個和下一個元素的指針。