C ++程序使用2D数组表示图
这是一个C++程序，表示使用2D数组的图形。
该算法的时间复杂度为O（v*v）。
算法
Begin Take the input of the number of vertex ‘v’ and edges ‘e’. Assign memory to the graph[][] matrix. Take the input of ‘e’ pairs of vertexes of the given graph in graph[][]. For each pair of connected vertex(v1, v2), store 1 in the graph[][] at the index (v1, v2) and (v2, v1). Print the matrix using PrintMatrix(). End
范例程式码
#include<iostream>
#include<iomanip>
using namespace std;
void PrintMatrix(int **matrix, int n) {
int i, j;
cout<<"\n\n"<<setw(4)<<"";
for(i = 0; i < n; i++)
cout<<setw(3)<<"("<<i+1<<")";
cout<<"\n\n";
for(i = 0; i < n; i++) {
cout<<setw(3)<<"("<<i+1<<")";
for(j = 0; j < n; j++) {
cout<<setw(4)<<matrix[i][j];
}
cout<<"\n\n";
}
}
int main() {
int i, v, e, j, v1, v2;
cout<<"Enter the number of vertexes of the graph: ";
cin>>v;
int **graph;
graph = new int*[v];
for(i = 0; i < v; i++) {
graph[i] = new int[v];
for(j = 0; j < v; j++) graph[i][j] = 0;
}
cout<<"\nEnter the number of edges of the graph: ";
cin>>e;
for(i = 0; i < e; i++) {
cout<<"\nEnter the vertex pair for edge "<<i+1;
cout<<"\nV(1): ";
cin>>v1;
cout<<"V(2): ";
cin>>v2;
graph[v1-1][v2-1] = 1;
graph[v2-1][v1-1] = 1;
}
PrintMatrix(graph, v);
}输出结果
Enter the number of vertexes of the graph: 5 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): 3 V(2): 2 Enter the vertex pair for edge 3 V(1): 1 V(2): 1 Enter the vertex pair for edge 4 V(1): 3 V(2): 1 (1) (2) (3) (4) (5) (1) 1 1 1 0 0 (2) 1 0 1 0 0 (3) 1 1 0 0 0 (4) 0 0 0 0 0 (5) 0 0 0 0 0