無向圖深度搜索演算法

⑴ 基於深度優先搜索演算法，寫出求無向圖連通分量的演算法

你可以到網上找一下相關的源碼
這個重頭寫 太恐怖了
沒個兩三天出不來。

⑵ 你好，請問用鄰接表存儲無向圖，進行深度優先搜索的時間復雜度為什麼

設有n個點，e條邊
鄰接矩陣：矩陣包含n^2個元素，在演算法中，共n個頂點，對每個頂點都要遍歷n次，所以時間復雜度為O(n^2)
鄰接表：包含n個頭結點和e個表結點，演算法中對所有結點都要遍歷一次，所以時間復雜度為
O（n+e）
順便，對於廣度優先演算法的時間復雜度，也是這樣

⑶ 深度優先搜索的詳細解釋

事實上，深度優先搜索屬於圖演算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次.
舉例說明之：下圖是一個無向圖，如果我們從A點發起深度優先搜索（以下的訪問次序並不是唯一的，第二個點既可以是B也可以是C,D），則我們可能得到如下的一個訪問過程：A->B->E（沒有路了！回溯到A)->C->F->H->G->D（沒有路，最終回溯到A,A也沒有未訪問的相鄰節點，本次搜索結束）.簡要說明深度優先搜索的特點：每次深度優先搜索的結果必然是圖的一個連通分量.深度優先搜索可以從多點發起.如果將每個節點在深度優先搜索過程中的"結束時間"排序（具體做法是創建一個list，然後在每個節點的相鄰節點都已被訪問的情況下，將該節點加入list結尾，然後逆轉整個鏈表)，則我們可以得到所謂的"拓撲排序",即topological sort.

⑷ 根據用戶的輸入建立一個以鄰接矩陣存儲的無向圖，然後轉換為鄰接表存儲，最後進行深度優先搜索生成森林。

編寫程序建立該圖的鄰接矩陣存儲。
(2)編寫程序建立該圖的鄰接表存儲。(3)基於上圖所建的存儲結構，編寫實現深度優先搜索演算法和廣度優先搜索演算法

⑸ 無向有權的圖的深度、廣度優先遍歷怎麼做的啊，他的遍歷序列怎麼求呢

總結深度優先與廣度優先的區別
1、區別

1） 二叉樹的深度優先遍歷的非遞歸的通用做法是採用棧，廣度優先遍歷的非遞歸的通用做法是採用隊列。

2） 深度優先遍歷：對每一個可能的分支路徑深入到不能再深入為止，而且每個結點只能訪問一次。要特別注意的是，二叉樹的深度優先遍歷比較特殊，可以細分為先序遍歷、中序遍歷、後序遍歷。具體說明如下：

先序遍歷：對任一子樹，先訪問根，然後遍歷其左子樹，最後遍歷其右子樹。
中序遍歷：對任一子樹，先遍歷其左子樹，然後訪問根，最後遍歷其右子樹。
後序遍歷：對任一子樹，先遍歷其左子樹，然後遍歷其右子樹，最後訪問根。
廣度優先遍歷：又叫層次遍歷，從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。

3）深度優先搜素演算法：不全部保留結點，佔用空間少；有回溯操作(即有入棧、出棧操作)，運行速度慢。

廣度優先搜索演算法：保留全部結點，佔用空間大； 無回溯操作(即無入棧、出棧操作)，運行速度快。

⑹ 無向圖的度數與邊的關系

當圖為無向圖是邊數為e時，那麼度數為2e，當圖為有向2圖時，那麼度數也為2e，所以說邊數e和度數之間的關系為2e。

基本圖：把有向圖D的每條邊除去定向就得到一個相應的無向圖G，稱G為D的基本圖。稱D為G的定向圖

圖G的頂點數和邊數e的關系：若G是無向圖，則0≤e≤n(n-1)/2。若G為無向圖，則0≤e≤n(n-1)。

(6)無向圖深度搜索演算法擴展閱讀：

有向圖和無向圖求解最短路徑區別：

1、無向圖最短路問題使用單標號法。單標號法是對每一點賦予一個路權標號。

2、有向最短路問題使用雙標號法。雙標號法是對每一點賦予兩個標號：路徑和路權。

完全圖具有最多的邊數。任意一對頂點間均有邊相連。

圖的遍歷演算法：

1、廣度優先搜索法

圖的廣度優先搜索是樹的按層次遍歷的推廣，它的基本思想是：首先訪問初始點vi，並將其標記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點vi1，vi2，…，vi t，並均標記已訪問過。

然後再按照vi1，vi2，……，vi t的次序，訪問每一個頂點的所有未被訪問過的鄰接點，並均標記為已訪問過，依次類推，直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。

2、深度優先搜索法

深度優先搜索法是樹的先根遍歷的推廣，基本思想是：從圖G的某個頂點v0出發，訪問v0，然後選擇一個與v0相鄰且沒被訪問過的頂點vi訪問，再從vi出發選擇一個與vi相鄰且未被訪問的頂點vj進行訪問，依次繼續。

如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則退回到已被訪問的頂點序列中最後一個擁有未被訪問的相鄰頂點的頂點w，從w出發按同樣的方法向前遍歷，直到圖中所有頂點都被訪問。

⑺ 7個頂點組成的無向圖。從頂點1出發，對它進行深度優先遍歷得到的序列是（）

序列為：1354267。

深度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出剛訪問這個結點的第一個未被訪問的鄰結點，然後再以此鄰結點為頂點，繼續找它的下一個新的頂點進行訪問，重復此步驟，直到所有結點都被訪問完為止。

廣度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出這個結點的所有未被訪問的鄰接點，訪問完後再訪問這些結點中第一個鄰接點的所有結點，重復此方法，直到所有節點都被訪問完為止。

(7)無向圖深度搜索演算法擴展閱讀：

深度優先遍歷的相關要求規定：

1、深度優先搜索屬於圖演算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

2、每次深度優先搜索的結果必然是圖的一個連通分量。深度優先搜索可以從多點發起，如果將每個節點在深度優先搜索過程中的"結束時間"排序，則可以得到所謂的"拓撲排序"，即topological sort。

3、深度優先搜索用一個數組存放產生的所有狀態。把初始狀態放入數組中，設為當前狀態；擴展當前的狀態，產生一個新的狀態放入數組中，同時把新產生的狀態設為當前狀態；判斷當前狀態是否和前面的重復，如果重復則回到上一個狀態，產生它的另一狀態。

⑻ 若無向圖G=(V,E)中含有7個頂點，要保證G在任何情況下都是連通的，則需要的邊數最少是（）條

至少有n條邊，正好可以組成一個環。

無向連通圖指的是圖中的每個頂點都有邊與其相連，且圖中沒有斷處，即對無向連通圖進行遍歷時，僅需要從圖中的一個頂點出發。

進行深度優先或廣度優先搜索，便可以訪問到圖中所有的頂點。無向連通圖構成的條件是：邊數＝頂點數－1。

連通分量的提出是以＂整個無向圖不是連通圖＂為前提的，因為如果無向圖是連通圖，則其無法分解出多個最大連通子圖，因為圖中所有的頂點之間都是連通的。

(8)無向圖深度搜索演算法擴展閱讀：

無向圖到連通圖的tarjan演算法：

如果兩個頂點可以相互連接，則這兩個頂點是強連接的。如果有向圖G的每個頂點都是強連通的，則G是一個強連通圖。有向圖的強連通子圖是強連通分量。

在下面的圖中，子圖｛1，2，3，4｝是一個強連接組件，因為頂點1、2、3和4是不明確的。｛5｝和｛6｝也是兩個強連接的分量。

利用Tarjan演算法求有向圖的強連通分量。尋找有向圖強連通分量的Tarjan演算法是以其發明者RobertTarjan的名字命名的。RobertTarjan也發明了尋找雙連通分量的Tarjan演算法。

Tarjan演算法是基於圖深度優先搜索演算法的。每個強連接組件都是搜索樹中的一個子樹。在搜索過程中，將當前搜索樹中未處理的節點添加到堆棧中，並且可以追溯到堆棧頂部的節點，以確定它們是否是強連接組件。

定義DFN（u）為u查找的節點的序列號（時間戳），Low（u）為u或u的子樹可以跟蹤的最早棧中節點的序號。

當DFN（u）＝Low（u）時，以u為根的搜索子樹上所有節點是一個強連通分量。

⑼ 無向圖中求兩定點之間所有路徑。圖用二維數組存儲。最好用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 (1<<30)

// 標記可以到達的路徑長度
#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[start] = TRUE;

for(i=0;i<n;i++)
{
// 節點不在路徑中，且可以到達
if(isNodeUsed[i] == FALSE && map[start][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;j<tempPathsNum;j++)
{
// 在當前起點到達終點的所有路徑中，添加當前起點
tempPaths[j].nodes[tempPaths[j].size] = start;
tempPaths[j].size ++;

// 合並到最終的路徑中
paths[(*pathsNum)] = tempPaths[j];
(*pathsNum)++;
}
}
}
}
isNodeUsed[start] = 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;i<n;i++)
{
isNodeUsed[i] = FALSE;
for(j=0;j<n;j++)
{
map[i][j] = INFINTITY;
}
}

// 讀入路徑
for(i=0;i<m;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;i<pathsNum;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
*/

⑽ 無向圖中查找環的演算法有哪些

比較直觀的辦法是，從初始結點 S 開始，用深度優先的方法遍歷圖的結點，如果在這個過程中，你遇到了一個先前就已經發現過的結點（假定它叫 V），說明存在一個環。
如果你想輸出這個環，那麼就從 V 沿路返回，直到又遇到 V，途中經過的所有結點就組成了這個環。