C++ 邻接矩阵(代码)
C++邻接矩阵代码,见下:
#include<iostream>
using namespace std;
#define inf -1
class Graph{
private:
int vertices;
int **edges;
public:
Graph(int vertices);
~Graph();
void addEdge(int u, int v, int w);
void printGraph();
};
Graph::Graph(int vertices){
this->vertices = vertices;
edges = new int* [vertices];
for(int i=0; i<vertices; ++i){
edges[i] = new int[vertices];
for(int j=0; j<vertices; ++j){
edges[i][j] = inf;
}
}
}
Graph::~Graph(){
for(int i=0; i<vertices; ++i){
delete[] edges[i];
}
delete[] edges;
}
void Graph::addEdge(int u, int v, int w){
edges[u][v] = w;
}
void Graph::printGraph(){
for(int i=0; i<vertices; ++i){
for(int j=0; j<vertices; ++j){
cout << edges[i][j] << " ";
}
cout << endl;
}
}
int main(){
int vertices = 5;
Graph graph(vertices);
graph.addEdge(0, 1, 1);
graph.addEdge(0, 2, 3);
graph.addEdge(1, 2, 2);
graph.addEdge(2, 3, 7);
graph.addEdge(3, 4, 9);
graph.addEdge(4, 0, 4);
graph.addEdge(4, 2, 5);
graph.printGraph();
return 0;
}
代码一,对应力扣,传递信息,代码见下
class Solution {
int matrix[10][10];
int N;
int dfs(int u, int k){
if(k == 0){
if(u == N-1){
return 1;
}
return 0;
}
int sum = 0;
for(int i=0; i<N; ++i){
if(matrix[u][i]){
sum += dfs(i, k-1);
}
}
return sum;
}
public:
int numWays(int n, vector<vector<int>>& relation, int k) {
N = n;
memset(matrix, 0, sizeof(matrix));
for(int i=0; i<relation.size(); ++i){
int a = relation[i][0];
int b = relation[i][1];
matrix[a][b] = 1;
}
return dfs(0, k);
}
};
代码二,对应力扣 省份数量,代码见下:
class Solution {
bool color[201];
int count;
int n;
void dfs(vector<vector<int>>& isConnected, int u){
if(color[u]){
return;
}
color[u] = true;
for(int i=0; i<n; ++i){
if(isConnected[u][i]){
dfs(isConnected, i);
}
}
}
public:
int findCircleNum(vector<vector<int>>& isConnected) {
n = isConnected.size();
count = 0;
memset(color, false, sizeof(color));
for(int i=0; i<n; ++i){
if(color[i] == false){
dfs(isConnected, i);
++count;
}
}
return count;
}
};