3

请原谅我的笨拙，但我在尝试理解以下内容时遇到了麻烦：

class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // A dynamic array of adjacency lists
    void bridgeUtil(int v, bool visited[], int disc[], int low[], int parent[]);

  public:
    Graph(int V);   // Constructor
    void addEdge(int v, int w);   // function to add an edge to graph
    void bridge();    // prints all bridges
};

  Graph::Graph(int V)
  {
      this->V = V;
      adj = new list<int>[V];
  }

  void Graph::addEdge(int v, int w)
  {
     adj[v].push_back(w);
     adj[w].push_back(v);  // Note: the graph is undirected
  }

任何人都可以解释这个数据结构是如何工作的，以及初始化它时会产生什么结果：

  Graph g1(5);
  g1.addEdge(1, 0);
  g1.addEdge(0, 2);
  g1.addEdge(2, 1);
  g1.addEdge(0, 3);
  g1.addEdge(3, 4);

非常感谢！

4

6 回答 6

6

底层数据结构

std::list是一个双向链表，它的行为类似于std::vector除了向量基本上是一个动态数组管理系统。

图表

创建图表时，您指定图表将拥有的节点总数。每个节点都有自己的列表。

当您调用该函数add_edge时，它会在 index 处获取节点（这是一个列表）v。然后它将数字添加w到该列表中，表示存在从 nodev到 node的链接w。在下一个语句中再次发生相同的情况，但相反。它在 index 处获取列表w并将数字添加v到列表中，表示存在从 nodew到 node的链接v。

正是由于这种性质，我们找到了注释// Note: the graph is undirected，因为它绘制了从两个节点到另一个节点的路径。

结果

由于每个节点都有自己的列表。我们可以随机选择一个，并使用如下函数找到与其相连的所有节点。

list<int> Graph::getNodes(int v)
{
   return(adj[v]);
}

你的代码做什么

//Creates 5 lists, each one representing a node with possible id [0 - 4]
Graph g1(5);       
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);

//Results in 5 lists that look like this
/*
  (NODE) | (NODE) | (NODE) | (NODE) | (NODE)
  adj[0] | adj[1] | adj[2] | adj[3] | adj[4]
---------------------------------------------
    1    |    0   |    0   |    0   |   3
    2    |    2   |    1   |    4   |
    3    |        |        |        |
*/

根据列表，我可以得出结论，从Node 0，我可以到达Nodes 1, 2 and 3

于 2013-08-01T20:13:44.407 回答
2

看看维基百科的文章。简而言之，图由节点和顶点组成。节点是“地方”或“事物”，而顶点是它们之间的连接。您的代码用列表列表表示这一点。列表x包含节点x连接到的所有节点。

您的示例图将如下所示： 在此处输入图像描述

于 2013-08-01T20:13:42.523 回答
1

图是一组节点和节点之间的边。在这里，每个节点都是一个数字。每个节点的边用列表表示（列表中的每个条目都是边另一端的节点）。节点 0 的邻接在邻接数组的列表 0 中。在两个节点之间添加一条边后，您将......在这两个节点之间有一条边。把它画出来可能会有所帮助。您的图表将如下所示：

0--1
|\ |
| \|
3--2
|
4
于 2013-08-01T20:12:50.497 回答
0

每个 Graph 实例中都有固定数量的 std::list。在您的示例中，数组中有 5 个。这个数字不变。

数组中的每个条目都是 int 的双链表。

在 X 和 Y 之间添加一条边会更改两个 std::lists。X 处的数组索引是 X 的节点列表，并将 T 添加到其中。Y 处的数组索引是 Y 的节点列表，并将 X 添加到其中。

如果你想要一个演练......问你的老师，因为这显然是家庭作业。:-)

于 2013-08-01T20:11:19.150 回答
0

它跟踪图形，可能使用邻接图或链表。添加 5 条边后，该图将包含以下顶点：{0, 1, 2, 3, 4} 并且将具有来自 {1-0, 0-2, 2-1, 0-3, 3-4} 的边您在寻找更多细节吗？

我不确定它是如何存储的，但有两种可能的方式是邻接图或链表。

邻接图：

\ 0 1 2 3 4 
0| 0 1 1 1 0 
1| 1 0 1 0 0 
2| 1 1 0 0 0
3| 1 0 0 0 1
4| 0 0 0 1 0

0 表示顶点未连接，1 表示它们已连接。

链表：

0 > 1, 2, 3
1 > 0, 2
2 > 0, 1
3 > 0, 4
4 > 3

这意味着 0 到 1、2 和 3，而 4 只到 3。

于 2013-08-01T20:09:12.913 回答
0 
enter code here

// Program to print BFS traversal from a given 
// source vertex. BFS(int s) traverses vertices 
// reachable from s. 
#include<iostream> 
#include <list> 

using namespace std; class Graph 
    { 
        int V; // No. of vertices 
    
        // Pointer to an array containing adjacency 
        // lists 
        list<int> *adj; 
    public: 
        Graph(int V); // Constructor 
    
        // function to add an edge to graph 
        void addEdge(int v, int w); 
    
        // prints BFS traversal from a given source s 
        void BFS(int s); 
    }; 
    
    Graph::Graph(int V) 
    { 
        this->V = V; 
        adj = new list<int>[V]; 
    } 
    
    void Graph::addEdge(int v, int w) 
    { 
        adj[v].push_back(w); // Add w to v’s list. 
    } 
    
    void Graph::BFS(int s) 
    { 
        // Mark all the vertices as not visited 
        bool *visited = new bool[V]; 
        for(int i = 0; i < V; i++) 
            visited[i] = false; 
    
        // Create a queue for BFS 
        list<int> queue; 
    
        // Mark the current node as visited and enqueue it 
        visited[s] = true; 
        queue.push_back(s); 
    
        // 'i' will be used to get all adjacent 
        // vertices of a vertex 
        list<int>::iterator i; 
    
        while(!queue.empty()) 
        { 
            // Dequeue a vertex from queue and print it 
            s = queue.front(); 
            cout << s << " "; 
            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 
            for (i = adj[s].begin(); i != adj[s].end(); ++i) 
            { 
                if (!visited[*i]) 
                { 
                    visited[*i] = true; 
                    queue.push_back(*i); 
                } 
            } 
        } 
    } 
    
    // Driver program to test methods of graph class 
    int main() 
    { 
        // Create a graph given in the above diagram 
        Graph g(5); 
        g.addEdge(1, 0); 
        g.addEdge(0, 2); 
        g.addEdge(2, 1); 
        g.addEdge(0, 3); 
        g.addEdge(3, 4);
        
    // g.addEdge(3, 3); 
    
        cout << "Following is Breadth First Traversal "
            << "(starting from vertex 2) \n"; 
        g.BFS(2); 
    
        return 0; 
    }
于 2020-09-25T17:54:42.057 回答