資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用鄰接矩陣在給定圖中實現 DFS 遍歷的 C 程式
簡介
圖論使我們能夠研究和視覺化物件或實體之間的關係。在當前的計算機科學技術中，圖遍歷在探索和分析不同型別的資料結構方面發揮著至關重要的作用。圖上執行的關鍵操作之一是遍歷——訪問所有頂點或節點，遵循特定的路徑。基於深度優先的方法的 DFS 遍歷允許我們在回溯和探索其他分支之前探索圖的深度。在本文中，我們將涉及使用 C 語言中的鄰接矩陣表示法實現 DFS 遍歷。
使用鄰接矩陣的 DFS 遍歷
圖由兩個主要組成部分組成，即表示實體或元素的頂點或節點，以及連線這些頂點的邊，描繪它們之間的關係。
在加權或非加權圖中表示頂點之間關係的唯一方法是鄰接矩陣。它通常採用方陣的形式，其中行表示源頂點，列表示目標頂點，每個單元格包含有關對應對之間邊存在或權重的資訊。
示例
輸入使用圖的四個頂點給定一組特定的元素。輸入為
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
並設圖的起始頂點為 2。圖將從頂點“2”開始遍歷。頂點“2”的相鄰頂點顯然是 1 和 3。由於起始頂點為 2，因此在遍歷期間不能再次訪問它。在頂點 2 之後訪問頂點 3，然後我們需要檢視頂點 3 的相鄰頂點，它們是 1 和 2。頂點 1 和頂點 2 已經被訪問過，遍歷停止。
方法 1：包含使用鄰接矩陣作為輸入在給定圖中進行 DFS 遍歷的 C 程式
輸入使用某些數字定義，並且使用 for 迴圈，它將遍歷鄰接矩陣並返回 DFS 遍歷。
演算法
步驟 1：程式首先定義一個常量 `MAX` 來表示給定圖中節點的最大數量，並初始化一個名為 `visited` 的陣列，以跟蹤在遍歷期間是否已訪問特定節點。
步驟 2：'dfs()' 函式的引數為一個方形鄰接矩陣作為 `adjMatrix`，表示我們的圖，頂點的總數為 'vCount'，以及起始頂點為 `start`。此函式對給定圖執行遞迴深度優先搜尋遍歷。
步驟 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;
}
輸出
DFS Traversal: 2 1
結論
透過使用鄰接矩陣作為圖的表示，我們可以有效地在大型或複雜的資料集上執行 DFS。在本文中，我們詳細解釋並提供了一個 C 程式，該程式使用基於鄰接矩陣的表示法實現了深度優先搜尋遍歷。深度優先搜尋是一種用於探索和分析圖結構的強大演算法。
4K+ 次檢視
