遍歷被訪問圖

❶ 對連通圖進行一次先深遍歷可訪問圖的全部頂點,對嗎

圖的遍歷從圖中某一頂點出發,按某種搜索方法訪遍其餘頂點,且使每一頂點僅被訪問一次.這一過程稱為圖的遍歷.遍歷圖的基本搜索方法有兩種：深度優先搜索DFS（Depth First Search）和廣度優先搜索BFS（Broad Fi...

❷ 遍歷的圖

（Depth-First Traversal)
圖的深度優先遍歷的遞歸定義：
假設給定圖G的初態是所有頂點均未曾訪問過。在G中任選一頂點v為初始出發點（源點），則深度優先遍歷可定義如下：首先訪問出發點v，並將其標記為已訪問過；然後依次從v出發搜索v的每個鄰接點w。若w未曾訪問過，則以w為新的出發點繼續進行深度優先遍歷，直至圖中所有和源點v有路徑相通的頂點（亦稱為從源點可達的頂點）均已被訪問為止。若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。
圖的深度優先遍歷類似於樹的前序遍歷。採用的搜索方法的特點是盡可能先對縱深方向進行搜索。這種搜索方法稱為深度優先搜索(Depth-First Search）。相應地，用此方法遍歷圖就很自然地稱之為圖的深度優先遍歷。
深度優先搜索的過程
設x是當前被訪問頂點，在對x做過訪問標記後，選擇一條從x出發的未檢測過的邊（x，y）。若發現頂點y已訪問過，則重新選擇另一條從x出發的未檢測過的邊，否則沿邊（x，y）到達未曾訪問過的y，對y訪問並將其標記為已訪問過；然後從y開始搜索，直到搜索完從y出發的所有路徑，即訪問完所有從y出發可達的頂點之後，才回溯到頂點x，並且再選擇一條從x出發的未檢測過的邊。上述過程直至從x出發的所有邊都已檢測過為止。此時，若x不是源點，則回溯到在x之前被訪問過的頂點；否則圖中所有和源點有路徑相通的頂點（即從源點可達的所有頂點）都已被訪問過，若圖G是連通圖，則遍歷過程結束，否則繼續選擇一個尚未被訪問的頂點作為新源點，進行新的搜索過程。
演算法實現 plate<intmax_size>voidDigraph<max_size>::depth_first(void(*visit)(Vertex&))const/*Post:Thefunction*-firstorder.Uses:-firstorder.*/{boolvisited[max_size];Vertexv;for(allvinG)visited[v]=false;for(allvinG)if(!visited[v])traverse(v,visited,visit);}template<intmax_size>voidDigraph<max_size>::traverse(Vertex&v,boolvisited[],void(*visit)(Vertex&))const/*Pre:visavertexoftheDigraph.Post:Thedepth-firsttraversal,usingfunction*visit,.Uses:traverserecursively.*/{Vertexw;visited[v]=true;（*visit)(v);for(allwadjacenttov)if(!visited[w])traverse(w,visited,visit);} （Width-First Traversal）
基本思想
1、從圖中某個頂點V0出發，並訪問此頂點；
2、從V0出發，訪問V0的各個未曾訪問的鄰接點W1，W2，…，Wk；然後，依次從W1,W2，…，Wk出發訪問各自未被訪問的鄰接點；
3、重復步驟2，直到全部頂點都被訪問為止。
廣度優先遍歷的性質
與深度優先遍歷類似，廣度優先遍歷也有許多有用的特性：
1、廣度優先生成樹
在廣度優先遍歷中，如果將每次「前進」（縱深）路過的（將被訪問的）結點和邊都記錄下來，就得到一個子圖，該子圖為以出發點為根的樹，稱為廣度優先生成樹。這種情況與深度優先遍歷類似。
類似地，也可以給廣度優先生成樹結點定義時間戳。
2、最短路徑
顯然，從v0出發廣度優先遍歷圖，將得到v0到它的各個可達到的路徑。我們這里定義路徑上的邊的數目為路徑長度。與深度優先遍歷不同，廣度優先遍歷得到的v0到各點的路徑是最短路徑（未考慮邊權）。
演算法實現 template<intmax_size>voidDigraph<max_size>::breadth_first(void(*visit)(Vertex&))const/*Post:Thefunction*-firstorder.Uses:MethodsofclassQueue.*/{Queueq;boolvisited[max_size];Vertexv,w,x;for(allvinG)visited[v]=false;for(allvinG)if(!visited[v]){q.append(v);while(!q.empty()){q.retrieve(w);if(!visited[w]){visited[w]=true;(*visit)(w);for(allxadjacenttow)q.append(x);}q.serve();}}}與深度優先遍歷的比較
廣度優先遍歷與深度優先遍歷的區別在於：廣度優先遍歷是以層為順序，將某一層上的所有節點都搜索到了之後才向下一層搜索；而深度優先遍歷是將某一條枝椏上的所有節點都搜索到了之後，才轉向搜索另一條枝椏上的所有節點。
深度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出剛訪問這個結點的第一個未被訪問的鄰結點，然後再以此鄰結點為頂點，繼續找它的下一個新的頂點進行訪問，重復此步驟，直到所有結點都被訪問完為止。
廣度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出這個結點的所有未被訪問的鄰接點，訪問完後再訪問這些結點中第一個鄰接點的所有結點，重復此方法，直到所有結點都被訪問完為止。
可以看到兩種方法最大的區別在於前者從頂點的第一個鄰接點一直訪問下去再訪問頂點的第二個鄰接點；後者從頂點開始訪問該頂點的所有鄰接點再依次向下，一層一層的訪問。

❸ 對連通圖進行一次先深遍歷可訪問圖的全部頂點，對嗎

如果是無向的連通圖或者有向的強連通圖,是對的,對於無向的非連通圖就不可能一次遍歷訪問到所有頂點了,對於有向的非強連通圖則有可能對,有可能不對

❹ 圖的遍歷方法主要包括

圖的遍歷方法主要包括深度優先搜索法和廣度（寬度）優先搜索法兩種演算法。

廣度優先遍歷（Breadth First Search），又稱為廣度優先搜索，簡稱BFS。深度優化遍歷(Depth First Search)，也有稱為深度優化搜索，簡稱為DFS。事實上，我們在樹的遍歷中早已涉及DFS，層序遍歷、中序遍歷和後序遍歷都屬於深度優先遍歷的方式，因為這些遍歷方式本質上都歸結於棧。

圖的遍歷方法復雜性介紹

① 在圖結構中，沒有一個「自然」的首結點，圖中任意一個頂點都可作為第一個被訪問的結點。

② 在非連通圖中，從一個頂點出發，只能夠訪問它所在的連通分量上的所有頂點，因此，還需考慮如何選取下一個出發點以訪問圖中其餘的連通分量。

③ 在圖結構中，如果有迴路存在，那麼一個頂點被訪問之後，有可能沿迴路又回到該頂點。

④ 在圖結構中，一個頂點可以和其它多個頂點相連，當這樣的頂點訪問過後，存在如何選取下一個要訪問的頂點的問題。

❺ 圖遍歷演算法之DFS/BFS

在計算機科學， 圖遍歷（Tree Traversal，也稱圖搜索）是一系列圖搜索的演算法， 是單次訪問樹結構類型數據（tree data structure)中每個節點以便檢查或更新的一系列機制。圖遍歷演算法可以按照節點訪問順序進行分類，根據訪問目的或使用場景的不同，演算法大致可分為28種：

圖遍歷即以特定方式訪問圖中所有節點，給定節點下有多種可能的搜索路徑。假定以順序方式進行（非並行），還未訪問的節點就需通過堆棧（LIFO）或隊列（FIFO）規則來確定訪問先後。由於樹結構是一種遞歸的數據結構，在清晰的定義下，未訪問節點可存儲在調用堆棧中。本文介紹了圖遍歷領域最流行的廣度優先搜索演算法BFS和深度優先搜索演算法DFS，對其原理、應用及實現進行了闡述。通常意義上而言，深度優先搜索（DFS）通過遞歸調用堆棧比較容易實現，廣義優先搜索通過隊列實現。

深度優先搜索（DFS）是用於遍歷或搜索圖數據結構的演算法，該演算法從根節點開始（圖搜索時可選擇任意節點作為根節點）沿著每個分支進行搜索，分支搜索結束後在進行回溯。在進入下一節點之前，樹的搜索盡可能的加深。
DFS的搜索演算法如下（以二叉樹為例）：假定根節點（圖的任意節點可作為根節點）標記為 ,
(L) : 遞歸遍歷左子樹，並在節點 結束。
(R): 遞歸遍歷右子樹，並在節點 結束。
(N): 訪問節點 。
這些步驟可以以任意次序排列。如果（L）在（R）之前，則該過程稱為從左到右的遍歷；反之，則稱為從右到左的遍歷。根據訪問次序的不同，深度優先搜索可分為 pre-order、in-order、out-order以及post-order遍歷方式。

（a）檢查當前節點是否為空；
（b）展示根節點或當前節點數據；
（c）遞歸調用pre-order函數遍歷左子樹；
（d）遞歸調用pre-order函數遍歷右子樹。
pre-order遍歷屬於拓撲排序後的遍歷，父節點總是在任何子節點之前被訪問。該遍歷方式的圖示如下：

遍歷次序依次為：F -B -A-D- C-E-G- I-H.

（a）檢查當前節點是否為空；
（b）遞歸調用in-order函數遍歷左子樹；
（c）展示根節點或當前節點數據；
（d）遞歸調用in-order函數遍歷右子樹。
在二叉樹搜索中，in-order遍歷以排序順序訪問節點數據。該遍歷方式的圖示如下：

遍歷次序依次為：A -B - C - D - E - F - G -H-I

（a）檢查當前節點是否為空；
（b）遞歸調用out-order函數遍歷右子樹；
（c）展示根節點或當前節點數據；
（d）遞歸調用out-order函數遍歷左子樹。
該遍歷方式與LNR類似，但先遍歷右子樹後遍歷左子樹。仍然以圖2為例，遍歷次序依次為：H- I-G- F- B- E- D- C- A.

（a）檢查當前節點是否為空；
（b）遞歸調用post-order函數遍歷左子樹；
（c）遞歸調用post-order函數遍歷右子樹；
（d）展示根節點或當前節點數據。
post-order遍歷圖示如下：

遍歷次序依次為：A-C-E-D-B-H-I-G-F.

pre-order遍歷方式使用場景：用於創建樹或圖的副本；
in-order遍歷使用場景：二叉樹遍歷；
post-order遍歷使用場景：刪除樹

遍歷追蹤也稱樹的序列化，是所訪問根節點列表。無論是pre-order，in-order或是post-order都無法完整的描述樹特性。給定含有不同元素的樹結構，pre-order或post-order與in-order遍歷方式結合起來使用才可以描述樹的獨特性。

樹或圖形的訪問也可以按照節點所處的級別進行遍歷。在每次訪問下一層級節點之前，遍歷所在高層級的所有節點。BFS從根節點（圖的任意節點可作為根節點）出發，在移動到下一節點之前訪問所有相同深度水平的相鄰節點。

BFS的遍歷方法圖示如下：

遍歷次序依次為： F-B-G-A-D-I-C-E-H.

圖演算法相關的R包為igraph，主要包括圖的生成、圖計算等一系列演算法的實現。

使用方法：

參數說明：

示例：

結果展示：

DFS R輸出節點排序：

使用方法：

參數含義同dfs
示例：

結果展示：

BFS R輸出節點排序：

以尋找兩點之間的路徑為例，分別展示BFS及DFS的實現。圖示例如下：

示例：

輸出結果：

示例：

輸出結果：

[1] 維基網路： https://en.wikipedia.org/wiki/Tree_traversal
[2] GeeksforGeeks: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
[3] http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html
[4]Martin Broadhurst, Graph Algorithm: http://www.martinbroadhurst.com/Graph-algorithms.html#section_1_1
[5]igraph: https://igraph.org/r/doc/dfs.html
[6]igraph: https://igraph.org/r/doc/bfs.html
[7] Depth-First Search and Breadth-First Search in python: https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/

❻ 用C語言編程實現圖的遍歷演算法

圖的遍歷是指按某條搜索路徑訪問圖中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。圖的遍歷有深度遍歷演算法和廣度遍歷演算法，最近阿傑做了關於圖的遍歷的演算法，下面是圖的遍歷深度優先的演算法（C語言程序）：
#include<stdio.h>
#include<malloc.h>
#define MaxVertexNum 5
#define m 5
#define TRUE 1
#define NULL 0
typedef struct node
{
int adjvex;
struct node *next;
}JD;
typedef struct EdgeNode
{
int vexdata;
JD *firstarc;
}TD;
typedef struct
{
TD ag[m];
int n;
}ALGRAPH;
void DFS(ALGRAPH *G,int i)
{
JD *p;
int visited[80];
printf("visit vertex:%d->",G->ag[i].vexdata);
visited[i]=1;
p=G->ag[i].firstarc;
while(p)
{
if (!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
void creat(ALGRAPH *G)
{
int i,m1,j;
JD *p,*p1;
printf("please input the number of graph\n");
scanf("%d",&G->n);
for(i=0;i<G->n;i++)
{
printf("please input the info of node %d",i);
scanf("%d",&G->ag[i].vexdata);
printf("please input the number of arcs which adj to %d",i);
scanf("%d",&m1);
printf("please input the adjvex position of the first arc\n");
p=(JD *)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
G->ag[i].firstarc=p;
p1=p;
for(j=2 ;j<=m1;j++)
{
printf("please input the position of the next arc vexdata\n");
p=(JD *)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
p1->next=p;
p1=p;
}
}
}
int visited[MaxVertexNum];
void DFSTraverse(ALGRAPH *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=0;
for(i=0;i<G->n;i++)
if(!visited[i])
DFS(G,i);
}
int main()
{
ALGRAPH *G;
printf("下面以臨接表存儲一個圖；\n");
creat(G);
printf("下面以深度優先遍歷該圖 \n");
DFSTraverse(G);
getchar();
}

❼ 圖的圖的遍歷

常見的圖遍歷方式有兩種：深度優先遍歷和廣度優先遍歷，這兩種遍歷方式對有向圖和無向圖均適用。 深度優先遍歷的思想類似於樹的先序遍歷。其遍歷過程可以描述為：從圖中某個頂點v出發，訪問該頂點，然後依次從v的未被訪問的鄰接點出發繼續深度優先遍歷圖中的其餘頂點，直至圖中所有與v有路徑相通的頂點都被訪問完為止。
深度優先遍歷演算法實現：
為了便於在演算法中區分頂點是否已被訪問過，需要創建一個一維數組visited[0..n-1]（n是圖中頂點的數目），用來設置訪問標志，其初始值visited（0≤i≤n-1）為"0"，表示鄰接表中下標值為i的頂點沒有被訪問過，一旦該頂點被訪問，將visited置成"1"。
int visited[0..n-1]={0,0,...0};
void DFS(AdjList adj,int v)
{//v是遍歷起始點的在鄰接表中的下標值，其下標從0開始
visited[v]=1; visited(adj[v].elem);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) DFS(adj,w->adjvex);
}
對於無向圖，這個演算法可以遍歷到v頂點所在的連通分量中的所有頂點，而與v頂點不在一個連通分量中的所有頂點遍歷不到；而對於有向圖可以遍歷到起始頂點v能夠到達的所有頂點。若希望遍歷到圖中的所有頂點，就需要在上述深度優先遍歷演算法的基礎上，增加對每個頂點訪問狀態的檢測： intvisited[0..n-1]={0,0,...0};voidDFSTraverse(AdjListadj){for(v=0;v<n;v++)if(!visited[v])DFS(adj,v);} 對圖的廣度優先遍歷方法描述為：從圖中某個頂點v出發，在訪問該頂點v之後，依次訪問v的所有未被訪問過的鄰接點，然後再訪問每個鄰接點的鄰接點，且訪問順序應保持先被訪問的頂點其鄰接點也優先被訪問，直到圖中的所有頂點都被訪問為止。下面是對一個無向圖進行廣度優先遍歷的過程。
下面我們討論一下實現廣度優先遍歷演算法需要考慮的幾個問題：
（1）在廣度優先遍歷中，要求先被訪問的頂點其鄰接點也被優先訪問，因此，必須對每個頂點的訪問順序進行記錄，以便後面按此順序訪問各頂點的鄰接點。應利用一個隊列結構記錄頂點訪問順序，就可以利用隊列結構的操作特點，將訪問的每個頂點入隊，然後，再依次出隊，並訪問它們的鄰接點；
（2）在廣度優先遍歷過程中同深度優先遍歷一樣，為了避免重復訪問某個頂點，也需要創建一個一維數組visited[0..n-1]（n是圖中頂點的數目），用來記錄每個頂點是否已經被訪問過。
int visited[0..n-1]={0,0,...0};
void BFS(AdjList adj,int v)
{//v是遍歷起始點在鄰接表中的下標，鄰接表中下標從0開始
InitQueue(Q); //Q是隊列
visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);
while (!QueueEmpty(Q)) {
DeQueue(Q,v);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) {
visited[w->adjvex]=1;
visite(adj[w->adjvex].elem);
EnQueue(Q,w->adjvex); }
}
}

❽ 使用圖遍歷的方法判斷一個圖是否連通，其判斷依據是

採用圖的深度遍歷法，從其中一個結點v出發，直至所有與v有路徑相通的結點都被訪問到。若此時圖中所有點都被訪問過，則該圖是連通圖，反之，說明還有其他連通分量，該圖不是一個連通圖。

❾ 圖遍歷的演算法

圖的遍歷方法目前有深度優先搜索法和廣度（寬度）優先搜索法兩種演算法。 深度優先搜索法是樹的先根遍歷的推廣，它的基本思想是：從圖G的某個頂點v0出發，訪問v0，然後選擇一個與v0相鄰且沒被訪問過的頂點vi訪問，再從vi出發選擇一個與vi相鄰且未被訪問的頂點vj進行訪問，依次繼續。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則退回到已被訪問的頂點序列中最後一個擁有未被訪問的相鄰頂點的頂點w，從w出發按同樣的方法向前遍歷，直到圖中所有頂點都被訪問。其遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void DFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //訪問標志數組初始化
for(v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v); //對尚未訪問的頂點調用DFS
}
void DFS(Graph G, int v){ //從第v個頂點出發遞歸地深度優先遍歷圖G
visited[v]=TRUE; VisitFunc(v); //訪問第v個頂點
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一個鄰接頂點，若頂點在G中沒有鄰接頂點，則返回空（0）。
//若w是v的鄰接頂點，NextAdjVex返回v的（相對於w的）下一個鄰接頂點。
//若w是v的最後一個鄰接點，則返回空（0）。
if(!visited[w])
DFS(G, w); //對v的尚未訪問的鄰接頂點w調用DFS
} 圖的廣度優先搜索是樹的按層次遍歷的推廣，它的基本思想是：首先訪問初始點vi，並將其標記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點vi1,vi2,…, vi t，並均標記已訪問過，然後再按照vi1,vi2,…, vi t的次序，訪問每一個頂點的所有未被訪問過的鄰接點，並均標記為已訪問過，依次類推，直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。其非遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void BFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空輔助隊列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入隊列
while(!QueueEmpty(Q)){
DeQueue(Q, u); //隊頭元素出隊並置為u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!Visited[w]){ //w為u的尚未訪問的鄰接頂點
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}