プログラミング
 Computer >> コンピューター >  >> プログラミング >> プログラミング

隣接リスト表現のためのプリムのMST


これは前のアルゴリズムに似ています。ここでの唯一の違いは、グラフG(V、E)が隣接リストで表されることです。

時間計算量隣接リストの表現はO(E log V)です。

入力と出力

Input:
The cost matrix:
隣接リスト表現のためのプリムのMST 
Output:
Edge: A--B And Cost: 1
Edge: B--E And Cost: 2
Edge: A--C And Cost: 3
Edge: A--D And Cost: 4
Edge: E--F And Cost: 2
Edge: F--G And Cost: 3
Total Cost: 15

アルゴリズム

prims(g: Graph, start)

入力- グラフgと「start」という名前のシード頂点

出力- エッジを追加した後のツリー。

Begin
   create two set B, N
   add the start node in B set.

   for all vertices u in graph g do
      add u in the set N
   done

   while B ≠ N do
      min := ∞
      for all vertices u in graph g do
         if u is in the set B then
            for all vertices v which are adjacent with u do
               if v is in (N – B) then
                  if min > cost of uv edge then
                     min := cost of uv edge
                     parent := u
                     node := v
            done
      done

      insert node in the B set
      add the edge starting from parent to node in the tree
   done

   return the tree
End

#include<iostream>
#include<list>
#include<set>
using namespace std;

typedef struct nodes {
   int dest;
   int cost;
}node;

class Graph {
   int n;
   list<node> *adjList;
   private:
      void showList(int src, list<node> lt) {
         list<node> :: iterator i;
         node tempNode;

         for(i = lt.begin(); i != lt.end(); i++) {
            tempNode = *i;
            cout << "(" << src << ")---("<<tempNode.dest << "|"<<tempNode.cost<<") ";
         }
         cout << endl;
      }

   public:
      Graph() {
         n = 0;
      }

      Graph(int nodeCount) {
         n = nodeCount;
         adjList = new list<node>[n];
      }

      void addEdge(int source, int dest, int cost) {
         node newNode;
         newNode.dest = dest;
         newNode.cost = cost;
         adjList[source].push_back(newNode);
      }

      void displayEdges() {
         for(int i = 0; i<n; i++) {
            list<node> tempList = adjList[i];
            showList(i, tempList);
         }
      }

      friend Graph primsMST(Graph g, int start);
};

set<int> difference(set<int> first, set<int> second) {
   set<int> :: iterator it;
   set<int> res;

   for(it = first.begin(); it != first.end(); it++) {
      if(second.find(*it) == second.end())
         res.insert(*it);    //add those item which are not in the second list
   }

   return res;    //the set (first-second)
}

Graph primsMST(Graph g, int start) {
   int n = g.n;
   set<int> B, N, diff;
   Graph tree(n);        //make tree with same node as graph
   B.insert(start);     //insert start node in the B set

   for(int u = 0; u<n; u++) {
      N.insert(u); //add all vertices in the N set
   }

   while(B != N) {
      int min = 9999;             //set as infinity
      int v, par;
      diff = difference(N, B);    //find the set N - B

      for(int u = 0; u < n; u++) {
         if(B.find(u) != B.end()) {
            list<node>::iterator it;
            for(it = g.adjList[u].begin(); it != g.adjList[u].end(); it++) {
               if(diff.find(it->dest) != diff.end()) {
                  if(min > it->cost) {
                     min = it->cost;    //update cost
                     par = u;
                     v = it->dest;
                  }
               }
            }
         }
      }

      B.insert(v);
      tree.addEdge(par, v, min);
      tree.addEdge(v, par, min);
   }
   return tree;
}

main() {
   Graph g(7), tree(7);
   g.addEdge(0, 1, 1);
   g.addEdge(0, 2, 3);
   g.addEdge(0, 3, 4);
   g.addEdge(0, 5, 5);
   g.addEdge(1, 0, 1);
   g.addEdge(1, 3, 7);
   g.addEdge(1, 4, 2);
   g.addEdge(2, 0, 3);
   g.addEdge(2, 4, 8);
   g.addEdge(3, 0, 4);
   g.addEdge(3, 1, 7);
   g.addEdge(4, 1, 2);
   g.addEdge(4, 2, 8);
   g.addEdge(4, 5, 2);
   g.addEdge(4, 6, 4);
   g.addEdge(5, 0, 5);
   g.addEdge(5, 4, 2);
   g.addEdge(5, 6, 3);
   g.addEdge(6, 4, 4);
   g.addEdge(6, 5, 3);

   tree = primsMST(g, 0);
   tree.displayEdges();
}

出力

Edge: A--B And Cost: 1
Edge: B--E And Cost: 2
Edge: A--C And Cost: 3
Edge: A--D And Cost: 4
Edge: E--F And Cost: 2
Edge: F--G And Cost: 3
Total Cost: 15

  1. 隣接リストを実装するC++プログラム

    グラフの隣接リスト表現は、リンクリスト表現です。この表現では、リストの配列があります。配列のサイズはVです。ここで、Vは頂点の数です。つまり、V個の異なるリストを格納する配列があると言えます。リストヘッダーが頂点uの場合、uの隣接するすべての頂点を保持することを意味します。 隣接リスト表現の複雑さ この表現は、無向グラフの場合はO(V + 2E)を取り、有向グラフの場合はO(V + E)を取ります。エッジの数を増やすと、必要なスペースも増えます。 入力 : 出力 : アルゴリズム add_edge(adj_list、u、v) 入力 :エッジ{u、v}のuとv、およ

  2. データ構造の隣接リスト

    グラフは非線形のデータ構造です。これは、ノードを使用したデータと、エッジを使用したそれらの関係を表します。グラフGには2つのセクションがあります。頂点とエッジ。頂点はセットVを使用して表され、エッジはセットEとして表されます。したがって、グラフ表記はG(V、E)です。アイデアを得るための1つの例を見てみましょう。 このグラフには、5つの頂点と5つのエッジがあります。エッジが方向付けられます。例として、頂点BとDを接続するエッジを選択した場合、ソース頂点はBで、デスティネーションはDです。したがって、BをDに移動することはできますが、DからBに移動することはできません。 グラフは非線形