資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用C語言實現深度優先搜尋(DFS)
深度優先搜尋(DFS) 是一種遍歷圖並訪問所有節點然後再返回的演算法，它可以確定是否存在兩節點之間的路徑。
演算法
以下是深度優先搜尋(DFS)的實現演算法：
步驟1 − 初始棧為空。
步驟2 − 如果要訪問的節點不在棧中，則將其壓入棧中並標記為已訪問。
步驟3 − 然後，檢查當前節點是否與我們的搜尋條件匹配。
步驟3.1 − 如果匹配，則完成。
步驟4 − 否則，我們需要訪問當前節點的所有相鄰節點。
步驟4.1 − 然後以任意順序訪問所有這些型別的節點，並繼續搜尋。
步驟5 − 如果所有相鄰節點都已訪問，則成為死衚衕。
步驟6 − 我們返回到先前訪問的節點，並將最近的節點從棧中彈出。
步驟7 − 如果所有節點都已搜尋完畢，或者我們得到答案，則演算法終止。
深度優先搜尋(DFS)的C語言程式實現
以下是深度優先搜尋(DFS)的C語言程式實現：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
void addVertex(char);
void addEdge(int, int);
void displayVertex(int);
void depthFirstSearch();
int getAdjUnvisitedVertex(int);
struct Vertex {
char label;
bool visited;
};
//stack variables
int stack[MAX];
int top = -1;
//graph variables
//array of vertices
struct Vertex * lstVertices[MAX];
//adjacency matrix
int adjMatrix[MAX][MAX];
//vertex count
int vertexCount = 0;
//stack functions
void push(int item) {
stack[++top] = item;
}
int pop() {
return stack[top--];
}
int peek() {
return stack[top];
}
bool isStackEmpty() {
return top == -1;
}
//graph functions
//add vertex to the vertex list
void addVertex(char label) {
struct Vertex * vertex = (struct Vertex * ) malloc(sizeof(struct Vertex));
vertex -> label = label;
vertex -> visited = false;
lstVertices[vertexCount++] = vertex;
}
//add edge to edge array
void addEdge(int start, int end) {
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
//display the vertex
void displayVertex(int vertexIndex) {
printf("%c ", lstVertices[vertexIndex] -> label);
}
//get the adjacent unvisited vertex
int getAdjUnvisitedVertex(int vertexIndex) {
int i;
for (i = 0; i < vertexCount; i++) {
if (adjMatrix[vertexIndex][i] == 1 && lstVertices[i] -> visited == false) {
return i;
}
}
return -1;
}
void depthFirstSearch() {
int i;
//mark first node as visited
lstVertices[0] -> visited = true;
//display the vertex
displayVertex(0);
//push vertex index in stack
push(0);
while (!isStackEmpty()) {
//get the unvisited vertex of vertex which is at top of the stack
int unvisitedVertex = getAdjUnvisitedVertex(peek());
//no adjacent vertex found
if (unvisitedVertex == -1) {
pop();
} else {
lstVertices[unvisitedVertex] -> visited = true;
displayVertex(unvisitedVertex);
push(unvisitedVertex);
}
}
//stack is empty, search is complete, reset the visited flag
for (i = 0; i < vertexCount; i++) {
lstVertices[i] -> visited = false;
}
}
int main() {
int i, j;
for (i = 0; i < MAX; i++) // set adjacency {
for (j = 0; j < MAX; j++) // matrix to 0
adjMatrix[i][j] = 0;
addVertex('S'); // 0
addVertex('A'); // 1
addVertex('B'); // 2
addVertex('C'); // 3
addVertex('D'); // 4
addEdge(0, 1); // S - A
addEdge(0, 2); // S - B
addEdge(0, 3); // S - C
addEdge(1, 4); // A - D
addEdge(2, 4); // B - D
addEdge(3, 4); // C - D
printf("Depth First Search: ");
depthFirstSearch();
return 0;
}
輸出
執行上述程式後，會產生以下結果：
Depth First Search: S A D B C
更新於：2024年6月25日
6K+ 次瀏覽
廣告