Computer >> Máy Tính >  >> Lập trình >> C ++

Chương trình C ++ để biểu diễn đồ thị sử dụng danh sách tỷ lệ

Chương trình này biểu diễn một biểu đồ bằng cách sử dụng danh sách tỷ lệ và độ phức tạp về thời gian của thuật toán này là O (e).

Thuật toán

Begin
   Take the input of the number of vertex ‘v’ and edges ‘e’ and also
   take the input of ‘e’ pairs of vertexes of the given graph in e[][].
   For each edge print the corresponding vertex involved in that connection.
End

Mã mẫu

#include<iostream>
using namespace std;
int main() {
   int i, v, e, j, c;
   cout<<"Enter the number of vertexes of the graph: ";
   cin>>v;
   cout<<"\nEnter the number of edges of the graph: ";
   cin>>e;
   int edge[e][2];
   for(i = 0; i < e; i++) {
      cout<<"\nEnter the vertex pair for edge "<<i+1;
      cout<<"\nV(1): ";
      cin>>edge[i][0];
      cout<<"V(2): ";
      cin>>edge[i][1];
   }
   cout<<"\n\nThe incidence list representation for the given graph: ";
   for(i = 0; i < e; i++) {
      // For each vertex print, its adjacent vertex.
      cout<<"\n\tE("<<i+1<<") -> { ";
         cout<<"V("<<edge[i][0]<<") , "<<"V("<<edge[i][1]<<")";
         cout<<" }";
   }
}

Đầu ra

Enter the number of vertexes of the graph: 3
Enter the number of edges of the graph: 4
Enter the vertex pair for edge 1
V(1): 2
V(2): 1
Enter the vertex pair for edge 2
V(1): 1
V(2): 2
Enter the vertex pair for edge 3
V(1): 3
V(2): 2
Enter the vertex pair for edge 4
V(1): 2
V(2): 3
The incidence list representation for the given graph:
E(1) -> { V(2) , V(1) }
E(2) -> { V(1) , V(2) }
E(3) -> { V(3) , V(2) }
E(4) -> { V(2) , V(3) }