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) }