兩節點間所有路徑的python（以下哪種結構節點間路徑更多）

本文目錄一覽：

• 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

*/