2 wiflsnmo wiflsnmo 于 2016.04.12 16:36 提问

图的算法问题 已知边的起止节点求其中一个系统节点总数

求大神帮我想个算法,我有n组数据对,src->target,展示出来就是数个有向无环图,每个分隔的图称为一个系统,要求给出两个数据我能知道这两个数在不在同一个系统以及这个系统的节点总数是多少。有没有什么简单可行的方法啊
图片说明图片说明

1个回答

caozhy
caozhy   Ds   Rxr 2016.04.12 17:48

无非就是递归遍历。你每个节点除了本身数据之外,加上一个bool值表示是否被遍历过,伪代码如下:
int countNode(Node n)
{
int r = 0;
n.Visited = true;
for (subn : n.Nodes)
{
if (!subn.Visited)
r += countNode(subn);
}
return r + 1;
}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
有环图求环的个数和具体节点数
这个问题一直没仔细写过,cf上做到了就写一下,就是用栈存储+回溯,很简单。 #include #include #include #include #include using namespace std; const int N = 20; vector edge[N]; int s[N],top=0;//stl里的stack没办法遍历,所以用数组模拟 bool instack[N]; int
算法导论笔记:24单源最短路径
最短路径问题:一个带权重的有向图G = (V, E)和权重函数w: E->R,该权重函数将每条边映射到实数值的权重上。一条路径p的权重w(p)是构成该路径的所有边的权重之和,定义从节点u到结点v的最短路径权重δ (u, v)如下:        在实际应用中,可以用一张图表示道路交通图,结点代表城市,边代表城市之间的道路,边上的权重代表道路的长度。目标就是找出一条从城市A到城市B的最
如何计算树中叶子结点的个数?
如何计算树中叶子结点的个数?题目 已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3 的结点。则该树中有多少个叶子结点? 解1设共有N个结点,N-1条边( 因为树中边和结点的关系为:结点数=边数+1),X个叶子结点,则有(PS:x表示乘号) N=X+2+3+4 (1) N-1=0xX+1x2+2x3+3x4 (2) 将两个等式连立,则有 X=12
求二叉树的节点总数及树的高度
struct BinaryTreeNode{ int data; BinaryTreeNode *pLeft; BinaryTreeNode *pRight; }; //获取树中的节点数 int CountNode(BinaryTreeNode *pRoot){ if(pRoot == NULL) return 0; else if(pRoot->pLeft == NULL &&
程序员面试金典: 9.4树与图 4.2给定有向图,设计一个算法,找出两个节点之间是否存在一条路径。
#include #include #include #include using namespace std; /* 问题:给定有向图,设计一个算法,找出两个节点之间是否存在一条路径。 分析:有向图,无非是没有顶点的树,需要考虑顶点和边。 图的两种创建方式:邻接矩阵,邻接表。 找出两个节点之间是否存在一条路径。Dijstra:两点之间最短路径,Flord是任意两点最
图形分割算法<==>最小割<==>最大流<==>网络流问题
最近研究图形分割算法,然后就牵扯出了网络流问题中的最大流最小割问题。 反过来学习才是最好的掌握和理解路线: 第一、什么是网络流问题? 第二、最大流、最小割 上图网络流就是求解最大流的一个实例。由此,可以引出最大流的一些基本的定义和概念 可以这样看,图就是一种管道,管道有最大通过流量的限制,图中边的权值就是所谓的“容量”。同时,注意有唯一的源点和汇点。
图论(二):图的四种最短路径算法
本文总结了图的几种最短路径算法的实现:深度或广度优先搜索算法,弗洛伊德算法,迪杰斯特拉算法,Bellman-Ford算法 1),深度或广度优先搜索算法(解决单源最短路径) 从起始结点开始访问所有的深度遍历路径或广度优先路径,则到达终点结点的路径有多条,取其中路径权值最短的一条则为最短路径。 下面是核心代码: void dfs(int cur, int dst){ /
【Java】给定有向图,设计一个算法,找出两个结点之间是否存在一条路径
给定有向图,设计一个算法,找出两个结点之间是否存在一条路径 通过图的遍历,比如深度优先或者广度优先搜索等,就能解决这个问题 从结点的其中一个出发,在遍历过程中,检查是否找到另一个结点即可 在遍历过程中,访问过的结点都应被标记为“已访问”,以避免重复访问 深度优先实现起来比较简单,递归即可 但广度优先很适合用来找最短路径,深度优先在访问临近结点之前需要先深度遍历其中一个临近结点 impo
数据结构之图的关节点和重连通分量
数据结构之图的关节点和重连通分量
贪心算法------单源最短路径问题(Dijkstra)
1.问题描述