本文目录一览:
- 1、如何找出二叉树两结点之间的路径,并嫠薪岬
- 2、python 的 networkx 的中有没有 函数 可以直接取出与 某一个点(node)所相连的所有边的个数?
- 3、python networkx希望得到两个非相邻点所有路径,而不只是最短路径,怎么实现?
- 4、如何使用Python的networkx模块来生成节点列表完全连通子图
- 5、如何查找无向图两个节点间的所有路径
- 6、无向图中求两定点之间所有路径。图用二维数组存储。最好用c语言、给我解题思路也行。谢谢
如何找出二叉树两结点之间的路径,并嫠薪岬
使用中序遍历即可。
bool getPath(TreeNode *root, TreeNode *one, TreeNode *two)
{
int getNodes = 0;
if (root == NULL)
return false;
if (getPath(root-left, one, two))
{
//当前节点入队
if (getPath(root-right, one, two)) //如果两个节点刚好位于当前节点的左右子树则路径已经找到。
return false;
else //否则,仅仅找到了一个节点还需要继续搜索
return true;
}
else if (getPath(root-right, one, two))//仅仅找到了一个节点还需要继续搜索
{
//当前节点入队
return true;
}
return false;
}
最终获得队列则是两个节点间的路径。
python 的 networkx 的中有没有 函数 可以直接取出与 某一个点(node)所相连的所有边的个数?
path=nx.all_pairs_shortest_path(G) #调用多源最短路径算法,计算图G所有节点间的最短路径
print path[0][2] #输出节点0、2之间的最短路径序列: [0, 1, 2]
python networkx希望得到两个非相邻点所有路径,而不只是最短路径,怎么实现?
这个需要你自己实现,就是你从起点开始,把其所有邻点作为路径中下一个点,然后再加入这些邻点的邻点,直到找到需要的终点,为什么不提供api呢,可能是因为如果路径中存在环,那这样的路径是有无数条的
如何使用Python的networkx模块来生成节点列表完全连通子图
path=nx.all_pairs_shortest_path(G)#调用多源最短路径算法,计算图G所有节点间的最短路径printpath[0][2]#输出节点0、2之间的最短路径序列:[0,1,2]
如何查找无向图两个节点间的所有路径
#define True 1 #define False 0 int visited[MAX_VERTEX_NUM]; void BreadthFirstSearch(Graph g,int v0) {/*广度优先搜索图g中v0所在的连通子图*/ int x,w,m; InitQueue(Q); EnterQueue(Q,v0); while(!Empty(Q)) { DeleteQueue(Q,x); if(!visited[x]) { visit(x); visited[x]=True; } w=FirstAdjVertex(g,x); while((w!=-1)!visited[w]) { EnterQueue(Q,w); w=NextAdjVertex(g,x,w); } } }//子图就是无向图的路径
无向图中求两定点之间所有路径。图用二维数组存储。最好用c语言、给我解题思路也行。谢谢
/*
深度优先搜索算法。
*/
#include stdio.h
#include stdlib.h
#include assert.h
// 图中最多的点数
#define MAX_NODES_NUM 10
// 图中两点最多的路径数
#define MAX_PATHS_BETWEEN_TWO_NODES_NUM (1(MAX_NODES_NUM-2))
// 标记无穷远的路径长度
#define INFINTITY (130)
// 标记可以到达的路径长度
#define REACHABLE 1
#define TRUE 1
#define FALSE 0
struct Path
{
int size;
int nodes[MAX_NODES_NUM];
};
/*
获取地图 map 中 点 start 到 点 end 的所有路径
map : 地图
n : 地图的点数
start : 起点
end : 终点
paths : 保存找到的所有从 start 到 end 路径
paths : 保存找到的所有从 start 到 end 路径数目
*/
void getPaths(int map[][MAX_NODES_NUM],int n ,int start,int end,int isNodeUsed[],struct Path paths[],int * pathsNum)
{
int i,j;
struct Path tempPaths[MAX_PATHS_BETWEEN_TWO_NODES_NUM];
int tempPathsNum ;
// 标记当前起点不可用
isNodeUsed = TRUE;
for(i=0;in;i++)
{
// 节点不在路径中,且可以到达
if(isNodeUsed[i] == FALSE map[i]== REACHABLE)
{
// 当前起点能直接到达终点
if(i == end)
{
paths[(*pathsNum)].size = 2;
paths[(*pathsNum)].nodes[0] = end;
paths[(*pathsNum)].nodes[1] = start;
(*pathsNum)++;
}
// 当前起点能不能直接到达终点,尝试当前节点通过其他节点达到终点
else
{
// 递归计算从当前起点到达终点的所有路径
tempPathsNum = 0;
getPaths(map,n,i,end,isNodeUsed,tempPaths,tempPathsNum);
// 处理找到的,从当前起点到达终点的所有路径
for(j=0;jtempPathsNum;j++)
{
// 在当前起点到达终点的所有路径中,添加当前起点
tempPaths[j].nodes[tempPaths[j].size] = start;
tempPaths[j].size ++;
// 合并到最终的路径中
paths[(*pathsNum)] = tempPaths[j];
(*pathsNum)++;
}
}
}
}
isNodeUsed = FALSE;
}
int main(int argc, char *argv[])
{
int map[MAX_NODES_NUM][MAX_NODES_NUM];
int isNodeUsed[MAX_NODES_NUM];
struct Path paths[MAX_PATHS_BETWEEN_TWO_NODES_NUM];
int pathsNum;
int i,j;
int start,end;
int a,b;
int n,m;
// 读取点数,路径数
while(scanf("%d%d",n,m)!=EOF)
{
// 初始化图
for(i=0;in;i++)
{
isNodeUsed[i] = FALSE;
for(j=0;jn;j++)
{
map[i][j] = INFINTITY;
}
}
// 读入路径
for(i=0;im;i++)
{
scanf("%d%d",a,b);
// 标记 a b 间有路径,注意是无向图,标记两次
map[a][b] = REACHABLE;
map[b][a] = REACHABLE;
}
// 要连接的两个点
scanf("%d%d",start,end);
// 查找点 start 到点 end 的所有路径
pathsNum = 0;
getPaths(map,n,start,end,isNodeUsed,paths,pathsNum);
// 打印点 start 到点 end 的所有路径
for(i=0;ipathsNum;i++)
{
for(j=paths[i].size-1;j=1;j--)
{
printf("%d - ",paths[i].nodes[j]);
}
printf("%d\n",paths[i].nodes[j]);
}
}
return 0;
}
/*
测试用数据:
1)首先输入点数 n,路径条数 m,
2)接下来输入 m 对点的编号,每对点 a,b 表示点 a 和 点 b 之间有一条路
点的编号从 0 开始到 n-1.
3)最后输入要连接的两个点
输入:
6 14
0 1
0 2
1 0
1 3
2 0
2 4
2 5
3 1
3 5
4 2
4 5
5 2
5 3
5 4
0 5
输出:
0 - 1 - 3 - 5
0 - 2 - 4 - 5
0 - 2 - 5
*/