21xrx.com
2024-12-23 00:39:38 Monday
登录
文章检索 我的文章 写文章
C++实现图的邻接表存储和广度优先遍历实例分析
2023-07-03 02:14:41 深夜i     --     --
C++ 邻接表存储 广度优先遍历 实例分析

C++是一门广泛使用的编程语言,在计算机科学中具有重要的地位。其中,C++实现图的邻接表存储和广度优先遍历是其中一个重要的应用领域。

首先,让我们来了解一下图的邻接表存储。图是由若干个结点和结点之间的连接(边)构成的数据结构。邻接表是一种用链表来表示图的存储结构。它的核心思想是将每一个结点的邻居结点都存储在一个链表中,以此来表示图的关系。

接着,我们来看一下广度优先遍历(BFS)的实例分析。BFS是一种图的遍历算法,它是从图的某一个结点出发,访问所有节点的过程。BFS从某个节点开始遍历,先遍历所有邻近的节点,然后再遍历它们的邻近节点,以此类推,直到遍历完整个图。

在C++语言中,我们可以使用vector来作为邻接表的数据结构,以便于实现图的邻接表存储。以下是一个实现20个结点的邻接表示例代码:


#include<iostream>

#include<vector>

using namespace std;

void addEdge(vector<int> adj[], int u, int v) 

  adj[u].push_back(v); 

void BFS(vector<int> adj[], int s) 

  bool visited[20] = {false}; 

  vector<int> queue;

  visited[s] = true; 

  queue.push_back(s); 

  vector<int>::iterator i; 

  while(!queue.empty()) 

  { 

    s = queue.front(); 

    cout << s << " "; 

    queue.erase(queue.begin()); 

    for (i = adj[s].begin(); i != adj[s].end(); ++i) 

    { 

      if (!visited[*i]) 

      { 

        visited[*i] = true; 

        queue.push_back(*i); 

      } 

    } 

  } 

int main() 

  vector<int> adj[20]; 

  addEdge(adj, 0, 1); 

  addEdge(adj, 0, 2); 

  addEdge(adj, 1, 2); 

  addEdge(adj, 2, 0); 

  addEdge(adj, 2, 3); 

  addEdge(adj, 3, 3); 

  cout << "BFS order starting from vertex 2: "; 

  BFS(adj, 2); 

  return 0; 

}

上面的代码中,addEdge函数用于在邻接表中添加两个节点之间的边。BFS函数使用一个bool数组visited来记录访问过的节点,并使用一个vector 来存储要访问的邻近节点。最后,main函数中的代码用来创建一个实例并测试BFS的结果。

上述实现是C++中图的邻接表存储和广度优先遍历的一个简单例子。通过了解和实践,大家可以更好地掌握C++中图的基本概念和算法,从而更好地应用于实际开发中。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复
    相似文章