当前位置: 首页 > article >正文

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;
    }
};


http://www.kler.cn/a/584375.html

相关文章:

  • mapbox高阶,结合threejs(threebox)添加extrusion挤出几何体,并添加侧面窗户贴图和楼顶贴图,同时添加真实光照投影
  • ubuntu修改时区
  • idea更新git代码报错No Git Roots
  • 【算法】贪心
  • Python带多组标签的Snowflake SQL查询批量数据导出程序
  • (十一) 人工智能 - Python 教程 - Python元组
  • springboot_data介绍
  • JavaScript语言的区块链隐私
  • centos7使用gpu加速的MinerU
  • Java 和 Kotlin 实现 23 种设计模式:从理论到实践
  • 【Python办公】Excel通用匹配工具(双表互匹)
  • PHP火山引擎API签名方法
  • 【Python办公自动化】—Excel中相同编号自动添加-1-2-3...
  • Word中把参考文献引用改为上标
  • 描述K8S创建pod的全过程
  • Linux 系统负载过高的排查思路
  • Secure and Privacy-Preserving Decentralized Federated Learning同态加密联邦学习文献阅读
  • 大数据与区块链——天作之合的技术搭档
  • SiC/GaN器件测试新选择:MHO5000如何破解高频开关噪声难题?
  • android 调用wps打开文档并感知保存事件