AI 助理
备案控制台
开发者社区 人工智能 文章 正文

【高阶数据结构】图 -- 详解（下）

2024-05-22 51
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【高阶数据结构】图 -- 详解（下）

【高阶数据结构】图 -- 详解（上）https://developer.aliyun.com/article/1515768?spm=a2c6h.13148508.setting.28.11104f0e63xoTy

四、最小生成树

最小生成树：构成生成树的所有边加起来的权值是最小的（最小成本让这 n 个点相连）。

连通图中的每一棵生成树，都是原图的一个极大无环子图，即：从其中删去任何一条边，生成树就不再连通；反之，在其中引入任何一条新边，都会形成一条回路。

若连通图由 n 个顶点组成，则其生成树必含 n 个顶点和 n-1 条边。因此构造最小生成树的准则有三条：

  1. 只能使用图中权值最小的边来构造最小生成树。
  2. 只能使用恰好 n-1 条边来连接图中的 n 个顶点。
  3. 选用的 n-1 条边不能构成回路。

构造最小生成树的方法： Kruskal 算法和 Prim 算法。这两个算法都采用了逐步求解的 贪心 策略。

贪心算法：是指在问题求解时，总是做出当前看起来最好的选择。也就是说贪心算法做出的不是

整体最优的的选择，而是某种意义上的 局部最优解 。贪心算法不是对所有的问题都能得到整体最优解。

1、Kruskal 算法

任给一个有 n 个顶点的连通网络 N={V, E}，首先构造一个由这 n 个顶点组成、不含任何边的图 G={V, NULL}，其中每个顶点自成一个连通分量，其次不断从 E 中取出权值最小的一条边（若有多条任取其一），若该边的两个顶点来自不同的连通分量，则将此边加入到 G 中。如此重复，直到所有顶点在同一个连通分量上为止。

核心：每次迭代时，选出一条具有最小权值，且两端点不在同一连通分量上的边，加入生成树。

struct Edge
{
  size_t _srci;
  size_t _dsti;
  W _w;
 
  Edge(size_t srci, size_t dsti, const W& w)
    : _srci(srci)
    , _dsti(dsti)
    , _w(w)
  {}
 
  bool operator>(const Edge& e) const
  {
    return _w > e._w;
  }
};
 
W Kruskal(Self& minTree)
{
  size_t n = _vertexs.size();
 
  minTree._vertexs = _vertexs;
  minTree._indexMap = _indexMap;
  minTree._matrix.resize(n);
  for (size_t i = 0; i < n; i++)
  {
    minTree._matrix[i].resize(n, MAX_W);
  }
 
  priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
  for (size_t i = 0; i < n; i++)
  {
    for (size_t j = 0; j < n; j++)
    {
      if (i < j && _matrix[i][j] != MAX_W)
      {
        minque.push(Edge(i, j, _matrix[i][j]));
      }
    }
  }
      
  // 选出n-1条边
  int size = 0;
  W totalW = W();
  UnionFindSet ufs(n);
  while (!minque.empty())
  {
    Edge min = minque.top();
    minque.pop();
 
    if (!ufs.InSet(min._srci, min._dsti))
    {
      cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
      minTree._AddEdge(min._srci, min._dsti, min._w);
      ufs.Union(min._srci, min._dsti);
      size++;
      totalW += min._w;
    }
    else
    {
      cout << "构成环：";
      cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
    }
  }
  if (size == n - 1) return totalW;
  else return W();
}
 
void TestGraphMinTree()
{
  const char* str = "abcdefghi";
  Graph<char, int> g(str, strlen(str));
  g.AddEdge('a', 'b', 4);
  g.AddEdge('a', 'h', 8);
  //g.AddEdge('a', 'h', 9);
  g.AddEdge('b', 'c', 8);
  g.AddEdge('b', 'h', 11);
  g.AddEdge('c', 'i', 2);
  g.AddEdge('c', 'f', 4);
  g.AddEdge('c', 'd', 7);
  g.AddEdge('d', 'f', 14);
  g.AddEdge('d', 'e', 9);
  g.AddEdge('e', 'f', 10);
  g.AddEdge('f', 'g', 2);
  g.AddEdge('g', 'h', 1);
  g.AddEdge('g', 'i', 6);
  g.AddEdge('h', 'i', 7);
 
  Graph<char, int> kminTree;
  cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
  kminTree.Print();
}

void Print()
{
  // 打印顶点和下标的映射关系
  // 打印顶点
  for (size_t i = 0; i < _vertexs.size(); i++)
  {
    cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
  }
  cout << endl;
 
  // 打印矩阵
  // 打印横下标
  cout << "  ";
  for (size_t i = 0; i < _vertexs.size(); i++)
  {
    //cout << i << ' ';
    printf("%4d", i);
  }
  cout << endl;
 
  for (size_t i = 0; i < _matrix.size(); i++)
  {
    cout << i << ' '; //打印竖下标
    for (size_t j = 0; j < _matrix[i].size(); j++)
    {
      //cout << _matrix[i][j] << ' ';
      if (_matrix[i][j] == MAX_W)
      {
        //cout << "* ";
        printf("%4c", '*');
      }
      else
      {
        //cout << _matrix[i][j] << ' ';
        printf("%4d", _matrix[i][j]);
      }
    }
    cout << endl;
  }
  cout << endl;
  for (size_t i = 0; i < _matrix.size(); i++)
  {
    for (size_t j = 0; j < _matrix[i].size(); j++)
    {
      if (i < j && _matrix[i][j] != MAX_W)
      {
        cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
      }
    }
  }
}

2、Prim 算法

W Prim(Self& minTree, const W& src)
{
  size_t srci = GetVertexIndex(src);
  size_t n = _vertexs.size();
 
  minTree._vertexs = _vertexs;
  minTree._indexMap = _indexMap;
  minTree._matrix.resize(n);
  for (size_t i = 0; i < n; ++i)
  {
    minTree._matrix[i].resize(n, MAX_W);
  }
 
  vector<bool> X(n, false);
  vector<bool> Y(n, true);
  X[srci] = true;
  Y[srci] = false;
 
  // 从X->Y集合中连接的边里面选出最小的边
  priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
  // 先把srci连接的边添加到队列中
  for (size_t i = 0; i < n; ++i)
  {
    if (_matrix[srci][i] != MAX_W)
    {
      minq.push(Edge(srci, i, _matrix[srci][i]));
    }
  }
 
  cout << "Prim开始选边" << endl;
  size_t size = 0;
  W totalW = W();
  while (!minq.empty())
  {
    Edge min = minq.top();
    minq.pop();
 
    // 最小边的目标点也在X集合，则构成环
    if (X[min._dsti])
    {
      //cout << "构成环:";
      //cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
    }
    else
    {
      minTree._AddEdge(min._srci, min._dsti, min._w);
      //cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
      X[min._dsti] = true;
      Y[min._dsti] = false;
      size++;
      totalW += min._w;
      if (size == n - 1)
        break;
 
      for (size_t i = 0; i < n; ++i)
      {
        if (_matrix[min._dsti][i] != MAX_W && Y[i])
        {
          minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
        }
      }
    }
  }
 
  if (size == n - 1)
  {
    return totalW;
  }
  else
  {
    return W();
  }
}
 
void TestGraphMinTree()
{
  const char* str = "abcdefghi";
  Graph<char, int> g(str, strlen(str));
  g.AddEdge('a', 'b', 4);
  g.AddEdge('a', 'h', 8);
  //g.AddEdge('a', 'h', 9);
  g.AddEdge('b', 'c', 8);
  g.AddEdge('b', 'h', 11);
  g.AddEdge('c', 'i', 2);
  g.AddEdge('c', 'f', 4);
  g.AddEdge('c', 'd', 7);
  g.AddEdge('d', 'f', 14);
  g.AddEdge('d', 'e', 9);
  g.AddEdge('e', 'f', 10);
  g.AddEdge('f', 'g', 2);
  g.AddEdge('g', 'h', 1);
  g.AddEdge('g', 'i', 6);
  g.AddEdge('h', 'i', 7);
 
  Graph<char, int> pminTree;
  cout << "Prim:" << g.Prim(pminTree, 'a') << endl;
  pminTree.Print();
  cout << endl;
 
  for (size_t i = 0; i < strlen(str); ++i)
  {
    cout << "Prim:" << g.Prim(pminTree, str[i]) << endl;
  }
}

五、最短路径

最短路径问题：从在带权有向图 G 中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是沿路径各边的权值总和达到最小。

1、单源最短路径 —— Dijkstra 算法

单源最短路径问题：给定一个图 G=(V, E)，求源结点 s ∈ V 到图中每个结点 v∈V 的最短路径。

Dijkstra 算法就适用于解决带权重的有向图上的单源最短路径问题，同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点，所以使用 Dijkstra 算法求解过后也就得到了所需起点到终点的最短路径。

针对一个带权有向图 G，将所有结点分为两组 S 和 Q，S 是已经确定最短路径的结点集合，在初始时为空（初始时就可以将源节点 s 放入，毕竟源节点到自己的代价是 0），Q 为其余未确定最短路径的结点集合，每次从 Q 中找出一个起点到该结点代价最小的结点 u ，将 u 从 Q 中移出，并放入 S 中，对 u 的每一个相邻结点 v 进行松弛操作。松弛即对每一个相邻结点 v ，判断源节点 s 到结点 u 的代价与 u 到 v 的代价之和是否比原来 s 到 v 的代价更小，若代价比原来小则要将 s 到 v 的代价更新为 s 到 u 与 u 到 v 的代价之和，否则维持原样。如此一直循环直至集合 Q 为空，即所有节点都已经查找过一遍并确定了最短路径，至于一些起点到达不了的结点在算法循环后其代价仍为初始设定的值，不发生变化。Dijkstra 算法每次都是选择 V-S 中最小的路径节点来进行更新，并加入 S 中，所以该算法使用的是贪心策略。

Dijkstra 算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径。

void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
{
  size_t srci = GetVertexIndex(src);
  size_t n = _vertexs.size();
    dist.resize(n, MAX_W);
  pPath.resize(n, -1);
 
  dist[srci] = 0;
  pPath[srci] = srci;
 
  // 已经确定最短路径的顶点集合
  vector<bool> S(n, false);
 
  for (size_t j = 0; j < n; ++j)
  {
    // 选最短路径顶点且不在S更新其他路径
    int u = 0;
    W min = MAX_W;
    for (size_t i = 0; i < n; ++i)
    {
      if (S[i] == false && dist[i] < min)
      {
        u = i;
        min = dist[i];
      }
    }
 
    S[u] = true;
    // 松弛更新u连接顶点v  srci->u + u->v <  srci->v  更新
    for (size_t v = 0; v < n; ++v)
    {
      if (_matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v])
      {
        dist[v] = dist[u] + _matrix[u][v];
        pPath[v] = u;
      }
    }
  }
}
 
void TestGraphDijkstra()
{
  const char* str = "syztx";
  Graph<char, int, INT_MAX, true> g(str, strlen(str));
  g.AddEdge('s', 't', 10);
  g.AddEdge('s', 'y', 5);
  g.AddEdge('y', 't', 3);
  g.AddEdge('y', 'x', 9);
  g.AddEdge('y', 'z', 2);
  g.AddEdge('z', 's', 7);
  g.AddEdge('z', 'x', 6);
  g.AddEdge('t', 'y', 2);
  g.AddEdge('t', 'x', 1);
  g.AddEdge('x', 'z', 4);
 
  vector<int> dist;
  vector<int> parentPath;
  g.Dijkstra('s', dist, parentPath);
  g.PrintShortPath('s', dist, parentPath);
}

void TestGraphDijkstra()
{
    const char* str = "sytx";
  Graph<char, int, INT_MAX, true> g(str, strlen(str));
  g.AddEdge('s', 't', 10);
  g.AddEdge('s', 'y', 5);
  g.AddEdge('t', 'y', -7);
  g.AddEdge('y', 'x', 3);
  vector<int> dist;
  vector<int> parentPath;
  g.Dijkstra('s', dist, parentPath);
    g.PrintShortPath('s', dist, parentPath);
}

图中带有负权路径时，上面的贪心策略就失效了，从测试结果可以看到 s->t->y 之间的最短路径没更新出来：

修改代码如下：

2、单源最短路径 —— Bellman-Ford 算法

Dijkstra 算法只能用来解决正权图的单源最短路径问题，但有些题目会出现负权图。这时这个算法就不能帮助我们解决问题了，而 Bellman—ford 算法 可以解决负权图的单源最短路径问题。

它的优点是可以解决有负权边的单源最短路径问题，而且可以用来判断是否有负权回路。它也有明显的缺点，它的时间复杂度 O(N*E)（N 是点数，E 是边数）普遍是要高于 Dijkstra 算法 O(N²) 的。像这里如果我们使用邻接矩阵实现，那么遍历所有边的数量的时间复杂度就是 O(N^3)，这里也可以看出来 Bellman-Ford 就是一种暴力求解更新。

bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
{
  size_t n = _vertexs.size();
  size_t srci = GetVertexIndex(src);
 
  // vector<W> dist,记录srci-其他顶点最短路径权值数组
  dist.resize(n, MAX_W);
 
  // vector<int> pPath 记录srci-其他顶点最短路径父顶点数组
  pPath.resize(n, -1);
 
  // 先更新srci->srci为缺省值
  dist[srci] = W();
 
  //cout << "更新边：i->j" << endl;
 
  // 总体最多更新n轮
  for (size_t k = 0; k < n; ++k)
  {
    // i->j 更新松弛
    bool update = false;
    cout << "更新第:" << k << "轮" << endl;
    for (size_t i = 0; i < n; ++i)
    {
      for (size_t j = 0; j < n; ++j)
      {
        // srci->i + i->j
        if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
        {
          update = true;
          cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
          dist[j] = dist[i] + _matrix[i][j];
          pPath[j] = i;
        }
      }
    }
    // 如果这个轮次中没有更新出更短路径，那么后续轮次就不需要再走了
    if (update == false)
      break;
  }
 
  // 还能更新就是带负权回路
  for (size_t i = 0; i < n; ++i)
  {
    for (size_t j = 0; j < n; ++j)
    {
      // srci->i + i->j
      if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
      {
        return false;
      }
    }
  }
  return true;
}
 
void TestGraphBellmanFord1()
{
  const char* str = "syztx";
  Graph<char, int, INT_MAX, true> g(str, strlen(str));
  g.AddEdge('s', 't', 6);
  g.AddEdge('s', 'y', 7);
  g.AddEdge('y', 'z', 9);
  g.AddEdge('y', 'x', -3);
  g.AddEdge('z', 's', 2);
  g.AddEdge('z', 'x', 7);
  g.AddEdge('t', 'x', 5);
  g.AddEdge('t', 'y', 8);
  g.AddEdge('t', 'z', -4);
  g.AddEdge('x', 't', -2);
  vector<int> dist;
  vector<int> parentPath;
  if (g.BellmanFord('s', dist, parentPath))
    g.PrintShortPath('s', dist, parentPath);
  else
    cout << "存在负权回路" << endl;
}
 
void TestGraphBellmanFord2()
{
  const char* str = "syztx";
  Graph<char, int, INT_MAX, true> g(str, strlen(str));
  g.AddEdge('s', 't', 6);
  g.AddEdge('s', 'y', 7);
  g.AddEdge('y', 'z', 9);
  g.AddEdge('y', 'x', -3);
  g.AddEdge('y', 's', 1); // 新增
  g.AddEdge('z', 's', 2);
  g.AddEdge('z', 'x', 7);
  g.AddEdge('t', 'x', 5);
  g.AddEdge('t', 'y', -8); // 更改
  g.AddEdge('t', 'z', -4);
  g.AddEdge('x', 't', -2);
  vector<int> dist;
  vector<int> parentPath;
  if (g.BellmanFord('s', dist, parentPath))
    g.PrintShortPath('s', dist, parentPath);
  else
    cout << "存在负权回路" << endl;
}

3、多源最短路径 —— Floyd-Warshall 算法

Floyd-Warshall 算法是解决任意两点间的最短路径的一种算法。

Floyd 算法考虑的是一条最短路径的中间节点，即简单路径 p={v1, v2, …, vn} 上除 v1 和 vn 的任意节点。设 k 是 p 的一个中间节点，那么从i到j的最短路径 p 就被分成 i 到 k 和 k 到 j 的两段最短路径 p1，p2。p1 是从 i 到 k 且中间节点属于 {1, 2, …, k-1} 取得的一条最短路径。p2 是从 k 到 j 且中间节点属于 {1, 2, …, k-1} 取得的一条最短路径。

即 Floyd 算法本质是三维动态规划，D[i][j][k] 表示从点 i 到点 j 只经过 0 到 k 个点最短路径，然后建立起转移方程，然后通过空间优化，优化掉最后一维度，变成一个最短路径的迭代算法，最后即得到所以点的最短路。

void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
{
  size_t n = _vertexs.size();
  vvDist.resize(n);
  vvpPath.resize(n);
 
  // 初始化权值和路径矩阵
  for (size_t i = 0; i < n; ++i)
  {
    vvDist[i].resize(n, MAX_W);
    vvpPath[i].resize(n, -1);
  }
 
  // 直接相连的边更新一下
  for (size_t i = 0; i < n; ++i)
  {
    for (size_t j = 0; j < n; ++j)
    {
      if (_matrix[i][j] != MAX_W)
      {
        vvDist[i][j] = _matrix[i][j];
        vvpPath[i][j] = i;
      }
      if (i == j)
      {
        vvDist[i][j] = W();
      }
    }
  }
 
  // abcdef  a {} f ||  b {} c
  // 最短路径的更新：i-> {其他顶点} ->j
  for (size_t k = 0; k < n; ++k)
  {
    for (size_t i = 0; i < n; ++i)
    {
      for (size_t j = 0; j < n; ++j)
      {
        // k 作为的中间点尝试去更新i->j的路径
        if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W && vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
        {
          vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
 
          // 要找的是跟j相连的上一个邻接顶点
          // 如果 k->j 直接相连，上一个点就是k，那么vvpPath[k][j]存的就是k
          // 如果 k->j 没有直接相连（k->...->x->j），vvpPath[k][j]存的就是x
          vvpPath[i][j] = vvpPath[k][j];
        }
      }
    }
 
    // 打印权值和路径矩阵观察数据
    for (size_t i = 0; i < n; ++i)
    {
      for (size_t j = 0; j < n; ++j)
      {
        if (vvDist[i][j] == MAX_W)
        {
          //cout << "*" << " ";
          printf("%3c", '*');
        }
        else
        {
          //cout << vvDist[i][j] << " ";
          printf("%3d", vvDist[i][j]);
        }
      }
      cout << endl;
    }
    cout << endl;
 
    for (size_t i = 0; i < n; ++i)
    {
      for (size_t j = 0; j < n; ++j)
      {
        //cout << vvParentPath[i][j] << " ";
        printf("%3d", vvpPath[i][j]);
      }
      cout << endl;
    }
    cout << "=================================" << endl;
  }
}
 
void TestFloydWarShall()
{
  const char* str = "12345";
  Graph<char, int, INT_MAX, true> g(str, strlen(str));
  g.AddEdge('1', '2', 3);
  g.AddEdge('1', '3', 8);
  g.AddEdge('1', '5', -4);
  g.AddEdge('2', '4', 1);
  g.AddEdge('2', '5', 7);
  g.AddEdge('3', '2', 4);
  g.AddEdge('4', '1', 2);
  g.AddEdge('4', '3', -5);
  g.AddEdge('5', '4', 6);
  vector<vector<int>> vvDist;
  vector<vector<int>> vvParentPath;
  g.FloydWarshall(vvDist, vvParentPath);
 
  // 打印任意两点之间的最短路径
  for (size_t i = 0; i < strlen(str); ++i)
  {
    g.PrintShortPath(str[i], vvDist[i], vvParentPath[i]);
    cout << endl;
  }
}


文章标签：
算法
关键词：
数据结构图
数据结构高阶
高阶数据结构图
炫酷的伊莉娜
目录
相关文章
1897697198172439
|
6月前
|
存储 算法
数据结构===图
数据结构===图
1897697198172439
35 0
龙大吉
|
5月前
|
算法 Python
逆袭之路！用 Python 玩转图的 DFS 与 BFS，让数据结构难题无处遁形
【7月更文挑战第12天】图的遍历利器：DFS 和 BFS。Python 中，图可表示为邻接表或矩阵。DFS 沿路径深入，回溯时遍历所有可达顶点，适合找路径和环。BFS 层次遍历，先近后远，解决最短路径问题。两者在迷宫、网络路由等场景各显神通。通过练习，掌握这些算法，图处理将游刃有余。
龙大吉
65 3
众所周知
|
5月前
|
存储 算法 Python
“解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系，通过节点和边连接。常见的表示方法是邻接矩阵（适合稠密图）和邻接表（适合稀疏图）。图遍历包括DFS（深度优先搜索）和BFS（广度优先搜索）：DFS深入探索分支，BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
众所周知
45 1
Eternity._
|
5月前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set：高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set：高效数据结构的奥秘与技巧
Eternity._
64 0
东洛的克莱斯韦克
|
5月前
|
存储 Linux 数据库
【数据结构】二叉搜索树——高阶数据结构的敲门砖
【数据结构】二叉搜索树——高阶数据结构的敲门砖
东洛的克莱斯韦克
26 0
sky_qiyi
|
6月前
|
存储
数据结构学习记录——如何建立图（邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立）
数据结构学习记录——如何建立图（邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立）
sky_qiyi
82 0
sky_qiyi
|
6月前
|
存储 算法
数据结构学习记录——图应用实例-六度空间（题目描述、算法思路、伪代码及解读、图解）
数据结构学习记录——图应用实例-六度空间（题目描述、算法思路、伪代码及解读、图解）
sky_qiyi
61 0
sky_qiyi
|
6月前
|
存储 算法 安全
数据结构学习记录——图应用实例-拯救007（问题描述、解题思路、伪代码解读、C语言算法实现）
数据结构学习记录——图应用实例-拯救007（问题描述、解题思路、伪代码解读、C语言算法实现）
sky_qiyi
43 0
sky_qiyi
|
6月前
|
存储 C语言
数据结构学习记录——图的遍历（深度优先搜索、广度优先搜索、为什么需要两种遍历、图不连通怎么办）
数据结构学习记录——图的遍历（深度优先搜索、广度优先搜索、为什么需要两种遍历、图不连通怎么办）
sky_qiyi
66 0
sky_qiyi
|
6月前
|
存储 机器学习/深度学习
数据结构学习记录——什么是图（抽象数据类型定义、常见术语、邻接矩阵表示法、邻接表表示法）
数据结构学习记录——什么是图（抽象数据类型定义、常见术语、邻接矩阵表示法、邻接表表示法）
sky_qiyi
66 0