給定一個圖，使用鄰接矩陣實現深度優先搜尋（DFS）遍歷的C程序-C++-PHP中文網

給定一個圖，使用鄰接矩陣實現深度優先搜尋（DFS）遍歷的C程序

WBOY

發布： 2023-08-28 16:01:06

轉載

839 人瀏覽過

給定一個圖，使用鄰接矩陣實現深度優先搜尋（DFS）遍歷的C程序

簡介

圖論使我們能夠研究和視覺化物件或實體之間的關係。在目前的電腦科學技術中，圖遍歷在探索和分析不同類型的資料結構中起著至關重要的作用。在圖上執行的關鍵操作之一是遍歷 - 遵循特定路徑訪問所有頂點或節點。基於深度優先方法的 DFS 遍歷允許我們在回溯和探索其他分支之前探索圖的深度。在本文中，我們將使用 C 語言的鄰接矩陣表示來實作 DFS 遍歷。

使用鄰接矩陣進行DFS遍歷

圖由兩個主要元件組成，即表示實體或元素的頂點或節點，以及連接這些頂點的邊，描述它們之間的關係。

表示加權或未加權圖中頂點之間關係的唯一方法是透過鄰接矩陣。它通常採用方陣的形式，其中行表示源頂點，列表示目標頂點，每個單元包含有關對應對之間的邊存在或權重的資訊。

範例

輸入是使用圖形的四個頂點透過一組特定元素給出的。輸入是：

登入後複製

設圖的起始頂點為 2。圖將從頂點「2」開始遍歷。頂點「2」的相鄰頂點顯然是1和3。由於起始頂點是2，因此在遍歷過程中不能再次存取它。頂點3在頂點2之後被訪問，那麼我們需要查看頂點3的鄰接頂點1和2。頂點1和頂點2已經被訪問過，遍歷停止。

方法 1：C 程序，包括使用鄰接矩陣作為給定圖中的輸入進行 DFS 遍歷

輸入是用某些數字定義的，並使用 for 迴圈它將迭代鄰接矩陣並傳回 DFS 遍歷。

演算法

第1 步：程式首先定義一個常數「MAX」來表示給定圖中的最大節點數，並初始化一個名為「visited」的陣列來追蹤特定節點是否存在遍歷期間已被訪問過。

第 2 步：“dfs()”函數將一個方形鄰接矩陣作為參數，“adjMatrix”代表我們的圖，頂點總數為“vCount”，起始頂點為`開始`。此函數對給定圖執行遞歸深度優先搜尋遍歷。

第3 步：在“dfs()”函數中，我們使用基於布林值的“visited[]”數組中的索引將每個當前處理的頂點標記為“已訪問” ，並相應地列印其值。

第 4 步：「dfs()」內部的循環遞歸地迭代當前節點的所有未訪問的鄰居，直到不可能獲得與其連接的頂點。

第5步：在main()中，我們使用巢狀循環讀取使用者的輸入，例如「vCount」的頂點數量及其對應的連接到鄰接矩陣。

第 6 步：然後，我們提示使用者輸入所需的起始頂點，然後將「visited[]」陣列的每個元素初始化為零（因為尚未存取任何節點）。

第7步：最後，程式使用適當的參數呼叫「dfs()」函數來啟動深度優先搜尋遍歷，並列印出DFS遍歷路徑。

範例

//Including the required header files
#include<stdio.h>
#define MAX 100

int visited[MAX];
//dfs function is defined with three arguments
void dfs(int adjMatrix[][MAX], int vCount, int start) {
   visited[start] = 1;
   printf("%d ", start);

   for(int i=0; i<vCount; i++) {
      if(adjMatrix[start][i] && !visited[i]) {
         dfs(adjMatrix,vCount,i);
      }
   }
}
//main function is used to implement the above functions
int main() {
   int adjMatrix[MAX][MAX];
   int vCount;

   // Assigning the variable with value of 4
   vCount = 4;

   // Assigning the adjacency matrix directly same the example given above
   adjMatrix[0][0] = 1;
   adjMatrix[0][1] = 0;
   adjMatrix[0][2] = 0;
   adjMatrix[0][3] = 1;
   adjMatrix[1][0] = 0;
   adjMatrix[1][1] = 1;
   adjMatrix[1][2] = 1;
   adjMatrix[1][3] = 0;
   adjMatrix[2][0] = 0;
   adjMatrix[2][1] = 1;
   adjMatrix[2][2] = 1;
   adjMatrix[2][3] = 0;
   adjMatrix[3][0] = 1;
   adjMatrix[3][1] = 0;
   adjMatrix[3][2] = 0;
   adjMatrix[3][3] = 1;
//Declaring the start variable as integer data type and later assigned with a value of 2
   int start;
   
   // Assigning the starting vertex directly
   start = 2;
   
   for(int i = 0; i < MAX; ++i) {
      visited[i] = 0;
   }

   printf("\nDFS Traversal: ");
   dfs(adjMatrix, vCount, start);
   

   return 0;
}

登入後複製