Back to Code List
#### Graphs

### 1.cpp

### 1_input.txt

### 2.cpp

### 2_input.txt

### 3.cpp

### 3_input.txt

c++

Here are three files with different types of graphs and their traversal. I can't take much claim to these as I don't fully understand all of the code, but hopefully it may help someone in the future.

```
#include <iostream>
#include <fstream>
using namespace std;
enum colorType {white, blue, red};
struct Vertex
{
int id;//the id of the vertex
Vertex * next;
Vertex(int id_input, Vertex * input_next = NULL)
{
id = id_input;
next = input_next;
}
};
class Graph
{
private:
colorType * color;
int * pre;
int * dis;
public:
int n;//the number of vertices, the ids of the vertices are from 0 to n-1
Vertex ** adj;//adj[i] points the head of the adjacency list of vertex i
void printSP(int source, int v);//print shortest path from the source to v
Graph(int n_input);//constructor
void setAdjLists(int * adjM);//build the adjacency lists from the adecency matrix adjM
void printAdjLists();//print the adjacency lists of the graph
void printTraversal();
void traverse(int);
};
void Graph::traverse(int v)
{
// Mark the current node as visited and print it
color[v] = blue;
cout << v << " ";
// Recur for all the vertices adjacent to this vertex
Vertex * curr = adj[v];
while (curr != NULL) {
if(color[curr->id] == white)
traverse(curr->id);
curr = curr->next;
}
}
void Graph::printTraversal() {
// Mark all the vertices as not visited
color = new colorType[n];
for(int i = 0; i < n; i++)
color[i] = white;
// Call the recursive helper function to print DFS traversal
// starting from all vertices one by one
for(int i = 0; i < n; i++)
if(color[i] == white) {
traverse(i);
} else {
color[i] = red;
}
}
//initialize the graph by getting the number of vertices from n_input
Graph::Graph(int n_input)
{
n = n_input;
adj = new Vertex * [n];
//initialize adj[i] to NULL
for(int i = 0; i < n; i++)
adj[i] = NULL;
}
//construct the adj lists from the adj matrix adjM
void Graph::setAdjLists(int * adjM)
{
for(int i = 0; i < n; i++)
{
//create the i-th adj list adj[i], note that I consider the
//vertices in the reverse order from n-1 to 0 so that I can
//construct the list in order from 0 to n-1 because a new
//vertex is always inserted to the front
for(int j = n-1; j >= 0; j--)
{
if(adjM[i * n + j] == 1)
{
//create a new node and add it to the front of adj[i]
Vertex * v = new Vertex (j);
v->next = adj[i];
adj[i] = v;
}
}
}
}
//print the adj lists
void Graph::printAdjLists()
{
for(int i = 0; i < n; i++)
{
cout << "Adj list of vertex " << i << ": ";
Vertex *v = adj[i];
while(v != NULL)
{
if (v->next != NULL)
cout << v->id << "->";
else
cout << v->id;
v = v->next;
}
cout << endl;
}
cout << endl;
}
int main()
{
//open files
ifstream inputFile;
inputFile.open("1_input.txt");
if (!inputFile)
cout << "Error opening the input file " << endl;
int n;
//read the number in the first line, which is the number of vertices of
//the input graph
inputFile >> n;
//cout << "The number of vertices is: " << n << endl;
//next we read the adjacency matrix from the file to an array M.
//Here we use a one-dimensional array to simulate a two-dimesional
//adjacency matrix because we already know the length of each row
//is n
int * M = new int [n * n];
int i = 0;
int value;
while(inputFile >> value)
{
M[i] = value;
i++;
}
//uncomment the following piece of code if you want to check
//whether the adj matrix is read correctly from the input file
/*
cout << "The following is the matrix:" << endl;
for(int i = 0; i < n * n; i++)
{
if(i % n == 0)
cout << endl;
cout << M[i] << " ";
}
cout << endl;
*/
//initialize the graph by passing n to it and construct the
//adjacency lists
Graph graph(n);
graph.setAdjLists(M);
//uncomment the following line if you want to print the adj lists
//graph.printAdjLists();
cout << "The following is the DFS traversal vertex order, staring from vertex 0:" << endl;
graph.printTraversal();
cout << endl;
inputFile.close();
return 0;
}
```

```
8
0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 1 0 1 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
```

```
#include <iostream>
#include <fstream>
using namespace std;
struct Vertex
{
int id;//the id of the vertex
Vertex * next;
Vertex(int id_input, Vertex * input_next = NULL)
{
id = id_input;
next = input_next;
}
};
class Graph
{
public:
int n;//the number of vertices, the ids of the vertices are from 0 to n-1
Vertex ** adj;//adj[i] points the head of the adjacency list of vertex i
void topSort();//do topological sort
Graph(int n_input);//constructor
void setAdjLists(int * adjM);//build the adjacency lists from the adecency matrix adjM
void printAdjLists();//print the adjacency lists of the graph
};
void Graph::topSort()
{
int *degArr = new int[n];
int *queue = new int[n];
for (int i = 0; i < n; i++)
degArr[i] = 0;
//get degress for each vertex
for (int i = 0; i < n; i++)
{
Vertex * v = adj[i];
while (v != NULL)
{
degArr[v->id]++;
v = v->next;
}
}
int qFront, qRear;
qFront = -1;
//queue initial verticies
for (int i = 0; i < n; i++)
{
if (degArr[i] == 0)
{
if (qFront > -1)
{
// add to queue
qRear++;
queue[qRear] = i;
}
else
{
//start queue
qFront = qRear = 0;
queue[0] = i;
}
}
}
int count = 0;
while (qFront != -1 && qFront <= qRear)
{
int curr = queue[qFront];
//dequeue and print
cout << curr << " ";
qFront++;
count++;
//check the adjacecy list of u
Vertex * v = adj[curr];
while (v != NULL)
{
degArr[v->id]--;
if (degArr[v->id] == 0)
{
qRear++;
queue[qRear] = v->id;
}
v = v->next;
}
}
cout << endl;
if (count < n)
cout << "Not a DAG. ";
}
Graph::Graph(int n_input)
{
n = n_input;
adj = new Vertex * [n];
//initialize adj[i] to NULL
for(int i = 0; i < n; i++)
adj[i] = NULL;
}
//construct the adj lists from the adj matrix adjM
void Graph::setAdjLists(int * adjM)
{
for(int i = 0; i < n; i++)
{
//create the i-th adj list adj[i], note that I consider the
//vertices in the reverse order from n-1 to 0 so that I can
//construct the list in order from 0 to n-1 because a new
//vertex is always inserted to the front
for(int j = n-1; j >= 0; j--)
{
if(adjM[i * n + j] == 1)
{
//create a new node and add it to the front of adj[i]
Vertex * v = new Vertex (j);
v->next = adj[i];
adj[i] = v;
}
}
}
}
//print the adj lists
void Graph::printAdjLists()
{
for(int i = 0; i < n; i++)
{
cout << "Adj list of vertex " << i << ": ";
Vertex *v = adj[i];
while(v != NULL)
{
if (v->next != NULL)
cout << v->id << "->";
else
cout << v->id;
v = v->next;
}
cout << endl;
}
cout << endl;
}
int main()
{
//open files
ifstream inputFile;
inputFile.open("2_input.txt");
if (!inputFile)
cout << "Error opening the input file " << endl;
int n;
//read the number in the first line, which is the number of vertices of
//the input graph
inputFile >> n;
cout << "The number of vertices is: " << n << endl;
//next we read the adjacency matrix from the file to an array M.
//Here we use a one-dimensional array to simulate a two-dimesional
//adjacency matrix because we already know the length of each row
//is n
int * M = new int [n * n];
int i = 0;
int value;
while(inputFile >> value)
{
M[i] = value;
i++;
}
inputFile.close();
//uncomment the following piece of code if you want to check
//whether the adj matrix is read correctly from the input file
cout << "The following is the matrix:" << endl;
for(int i = 0; i < n * n; i++)
{
if(i % n == 0)
cout << endl;
cout << M[i] << " ";
}
cout << endl;
//initialize the graph by passing n to it
Graph graph(n);
graph.setAdjLists(M);
//uncomment the following line if you want to print the adj lists
graph.printAdjLists();
cout << "The following is a topological order:" << endl;
graph.topSort();
cout << endl;
return 0;
}
```

```
7
0 1 0 0 1 0 0
0 0 1 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
0 0 0 1 1 0 0
```

```
#include <iostream>
#include <fstream>
using namespace std;
//enum colorType {white, blue, red};
const int MAX = 10000;
struct Vertex
{
int id;//the id of the vertex
int weight; //the weight of an edge (u,v), where v is the current node and v is in the adj list of vertex u
Vertex * next;
Vertex(int id_input, int weight_input = 1, Vertex * next_input = NULL)
{
id = id_input;
weight = weight_input;
next = next_input;
}
};
class Graph
{
private:
int * pre;//the predecessor array
int * dis;//the shortest path distance array
public:
int n;//the number of vertices, the ids of the vertices are from 0 to n-1
Vertex ** adj;//adj[i] points the head of the adjacency list of vertex i
Graph(int n_input);//the class constructor
void Dijkstra(int s);//compute a shortest path tree from the source vertex s in a general graph
void printSP(int source, int v);//print the shortest path from the source vertex to v
int getSPdis(int v);//return the shortest path distance from the source vertex to v
void setAdjLists(int * adjM);// convert the adj matrix M to adj list
void printAdjLists();//print the adj list of the graph
};
//compute the correct information for the two
//arrays pre[] and dis[]
void Graph::Dijkstra(int s)
{
int count = n;
int *queue = new int[n];
for (int i = 0; i < n; i++)
{
dis[i] = MAX;
pre[i] = -1;
}
dis[s] = 0;
for (int i = 0; i < n; i++)
queue[i] = 1;
while (count > 0)
{
//extract min
int min;
int currmin = MAX;
for (int i = 0; i < n; i++)
{
if (queue[i] == 1 && dis[i] < currmin)
{
min = i;
currmin = dis[i];
}
}
//dequeue
int idx = min;
queue[idx] = 0;
count--;
//update weights
Vertex * v = adj[idx];
while (v != NULL)
{
if (dis[v->id] > dis[idx] + v->weight)
{
dis[v->id] = dis[idx] + v->weight;
pre[v->id] = idx;
}
v = v->next;
}
}
}
//return
int Graph::getSPdis(int v)
{
return dis[v];
}
void Graph::printSP(int source, int v)
{
if(v == source)
cout << source;
else
{
printSP(source, pre[v]);
cout << "->" << v;
}
}
Graph::Graph(int n_input)
{
n = n_input;
adj = new Vertex * [n];
//initialize adj[i] to NULL
for(int i = 0; i < n; i++)
adj[i] = NULL;
//create the two arrays of size n for the n vertices
pre = new int [n];
dis = new int [n];
}
void Graph::setAdjLists(int * adjM)
{
for(int i = 0; i < n; i++)
{
//create the i-th adj list adj[i], note that I consider the
//vertices in the reverse order from n-1 to 0 so that I can
//construct the list in order from 0 to n-1 because a new
//vertex is always inserted to the front
for(int j = n-1; j >= 0; j--)
{
if(adjM[i * n + j] > 0)
{
//create a new node and add it to the front of adj[i]
Vertex * v = new Vertex (j, adjM[i * n + j]);
v->next = adj[i];
adj[i] = v;
}
}
}
}
void Graph::printAdjLists()
{
cout << "The following are the adjacent lists with edge weights in the parentheses:" << endl;
for(int i = 0; i < n; i++)
{
cout << "Adj list of vertex " << i << ": ";
Vertex *v = adj[i];
while(v != NULL)
{
if (v->next != NULL)
cout << v->id << "(" << v->weight << ")" << "->";
else
cout << v->id << "(" << v->weight << ")";
v = v->next;
}
cout << endl;
}
cout << endl;
}
int main()
{
//open files
ifstream inputFile;
inputFile.open("3_input.txt");
if (!inputFile)
cout << "Error opening the input file " << endl;
int n;
//read the number in the first line, which is the number of vertices of
//the input graph
inputFile >> n;
cout << "The number of vertices is: " << n << endl << endl;
//next we read the adjacency matrix from the file to an array M.
//Here we use a one-dimensional array to simulate a two-dimesional
//adjacency matrix because we already know the length of each row
//is n
int * M = new int [n * n];
int i = 0;
int value;
while(inputFile >> value)
{
M[i] = value;
i++;
}
inputFile.close();
//uncomment the following piece of code if you want to check
//whether the adj matrix is read correctly from the input file
cout << "The following is the matrix:" << endl;
for(int i = 0; i < n * n; i++)
{
if(i % n == 0)
cout << endl;
cout << M[i] << " ";
}
cout << endl;
//initialize the graph by passing n to it
Graph graph(n);
graph.setAdjLists(M);
//print the adj lists with edge weights
graph.printAdjLists();
int source_vertex = 0;//the source vertex is 0
graph.Dijkstra(source_vertex);
//after the Dijkstra's algorithm, the following for loop is supposed to
//print the shortest paths from the source vertex to all other
//vertices
for(int i = 1; i <= n-1; i++)
{
cout << "The shortest path from the source vertex " << source_vertex << " to vertex " << i <<": ";
graph.printSP(source_vertex, i);// print the shortest path from 0 to 5 with source 0
cout << endl;
}
cout << endl;
//after the Dijkstra's algorithm, the following for loop is supposed to
//print the shortest path distances from the source vertex to all other
//vertices
for(int i = 1; i <= n-1; i++)
{
cout << "The shortest path distance from the source vertex " << source_vertex << " to vertex " << i <<" is: ";
cout << graph.getSPdis(i) << endl;
}
return 0;
}
```

```
6
0 5 0 0 10 0
0 0 2 9 3 8
7 0 0 6 0 4
0 0 4 0 8 3
0 2 0 1 0 0
0 0 0 6 0 0
```