C++深度遍历

C++深度遍历 //#include "stdafx.h" #include <iostream> using namespace std; #define MAX_VERTEX_NUM typedef struct ArcNode { int adjVex; struct ArcNode *nextArc; }ArcNode; typedef struct VNode { Based on the given title, description, tags, and partial content, we can extract several important C++ concepts and knowledge points related to graph theory and depth-first search (DFS). Below is a detailed breakdown of these concepts: ### 1. Depth-First Search (DFS) in Graph Theory **Definition:** DFS is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. **Key Points:** - **Recursion:** DFS often uses recursion to traverse through the nodes. - **Stack:** DFS can also be implemented using a stack data structure. - **Traversal Order:** DFS visits vertices in a depthward motion and uses a stack to remember to get back to visited vertices. ### 2. Implementation of DFS in C++ **Data Structures Used:** - **Adjacency List:** The given code uses an adjacency list to represent the graph. An adjacency list is a collection of unordered lists used to represent a finite graph. - **Vertex Node (VNode):** Represents a vertex in the graph. - **Arc Node (ArcNode):** Represents an edge connecting two vertices. **Code Explanation:** #### Vertex Node (VNode) ```cpp typedef struct VNode { char data; ArcNode* firstArc; } VNode, AdjList[MAX_VERTEX_NUM]; ``` - **`char data`:** Stores the label or data associated with the vertex. - **`ArcNode* firstArc`:** Pointer to the first arc (edge) connected to this vertex. #### Arc Node (ArcNode) ```cpp typedef struct ArcNode { int adjVex; struct ArcNode *nextArc; } ArcNode; ``` - **`int adjVex`:** Index of the adjacent vertex. - **`struct ArcNode *nextArc`:** Pointer to the next arc (edge) in the adjacency list. #### Graph Structure (AlGraph) ```cpp typedef struct AlGraph { AdjList vertices; int vexnum, arcnum; } AlGraph; ``` - **`AdjList vertices`:** Array of vertex nodes representing all vertices in the graph. - **`int vexnum`:** Number of vertices in the graph. - **`int arcnum`:** Number of edges in the graph. #### DFS Function ```cpp void DFS(AlGraph G, int v) { G.vertices[v].visit = true; cout << G.vertices[v].data << ""; for (int w = FirstAdjVex(G, v); w != 0; w = NextAdjVex(G, v, w)) { if (!G.vertices[w].visit) { DFS(G, w); } } } ``` - **Parameters:** - `AlGraph G`: The graph to traverse. - `int v`: The starting vertex index. - **Functionality:** - Marks the current vertex as visited. - Prints the data of the current vertex. - Recursively calls `DFS` for all unvisited adjacent vertices. ### 3. Example Code Explanation The provided code snippet initializes a graph and performs a depth-first search. #### Initialization ```cpp int a[6][6] = { {0, 1, 0, 0, 1, 0}, {1, 0, 0, 0, 1, 1}, {0, 0, 0, 1, 0, 1}, {0, 0, 1, 0, 0, 1}, {1, 1, 0, 0, 0, 0}, {0, 1, 1, 1, 0, 0} }; AlGraph G; G.arcnum = 7; G.vexnum = 6; for (int i = 0; i < 6; i++) { G.vertices[i].data = 65 + i; ArcNode* head = new ArcNode(); head->nextArc = NULL; for (int j = 5; j >= 0; j--) { if (a[i][j] == 1) { ArcNode* p = new ArcNode(); p->adjvex = j; p->nextArc = head->nextArc; head->nextArc = p; } } G.vertices[i].firstArc = head->nextArc; } ``` - **Graph Representation:** - Uses a 2D array `a` to represent the adjacency matrix of the graph. - Initializes the `AlGraph` structure `G`. - **Edge Construction:** - For each vertex `i`, creates an adjacency list by adding edges pointed to by `p`. - Links the edges in reverse order to ensure the first inserted edge is the first one in the list. ### Conclusion This C++ code demonstrates the implementation of depth-first search using an adjacency list representation of a graph. It covers important aspects such as the use of data structures like `ArcNode` and `VNode`, and the recursive nature of DFS. Understanding these concepts is crucial for anyone working with graphs and algorithms in C++.