How to Represent Graph with adjacency matrix and adjacency List
Adjacency Matrix
#include<iostream>
using namespace std;
int vertexArray[20][20]; //the adjacency matrix initially 0
int count = 0;
void showMatrix(int v) {
int i, j;
for(i = 0; i < v; i++) {
for(j = 0; j < v; j++) {
cout << vertexArray[i][j] << " ";
}
cout << endl;
}
}
void set_edge(int u, int v) { //function to add edge into the matrix
vertexArray[u][v] = 1;
vertexArray[v][u] = 1;
}
main(int argc, char* argv[]) {
int v = 6; //there are 6 vertices in the graph
set_edge(0, 1);
set_edge(0, 2);
set_edge(0, 3);
set_edge(1, 1);
set_edge(1, 2);
set_edge(1, 3);
set_edge(2, 4);
set_edge(5, 1);
set_edge(5, 2);
showMatrix(v);
}
complexity of Adjacency Matrix
The complexity of Adjacency Matrix is O(V2).
Adjacency List
#include<iostream>
#include<list>
#include<iterator>
using namespace std;
void ShowAdjacencylist(list<int> adj_list[], int v) {
for(int i = 0; i<v; i++) {
cout << i << "->";
list<int> :: iterator it;
for(it = adj_list[i].begin(); it != adj_list[i].end(); ++it) {
cout << *it << " ";
}
cout << endl;
}
}
void setEdge(list<int> adj_list[], int u, int v) {
//add v into the list u, and u into list v
adj_list[u].push_back(v);
adj_list[v].push_back(u);
}
main(int argc, char* argv[]) {
int v = 6; //there are 6 vertices in the graph
//create an array of lists whose size is 6
list<int> adj_list[v];
setEdge(adj_list, 0, 1);
setEdge(adj_list, 0, 2);
setEdge(adj_list, 0, 3);
setEdge(adj_list, 1, 2);
setEdge(adj_list, 1, 1);
setEdge(adj_list, 2, 4);
setEdge(adj_list, 3, 2);
setEdge(adj_list, 4, 5);
setEdge(adj_list, 5, 1);
ShowAdjacencylist(adj_list, v);
}