Câu 1:
template<class T>
typename DGraph<T>::Edge* DGraph<T>::VertexNode::getEdge(VertexNode* toNode) {
//TODO: Iterate through the adjacency list of this vertex
Edge* cur = this->adList;
while(cur){
if(cur->toNode == toNode){
return cur;
}
cur = cur->next;
}
return nullptr;
// checking if there exists an edge with this vertex as the starting
vertex
// and "toNode" as the ending vertex.
// If not return nullptr, else return that edge.
template<class T>
void DGraph<T>::VertexNode::addAdjacentEdge(Edge* newEdge) {
//TODO: add newEdge to adjacency list of this vertex.
newEdge->next = adList;
adList = newEdge;
}
template<class T>
bool DGraph<T>::VertexNode::connectTo(VertexNode* toNode, float weight) {
//TODO: get edge from this node to "toNode".
Edge* temp = getEdge(toNode);
//TODO: If the edge is not existed, create a new Edge and add it to the
adjacency list.
// If the edge is existed, update its weight.
if(temp){
temp->weight = weight;
return false;
}
//TODO: Return true if a new Edge is created; otherwise, return false.
Edge* newEdge = new Edge(this, toNode, weight);
addAdjacentEdge(newEdge);
return true;
}
template<class T>
bool DGraph<T>::VertexNode::removeTo(VertexNode *toNode) {
//TODO: remove the edge with "toNode" as the ending vertex from this node's
adjacency list.
Edge* tmp = getEdge(toNode);
if(!tmp){
return false;
}
if(tmp == adList){
adList = adList->next;
delete tmp;
return true;
}
Edge* it = adList;
while(it->next != tmp)
it = it->next;
if(tmp->next == nullptr){
it->next = nullptr;
delete tmp;
return true;
}
//TODO: return true if success; otherwise, return false.
it->next = tmp->next;
delete tmp;
return true;
}
-----------------------------------------------------------------------------------
-------------
-----------------------------------------------------------------------------------
-------------
-----------------------------------------------------------------------------------
-------------
-----------------------------------------------------------------------------------
-------------
-----------------------------------------------------------------------------------
-------------
câu 2:
template<class T>
typename DGraph<T>::VertexNode* DGraph<T>::getVertexNode(T vertex) {
//TODO: Iterate through the Node list of the graph
// check if any vertexNode contains vertex.
// If such a vertexNode exists, return it; otherwise, return nullptr.
VertexNode* cur = nodeList;
while(cur){
if(cur->vertex == vertex){
return cur;
}
cur = cur->next;
}
return nullptr;
}
template<class T>
void DGraph<T>::add(T vertex) {
//TODO: create a new vertexNode with vertex.
//TODO: add new vertexNode to the end of Node list of the graph.
//TODO: increase the countVertex.
VertexNode* newVertex = new VertexNode(vertex);
VertexNode* cur = nodeList;
if(!nodeList){
nodeList = newVertex;
countVertex++;
return;
}
while(cur->next){
cur = cur->next;
}
cur->next = newVertex;
countVertex++;
}
template <class T>
void DGraph<T>::connect(T from, T to, float weight) {
//TODO: get vertexNode with "from" and vertexNode with "to".
VertexNode* node_from = getVertexNode(from);
VertexNode* node_to = getVertexNode(to);
//TODO: If either of the two vertexNode objects does not exist,
// throw an exception: VertexNotFoundException("Vertex doesn't exist!").
if(!node_from || !node_to){
throw VertexNotFoundException("Vertex doesn't exist!");
}
//TODO: connect "from" vertexNode to "to" vertexNode.
// If a new edge is created, increase the countEdge.
if(node_from->connectTo(node_to,weight)) countEdge++;
}
-----------------------------------------------------------------------------------
------
-----------------------------------------------------------------------------------
------
-----------------------------------------------------------------------------------
------
câu 3:
template <class T>
bool DGraph<T>::removeEdge(T from, T to) {
//TODO: get vertexNode with "from" and vertexNode with "to".
VertexNode* F = getVertexNode(from);
VertexNode* To = getVertexNode(to);
//TODO: If either of the two vertexNode objects does not exist,
// throw an exception: VertexNotFoundException("Vertex doesn't exist!").
if(!F || !To){
throw VertexNotFoundException("Vertex doesn't exist!");
}
//TODO: Delete the edge between the "from" vertexNode and the "to" vertexNode.
(use removeTo method)
// If success return true and decrement the countEdge; otherwise, return
false;
bool remove = F->removeTo(To);
if(remove){
countEdge--;
return true;
}
return false;
}
template <class T>
void DGraph<T>::removeVertex(T removeVertex) {
// 1. Lấy đối tượng VertexNode tương ứng với removeVertex
VertexNode* removeNode = getVertexNode(removeVertex);
// 2. Nếu không tìm thấy vertexNode, ném ngoại lệ
if (!removeNode) {
throw VertexNotFoundException("Vertex doesn't exist!");
}
// 3. Duyệt qua tất cả các vertexNode trong danh sách nodeList của đồ thị
VertexNode* current = nodeList;
while (current) {
// - Kiểm tra và xóa các cạnh từ current tới removeNode
if (current != removeNode) {
if (current->removeTo(removeNode)) {
countEdge--; // giảm số lượng cạnh nếu thành công
}
}
// - Kiểm tra và xóa các cạnh từ removeNode tới current
if (removeNode->removeTo(current)) {
countEdge--; // giảm số lượng cạnh nếu thành công
}
current = current->next;
}
// 4. Xóa removeNode khỏi danh sách nodeList của đồ thị
if (nodeList == removeNode) {
nodeList = removeNode->next; // Nếu removeNode là đầu danh sách
} else {
current = nodeList;
while (current && current->next != removeNode) {
current = current->next;
}
if (current) {
current->next = removeNode->next; // Xóa removeNode khỏi danh sách
}
}
// 5. Xóa removeNode và giảm số lượng vertex
delete removeNode;
countVertex--;
}
-----------------------------------------------------------------------------------
---
-----------------------------------------------------------------------------------
---
-----------------------------------------------------------------------------------
---
câu 4:
template<class T>
string DGraph<T>::shape() {
//TODO: return the string with format: [Vertices: <numOfVertex>, Edges:
<numOfEdge>]
return "[Vertices: " + to_string(countVertex) + ", Edges: " +
to_string(countEdge) + "]";
}
template<class T>
bool DGraph<T>::empty() {
//TODO: return if graph is empty (it doesn't have any vertex and edge)
return (countVertex == 0 && countEdge == 0);
}
template<class T>
void DGraph<T>::clear() {
//TODO: remove all edges and vertices of graph.
VertexNode* current = nodeList;
while (current) {
VertexNode* toDelete = current;
current = current->next;
// Xóa tất cả các cạnh của đỉnh này
Edge* edge = toDelete->adList;
while (edge) {
Edge* edgeToDelete = edge;
edge = edge->next;
delete edgeToDelete; // Xóa các cạnh
countEdge--;
}
delete toDelete; // Xóa đỉnh
}
nodeList = nullptr; // Xóa danh sách đỉnh
countVertex = 0; // Đặt số lượng đỉnh về 0
countEdge = 0;
}
------------------------------------------------------------------------------
------------------------------------------------------------------------------
------------------------------------------------------------------------------
câu 5:
#include <queue>
class Graph
{
private:
int V;
Adjacency *adj;
public:
Graph(int V)
{
this->V = V;
adj = new Adjacency[V];
}
void addEdge(int v, int w)
{
adj[v].push(w);
adj[w].push(v);
}
void printGraph()
{
for (int v = 0; v < V; ++v)
{
cout << "\nAdjacency list of vertex " << v << "\nhead ";
adj[v].print();
}
}
Adjacency *BFS(int v)
{
Adjacency* result = new Adjacency();
bool *visited = new bool[V]{false};
queue<int> q;
visited[v] = true;
q.push(v);
while(!q.empty()){
int cur = q.front();
q.pop();
result->push(cur);
for(int i = 0; i < adj[cur].getSize(); i++){
int neighbor = adj[cur].getElement(i);
if(!visited[neighbor]){
visited[neighbor] = true;
q.push(neighbor);
}
}
}
delete visited;
return result;
}
};
------------------------------------------------------------------------------
------------------------------------------------------------------------------
------------------------------------------------------------------------------
câu 6:
#include <stack>
class Graph
{
private:
int V;
Adjacency *adj;
public:
Graph(int V)
{
this->V = V;
adj = new Adjacency[V];
}
void addEdge(int v, int w)
{
adj[v].push(w);
adj[w].push(v);
}
void printGraph()
{
for (int v = 0; v < V; ++v)
{
cout << "\nAdjacency list of vertex " << v << "\nhead ";
adj[v].print();
}
}
Adjacency *DFS(int v)
{
// v is a vertex we start DFS
Adjacency* result = new Adjacency();
bool *visited = new bool[V]{false};
stack<int> st;
visited[v] = true;
st.push(v);
while(!st.empty()){
int cur = st.top();
st.pop();
result->push(cur);
for(int i = adj[cur].getSize() - 1; i >= 0; i--){
int neighbor = adj[cur].getElement(i);
if(!visited[neighbor]){
visited[neighbor] = true;
st.push(neighbor);
}
}
}
delete visited;
return result;
}
};
-----------------------------------------------------------------------------------
-------------
-----------------------------------------------------------------------------------
-----------
-----------------------------------------------------------------------------------
----------
câu 7:
void dfs(int node, vector<vector<int>>& friends, vector<bool>& visited) {
visited[node] = true;
// Visit all friends of the current node
for (int neighbor : friends[node]) {
if (!visited[neighbor]) {
dfs(neighbor, friends, visited);
}
}
}
int numberOfFriendGroups(vector<vector<int>>& friends) {
int n = friends.size();
vector<bool> visited(n, false); // Keep track of visited nodes
int friendGroups = 0;
// Iterate over all nodes
for (int i = 0; i < n; i++) {
if (!visited[i]) {
// If the node is not visited, start a DFS from this node
dfs(i, friends, visited);
friendGroups++; // Each DFS call indicates a new friend group
}
}
return friendGroups;
}
-----------------------------------------------------------------------------------
-----------------------------------------------------------------------------------
--
-----------------------------------------------------------------------------------
-
câu 8:
#include <iostream>
#include <vector>
#include <list>
using namespace std;
class DirectedGraph
{
int V;
vector<list<int>> adj;
public:
DirectedGraph(int V)
{
this->V = V;
adj = vector<list<int>>(V, list<int>());
}
void addEdge(int v, int w)
{
adj[v].push_back(w);
}
bool isCyclicUtil(int v, bool visited[], bool *rs) {
if(!visited[v]) {
visited[v] = true;
rs[v] = true;
list<int>::iterator it;
for(it = adj[v].begin(); it != adj[v].end(); ++it) {
if (!visited[*it] && isCyclicUtil(*it, visited, rs))
return true;
else if (rs[*it])
return true;
}
}
rs[v] = false;
return false;
}
bool isCyclic()
{
bool *visited = new bool[V];
bool *rs = new bool[V];
for (int i = 0; i < V; i++) {
visited[i] = false;
rs[i] = false;
}
for (int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, rs))
return true;
return false;
}
};
-----------------------------------------------------------------------------------
---------------------------------------------------------------------------------
----------------------------------------------------------------------------------
câu 9:
class Graph {
int V;
Adjacency* adj;
public:
Graph(int V){
this->V = V;
adj = new Adjacency[V];
}
void addEdge(int v, int w){
adj[v].push(w);
}
//Heling functions
void topologicalSortUtil(int v, bool visited[], list<int>& Stack) {
visited[v] = true;
for (int i=0; i != adj[v].getSize(); ++i)
if (!visited[adj[v].getElement(i)])
topologicalSortUtil(adj[v].getElement(i), visited, Stack);
Stack.push_back(v);
}
void topologicalSort() {
list<int> Stack;
bool* visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
while (Stack.empty() == false) {
cout << Stack.back() << " ";
Stack.pop_back();
}
}
};
------------------------------------------------------------------------
-------------------------------------------------------------------------
--------------------------------------------------------------------------
câu 10:
int minDistance(int dist[], bool sptSet[], int V)
{
int min = 99999, min_index=-1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
int Dijkstra(int** graph, int src,int dst)
{
int V=6;
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++){
dist[i] = 99999;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet,V);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != 99999 && dist[u] + graph[u]
[v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
return dist[dst];
}
