数据结构与算法-图的存储，邻接矩阵，邻接表，链式前向星

本文主要是介绍数据结构与算法-图的存储，邻接矩阵，邻接表，链式前向星，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• 条件：无

• 题目：无

• 原理：无

• 代码：

  /**
  * Author: Moota
  * Copyright: Moota
  * Description: Written by Moota  
   */
  #include <iostream>
  #include <iomanip>
  #include <algorithm>  //sort
  #include <map>
  #include <queue>
  #include <deque>  //双端队列，头可插，尾可插
  #include <string>
  #include <cstring>
  #include <stack>
  #include <cmath>
  #include <fstream>
  #include <ctime>
  #include <climits> //数值的限制范围
  //(double)clock() / CLOCKS_PER_SEC <= 0.95 限制0.95s跑完
  using namespace std;
  
  class Solver {
      //通用属性
  public:
      Solver() {
          //取消和c输出输入的同步，加快读取
          ios::sync_with_stdio(false);
          cin.tie(nullptr);
          cout.tie(nullptr);
      }
  
      //通用方法
  public:
      void SaveCpp(string name) const {
  
          fstream input;
          fstream output;
  
          input.open("moota.cpp", ios::in);
          const string file = name + ".cpp";
          output.open(file.c_str(), ios::out);
  
          char c = 'O';
          while (!input.eof()) {
              input.get(c);
              output << c;
          }
  
          input.close();
          output.close();
  
      }
  
  protected:
      //待实现方法
      virtual void BeginPlay() {
  
      };
  
      virtual void Playing() {
      };
  
      virtual void EndPlay() {
      };
  public:
      //外观模式
      void Play() {
          BeginPlay();
          Playing();
          EndPlay();
      }
  };
  
  class SpecialSolver : public Solver {
  public:
      typedef long long lld;
      static const lld MAX = static_cast<lld>(1e4);
      static const lld INF = static_cast<lld>(1e18);
      //实例属性
  private:
      //int map[MAX][MAX]; 邻接矩阵
      /*
      struct Node {  邻接表
          int v;
          int w;
          Node* next;
      } * node[MAX];
  
      int n;
      //邻接表添加节点
      void AddNode(int u, int v, int w) {
          if (node[u] == nullptr) {
              node[u] = new Node{-1, 0, nullptr};
          }
          Node* temp = new Node{v, w, nullptr};
          temp->next = node[u]->next;
          node[u]->next = temp;
      }
  
      //邻接表遍历
      void Order() {
          for (int i = 1; i <= n; ++i) {
              Node* temp = node[i]->next;
              while (temp != nullptr) {
                  cout << i << "-" << temp->v << "-" << temp->w << "\n";
                  temp = temp->next;
              }
          }
      }
      */
      //链式前向星，实际就是邻接表的非链表实现
      int n, m;
      /*
       * @last 前一个 (u相同的) node结构体的下标
       * @vertex u->(不同的) v
       * @weight u->v的权值
      */
      struct Node {
          int last, vertex, weight;
      } node[MAX];
  
      //node结构体的下标
      int cnt = 0;
      //保存最后一个(u,v）node结构体的下标
      int head[MAX];
  
      void AddNode(int u, int v, int w) {
          ++cnt;
          //这里的head[u]是上的一个（u,v）node结构体的下标
          node[cnt] = {head[u], v, w};
          head[u] = cnt;
      }
  
      void Order() {
          /*1 4
          1 2 3
          1 4 5
          1 6 7
          1 8 9
          */
          for (int i = 1; i <= n; ++i) {
              for (int u = head[i]; u != 0; u = node[u].last) {
                  cout << i << "-" << node[u].vertex << "\n";
              }
          }
      }
  
      //实例方法
  private:
  protected:
      virtual void BeginPlay() override {
          Solver::BeginPlay();
          cin >> n >> m;
          int u, v, w;
          while (m--) {
              cin >> u >> v >> w;
              AddNode(u, v, w);
          }
          Order();
      };
  
      virtual void Playing() override {
          Solver::Playing();
  
      };
  
      virtual void EndPlay() override {
          Solver::EndPlay();
      };
  };
  
  SpecialSolver specialSolver;
  
  int main() {
      //注意改名字
      //specialSolver.SaveCpp("图的存储");
      specialSolver.Play();
  }
  
  

这篇关于数据结构与算法-图的存储，邻接矩阵，邻接表，链式前向星的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！