网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
湘中三水又吧 关注：5贴子：697
  • 6回复贴，共1页
隔了好几天没练习算法。毅力和决心沦落至如此，深感忧虑。现在动手也是不情不愿。不过还是希望自己能坚持，把想学的东西都写完。
跨过其他知识点，先学图算法。图的存储结构，常用的有邻接矩阵，邻接表，链式前向星。会邻接表肯定会邻接矩阵，链式前向星和邻接表并无本质的区别，就是开节点，一个动态，一个静态。还是邻接表用着顺手些。因而接下来的图算法都用邻接表做图的存储结构。
1楼2017-12-21 15:31回复
    #define NUM 1000
    #define INF 1<<31-1struct Edge
    {
    　 Edge(int _u,int _v,int _w,Edge* _next)
    　 {
    　 　 u = _u;
    　 　 v = _v;
    　 　 w = _w;
    　 　 next = _next;
    　 }
    　 int u;
    　 int v;
    　 int w;
    　 Edge* next;
    };
    Edge* adj[NUM];
    void Init()
    {
    　 for (int i = 0; i < NUM; ++i) adj[i] = NULL;
    }
    void AddEdge(int _u, int _v, int _w)
    {
    　 adj[_u] = new Edge(_u, _v, _w, adj[_u]);
    }
    void RmoveEdge(int _u, int _v)
    {
    　 Edge** cur = &adj[_u];
    　 while (*cur != NULL)
    　 {
    　 　 if ((*cur)->v == _v)
    　 　 {
    　 　 　 Edge* temp = *cur;
    　 　 　 *cur = (*cur)->next;
    　 　 　 delete temp;
    　 　 　 return;
    　 　 }
    　 　 cur = &(*cur)->next;
    　 }
    }
    2楼2017-12-21 16:12
    收起回复
      vector<bool> visited(NUM,false);
      深度优先遍历
      void DFS(int u, vector<bool>& visited)
      {
      　printf("%d ", u);
      　 visited[u] = true;
      　Edge* cur = adj[u];
      　while (cur != NULL)
      　 {
      　 　 int v = cur->v;
      　 　 if(!visited[v]) DFS(v,visited);
      　 　 cur = cur->next;
      　 }
      }
      广度优先遍历
      void BFS(int u)
      {
      　queue<int> queue;
      　queue.push(u);
      　 visited[u] = true;
      　 while (!queue.empty())
      　 {
      　 　 int temp = queue.front();
      　 　printf("%d ", temp);
      　 　queue.pop();
      　 　Edge* cur = adj[temp];
      　 　 while (cur != NULL)
      　 　 {
      　 　 　 int v = cur->v;
      　 　 　 if (!visited[v])
      　 　 　 {
      　 　 　 　 queue.push(v);
      　 　 　 　 visited[v] = true;
      　 　 　 }
      　 　 　 cur = cur->next;
      　 　}
      　 }
      }
      3楼2017-12-21 16:33
      回复
        经典的深度优先遍历和广度优先遍历。在实际应用中，深度优先用得更广泛。我想这主要是因为深度优先可以采用递归实现，代码更简单易写。不过递归的一大缺点就是递归层数有限制，嵌套多了可能会爆栈。这个时候，就有必要用广度优先来代替了。
        有趣的是，就我的发现来看，深度优先和广度优先是相伴相生的。如果一个问题能用深度优先来解决，则同时存在一个广度优先的解法。反之也成立。可见，深度优先和广度优先是解决问题的两种不同思想。
        4楼2017-12-21 16:42
        回复
          Dijkstra最短路径算法
          vector<bool> visited(NUM,false);
          vector<int> d(NUM,INF);
          vector<int> path(NUM, INF);
          void Dijkstra(int s, int n)
          {
          　 d[s] = 0;
          　 for (int i = 0; i < n; ++i)
          　 {
          　 　 int min = INF;
          　 　 for (int j = 0; j < n; ++j)
          　 　 {
          　 　 　 if (!visited[j] && (INF==min||d[j]<d[min]))
          　 　 　 {
          　 　 　 　 min = j;
          　 　 　 }
          　 　 }
          　 　 visited[min] = true;
          　 　 Edge* cur = adj[min];
          　 　 while (cur != NULL)
          　 　 {
          　 　 　 int v = cur->v;
          　 　 　 int w = cur->w;
          　 　 　 if (!visited[v] && d[min] + w < d[v])
          　 　 　 {
          　 　 　 　 d[v] = d[min] + w;
          　 　 　 　 path[v] = min;
          　 　 　 }
          　 　 　 cur = cur->next;
          　 　 }
          　 }
          }
          5楼2017-12-21 17:39
          回复
            void BellFord(int s, int n)
            {
            　d[s] = 0;
            　 for (int i = 0; i < n; ++i)
            　 {
            　 　 bool check = false;
            　 　 for (int j = 0; j < n; ++j)
            　 　 {
            　 　 　 Edge* cur = adj[j];
            　 　 　 while(cur!=NULL)
            　 　 　 {
            　 　 　 　 int u = cur->u;
            　 　 　 　 int v = cur->v;
            　 　 　 　 int w = cur->w;
            　 　 　 　 if (d[u] != INF&&d[u] + w < d[v])
            　 　 　 　 {
            　 　 　 　 　 d[v] = d[u] + w;
            　 　 　 　 　 path[v] = u;
            　 　 　 　 　 check = true;
            　 　 　 　 }
            　 　 　 　 cur = cur->next;
            　 　 　 }
            　 　 }
            　 　 if (!check) break;
            　 }
            }
            11楼2017-12-21 18:04
            收起回复
              bool SPFA(int s, int n)
              {
              　 vector<bool> inq(n, false);
              　vector<int> visitCnt(n, 0);
              　 queue<int> queue;
              　 d[s] = 0;
              　queue.push(s);
              　 inq[s] = true;
              　 while (!queue.empty())
              　{
              　　 int u = queue.front();
              　　 queue.pop();
              　　 inq[u] = false;
              　　 if (visitCnt[u]++ > n) return false;
              　　 Edge* cur = adj[u];
              　　 while (cur != NULL)
              　　 {
              　　　 int v = cur->v;
              　　　 int w = cur->w;
              　　　 if (d[u] != INF&&d[u] + w < d[v])
              　　　 {
              　　　　 if (!inq[v])
              　　　　 {
              　　　　　 queue.push(v);
              　　　　　 inq[v] = true;
              　　　　}
              　　　　d[v] = d[u] + w;
              　　　　path[v] = u;
              　　　 }
              　　　cur = cur->next;
              　　 }
              　 }
              　return true;
              }
              12楼2017-12-21 18:24
              收起回复

                扫二维码下载贴吧客户端

                下载贴吧APP
                看高清直播、视频！
                • 6回复贴，共1页
                发表回复
                发贴请遵守贴吧协议及“七条底线”贴吧投诉
                内  容:
                  查看全部
                发 表
                保存至快速回贴