图的深度优先遍历问题
分别用邻接矩阵和邻接链表两种数据结构实现图的深度优先遍历算法，输出遍历的结点序列，并分析算法的时间复杂度。
提交格式：
邻接矩阵数据结构实现void solveA(int n, int m, int e[][2], int out[])函数。
邻接链表数据结构实现void solveB(int n, int m, int e[][2], int out[])函数。
参数n为结点个数，m为边条数，e为所有边，out为输出序列。1<=n<=3000,1<=m<=100000,0<=e[i][j]
请不要printf输出任何内容。
输入样例：
n=5,m=10,e={{2,4},{3,0},{0,2},{3,1},{4,1},{0,1},{3,4},{2,3},{1,2},{0,4}}
输出样例：
solveA：out={0,1,2,3,4}
solveB：out={0,3,1,4,2}
void solveA(int n, int m, int e[][2], int out[]) {
// 建立邻接矩阵
int adjacencyMatrix[n][n];
memset(adjacencyMatrix, 0, sizeof(adjacencyMatrix));
for (int i = 0; i < m; i++) {
adjacencyMatrix[e[i][0]][e[i][1]] = 1;
adjacencyMatrix[e[i][1]][e[i][0]] = 1;
}
// 初始化访问标记数组
int visited[n];
memset(visited, 0, sizeof(visited));
// 初始化输出序列的下标
int index = 0;
// 从结点0开始深度优先遍历
dfsA(0, n, adjacencyMatrix, visited, out, &index);
}
void dfsA(int u, int n, int adjacencyMatrix[][n], int visited[], int out[], int *index) {
// 标记结点u已访问
visited[u] = 1;
// 将结点u加入输出序列
out[(*index)++] = u;
// 遍历结点u的所有邻居结点
for (int v = 0; v < n; v++) {
if (adjacencyMatrix[u][v] && !visited[v]) {
dfsA(v, n, adjacencyMatrix, visited, out, index);
}
}
}
void solveB(int n, int m, int e[][2], int out[]) {
Graph *graph = createGraph(n, m, e);
// 初始化访问标记数组
int visited[n];
memset(visited, 0, sizeof(visited));
// 初始化输出序列的下标
int index = 0;
// 从结点0开始深度优先遍历
dfsB(graph, 0, visited, out, &index);
freeGraph(graph);
}
void dfsB(Graph *graph, int u, int visited[], int out[], int *index) {
// 标记结点u已访问
visited[u] = 1;
// 将结点u加入输出序列
out[(*index)++] = u;
// 遍历结点u的所有邻居结点
ListNode *curr = graph->adj[u];
while (curr) {
int v = curr->val;
if (!visited[v]) {
dfsB(graph, v, visited, out, index);
}
curr = curr->next;
}
}
下面是使用邻接矩阵和邻接链表两种数据结构实现图的深度优先遍历算法的代码：
邻接矩阵数据结构实现：
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 3001
int n, m;
int e[MAX_N][MAX_N];
int visited[MAX_N];
int out[MAX_N];
int out_index;
void dfs(int u) {
visited[u] = 1;
out[out_index++] = u;
for (int v = 0; v < n; v++) {
if (e[u][v] && !visited[v]) {
dfs(v);
}
}
}
void solveA(int n, int m, int e[][2], int out[]) {
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
out_index = 0;
dfs(0);
}
int main() {
n = 5;
m = 10;
int edges[][2] = {{2, 4}, {3, 0}, {0, 2}, {3, 1}, {4, 1}, {0, 1}, {3, 4}, {2, 3}, {1, 2}, {0, 4}};
for (int i = 0; i < m; i++) {
int u = edges[i][0];
int v = edges[i][1];
e[u][v] = e[v][u] = 1;
}
solveA(n, m, edges, out);
for (int i = 0; i < n; i++) {
printf("%d ", out[i]);
}
printf("\n");
return 0;
}
邻接链表数据结构实现：
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 3001
typedef struct node {
int v;
struct node* next;
} Node;
int n, m;
Node* head[MAX_N];
int visited[MAX_N];
int out[MAX_N];
int out_index;
void dfs(int u) {
visited[u] = 1;
out[out_index++] = u;
Node* cur = head[u];
while (cur != NULL) {
int v = cur->v;
if (!visited[v]) {
dfs(v);
}
cur = cur->next;
}
}
void solveB(int n, int m, int e[][2], int out[]) {
for (int i = 0; i < n; i++) {
head[i] = NULL;
visited[i] = 0;
}
out_index = 0;
for (int i = 0; i < m; i++) {
int u = e[i][0];
int v = e[i][1];
Node* u_node = (Node*)malloc(sizeof(Node));
u_node->v = v;
u_node->next = head[u];
head[u] = u_node;
Node* v_node = (Node*)malloc(sizeof(Node));
v_node->v = u;
v_node->next = head[v];
head[v] = v_node;
}
dfs(0);
}
int main() {
n = 5;
m = 10;
int edges[][2] = {{2, 4}, {3, 0}, {0, 2}, {3, 1}, {4, 1}, {0, 1}, {3, 4}, {2, 3}, {1, 2}, {0, 4}};
solveB(n, m, edges, out);
for (int i = 0; i < n; i++) {
printf("%d ", out[i]);
}
printf("\n");
return 0;
}
时间复杂度分析：
邻接矩阵：对于每个结点，每次都要遍历所有的邻居结点，时间复杂度为 O(n^2)。
邻接链表：对于每个结点，每次只遍历该结点的邻居结点，时间复杂度为 O(m)。
因此，在稠密图（即每个结点的度都很大）的情况下，使用邻接矩阵的方式更加高效；在稀疏图（即每个结点的度都很小）的情况下，使用邻接链表的方式更加高效。
邻接矩阵数据结构实现的深度优先遍历如下：
void solveA(int n, int m, int e[][2], int out[]) {
// 初始化邻接矩阵和访问标记数组
int matrix[n][n];
memset(matrix, 0, sizeof(matrix));
bool visited[n];
memset(visited, 0, sizeof(visited));
// 建立邻接矩阵
for (int i = 0; i < m; i++) {
int u = e[i][0], v = e[i][1];
matrix[u][v] = 1;
matrix[v][u] = 1;
}
// 从结点0开始深度优先遍历
dfsA(0, matrix, visited, out, 0);
}
// 深度优先遍历
void dfsA(int u, int matrix[][n], bool visited[], int out[], int& index) {
// 标记当前结点已访问
visited[u] = true;
// 将当前结点加入遍历序列
out[index++] = u;
// 遍历当前结点的邻居结点
for (int v = 0; v < n; v++) {
if (matrix[u][v] == 1 && !visited[v]) {
// 如果当前结点与v有连边且v未被访问，则递归访问v
dfsA(v, matrix, visited, out, index);
}
}
}
邻接链表数据结构实现的深度优先遍历如下：
struct Node {
int v;
Node* next;
Node(int
#include <iostream>
using namespace std;
#define MaxInt 32767 //表示极大值
#define MVNum 100 //最大顶点数
#define OK 1
typedef char VerTexType;//顶点数据类型为字符型
typedef int ArcType;//权值为整形
typedef int Status;//定义返回值类型
//定义结构体
typedef struct{
//顶点表
VerTexType vexs[MVNum];
//邻接矩阵
ArcType arcs[MVNum][MVNum];
//当前顶点数和边数
int vexnum,arcnum;
}AMGraph;
//确定顶点位置
Status LocateVer(AMGraph G,VerTexType v){
for (int i = 0; i < G.vexnum; ++i) {
if (G.vexs[i]==v){
return i;
}
}
return -1;
}
//采用邻接矩阵创建无向图
Status CreateUDN(AMGraph &G){
int i,j,k;
//输入总顶点数和总边数
// cout<<"please input the vexnum and the arcnum:"<<endl;
cout<<"————————输入总顶点数和总边数————————"<<endl;
cin>>G.vexnum;
cin>>G.arcnum;
//依次输入点的信息存入顶点表中
cout<<"——————依次输入点的信息存入顶点表中——————"<<endl;
for ( i = 0; i < G.vexnum; ++i) {
cin>>G.vexs[i] ;
}
//初始化邻接矩阵，使每个权值初始化为最大值
cout<<"———初始化邻接矩阵，使每个权值初始化为最大值———"<<endl;
for (i = 0; i < G.vexnum; ++i) {
for ( j = 0; j < G.vexnum; ++j) {
G.arcs[i][j]=MaxInt;
}
}
//构造邻接矩阵,依次输入每条边依附的顶点和权值
cout<<"——构造邻接矩阵,依次输入每条边依附的顶点和权值——"<<endl;
for ( k = 0; k < G.arcnum; ++k) {
//定义两个顶点和边的权值
VerTexType v1,v2;
ArcType w;
cout<<"—————请依次输入每条边的顶点和权重—————"<<endl;
cin>>v1>>v2>>w;
//确定两个顶点在图中的位置
i=LocateVer(G,v1);
j=LocateVer(G,v2);
//两个顶点之间的权值
G.arcs[i][j]=w;
//无向图邻接矩阵权值对称
G.arcs[j][i]=G.arcs[i][j];
}
return OK;
cout<<endl;
}
int main() {
cout<<"***************显示相邻矩阵使用相邻矩阵***************"<<endl;
AMGraph G;
CreateUDN(G);
cout<<"-********************显示相邻矩阵********************"<<endl;
for (int i = 0; i < G.vexnum; ++i) {
for (int j = 0; j < G.vexnum; ++j) {
if (j!=G.vexnum-1){
if (G.arcs[i][j]!=MaxInt){
cout<<G.arcs[i][j]<<"\t";
} else{
cout << "∞" << "\t";
}
}else{
if(G.arcs[i][j]!=MaxInt){
cout<<G.arcs[i][j]<<endl;
} else{
cout << "∞" <<endl;
}
}
}
}
cout<<endl;
return 0;
}
邻接矩阵实现的DFS深度优先搜索代码如下：
#include <stdio.h>
#include <stdlib.h>
// 定义图的邻接矩阵
typedef struct {
int verNum, egdeNum; // 顶点个数、边条数
int *vertex; // 顶点
int **matrix; // 邻接矩阵
} MGraph;
// 初始化图
void Init_MGraph(MGraph &G, int n, int e, int edge[][2]) {
G.verNum = n;
G.egdeNum = e;
G.vertex = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
G.vertex[i] = i;
}
G.matrix = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
G.matrix[i] = (int *)malloc(n * sizeof(int));
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
G.matrix[i][j] = 0;
}
}
// 初始化邻接矩阵
for (int k = 0; k < e; k++) {
int *arc = edge[k];
G.matrix[arc[0]][arc[1]] = 1;
}
}
// 寻找下一个相邻的顶点,存在则返回下标，否则返回-1
int FindNextVertex(MGraph &G, int vexRow, int* visited) {
if (vexRow >= G.verNum) {
return -1;
}
for (int i = 0; i < G.verNum; i++) {
if (G.matrix[vexRow][i] != 0 && !visited[i]) {
return i;
}
}
return -1;
}
// DFS深度优先搜索
void DFS_MGraph(MGraph &G, int pos, int *visited, int *out) {
if (pos < G.verNum && !visited[pos]) {
// printf("当前结点: %d\n", G.vertex[pos]);
visited[pos] = 1;
out[pos] = pos;
// DFS 访问下一个顶点
int seq = FindNextVertex(G, pos, visited);
if (seq != -1) {
DFS_MGraph(G, seq, visited, out);
}
}
}
void DFS(MGraph &G, int *out) {
int visited[G.verNum];
// 初始化全局变量
for (int i = 0; i < G.verNum; i++) {
visited[i] = 0;
}
for (int i = 0; i < G.verNum; i++) {
if (!visited[i]) {
DFS_MGraph(G, i, visited, out);
}
}
}
void printResult(int *out, int n) {
printf("sloveA: out={");
for (int i = 0; i < n; i++) {
if (i != n - 1) {
printf("%d, ", out[i]);
} else {
printf("%d", out[i]);
}
}
printf("}");
}
void solveA(int n, int e, int edge[][2], int *out) {
MGraph G;
Init_MGraph(G, n, e, edge);
// DFS深度优先遍历
DFS(G, out);
// 输出结果
printResult(out, n);
}
int main() {
int n = 0;
int e = 0;
printf("请输入结点个数n, 边的条数e\n");
scanf("%d %d", &n, &e);
int edge[e][2];
for (int i = 0; i < e; i++) {
printf("请输入边关系集合(v1,v2): ");
scanf("%d %d", &edge[i][0], &edge[i][1]);
}
int out[n];
for (int i = 0; i < n; i++) {
out[i] = 0;
}
solveA(n, e, edge, out);
return 0;
}
运行结果如下所示：
图的深度优先遍历
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
/**
* @className: Graph
* @description: 图
* @date: 2021/3/28
* @author: cakin
*/
public class Graph {
// 存储顶点集合
private ArrayList<String> vertexList;
// 存储图对应的邻结矩阵
private int[][] edges;
// 表示边的数目
private int numOfEdges;
// 表示某个结点是否被访问
private boolean[] isVisited;
/**
* 功能描述：图的擦拭
*
* @param args 命令行
* @author cakin
* @date 2021/3/28
*/
public static void main(String[] args) {
// 顶点
String Vertexs[] = {"A", "B", "C", "D", "E"};
//String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
// 结点的个数
int n = Vertexs.length;
// 创建图对象
Graph graph = new Graph(n);
// 循环的添加顶点
for (String vertex : Vertexs) {
graph.insertVertex(vertex);
}
// 添加边
graph.insertEdge(0, 1, 1); // A-B
graph.insertEdge(0, 2, 1); // A-C
graph.insertEdge(1, 2, 1); // B-C
graph.insertEdge(1, 3, 1); // B-D
graph.insertEdge(1, 4, 1); // B-E
// 显示邻结矩阵
graph.showGraph();
// dfs测试
System.out.println("dfs:");
graph.dfs(); // A->B->C->D->E
}
// 构造器
public Graph(int n) {
// 初始化矩阵
edges = new int[n][n];
// 初始化 vertexList
vertexList = new ArrayList<>(n);
// 边的数量
numOfEdges = 0;
}
/**
* 功能描述：得到某个顶点的第一个邻接结点的下标 w
*
* @param index 顶点索引
* @return 如果存在就返回对应的下标，否则返回-1
*/
public int getFirstNeighbor(int index) {
for (int j = 0; j < vertexList.size(); j++) {
if (edges[index][j] > 0) {
return j;
}
}
return -1;
}
/**
* 功能描述：根据前一个邻接结点的下标来获取下一个邻接结点
*
* @param v1 第1个顶点
* @param v2 第2个顶点，也就是邻节点
* @return int 邻节点的下一个邻节点
* @author cakin
* @date 2021/3/29
*/
public int getNextNeighbor(int v1, int v2) {
for (int j = v2 + 1; j < vertexList.size(); j++) {
if (edges[v1][j] > 0) {
return j;
}
}
return -1;
}
/**
* 功能描述：深度优先遍历算法
*
* @author cakin
* @date 2021/3/29
* @param isVisited 节点是否被访问数组
* @param i 被访问节点的下标
* @return
* @description:
*/
private void dfs(boolean[] isVisited, int i) {
// 输出被访问节点
System.out.print(getValueByIndex(i) + "->");
// 将该结点设置为已经访问
isVisited[i] = true;
// 查找结点i的第一个邻接结点w
int w = getFirstNeighbor(i);
while (w != -1) { // 找到该邻节点
if (!isVisited[w]) {
// 递归进行深度优先遍历算法
dfs(isVisited, w);
}
// 如果w结点已经被访问过，找下一个邻节点
w = getNextNeighbor(i, w);
}
}
/**
* 功能描述：对 dfs 进行一个重载, 遍历所有的结点，并进行 dfs
*
* @author cakin
* @date 2021/3/29
*/
public void dfs() {
isVisited = new boolean[vertexList.size()];
// 遍历所有的结点，进行 dfs
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]) {
dfs(isVisited, i);
}
}
}
/**
* 功能描述：返回结点的个数
*
* @author cakin
* @date 2021/3/28
*/
public int getNumOfVertex() {
return vertexList.size();
}
/**
* 功能描述：显示图对应的矩阵
*
* @author cakin
* @date 2021/3/28
*/
public void showGraph() {
for (int[] link : edges) {
System.err.println(Arrays.toString(link));
}
}
/**
* 功能描述：得到边的数目
*
* @return 得到边的数目
* @author cakin
* @date 2021/3/28
*/
public int getNumOfEdges() {
return numOfEdges;
}
/**
* 功能描述：返回结点i(下标)对应的数据
*
* @param i 节点下标
* @return 节点对应的数据
* @author cakin
* @date 2021/3/28
* @description: 举例如下：
* 0->"A" 1->"B" 2->"C"
*/
public String getValueByIndex(int i) {
return vertexList.get(i);
}
/**
* 功能描述：返回v1和v2的权值
*
* @param v1 第1个顶点的下标
* @param v2 第2个顶点的下标
* @return int 两个顶点间的权值
* @author cakin
* @date 2021/3/28
*/
public int getWeight(int v1, int v2) {
return edges[v1][v2];
}
/**
* 功能描述：插入结点
*
* @param vertex 节点的数据
* @author cakin
* @date 2021/3/28
*/
public void insertVertex(String vertex) {
vertexList.add(vertex);
}
/**
* 功能描述：添加边
*
* @param v1 第1个顶点对应的下标
* @param v2 第2个顶点对应的下标
* @param weight 表示第1个顶点和第2个顶点的权重
*/
public void insertEdge(int v1, int v2, int weight) {
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}
}
用邻接矩阵和邻接链表实现的深度优先遍历的示例代码，参考：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 3001
#define M 100001
// 邻接矩阵数据结构
typedef struct {
int n;
bool adj[N][N];
bool visited[N];
} MatrixGraph;
MatrixGraph* createMatrixGraph(int n) {
MatrixGraph* graph = (MatrixGraph*)malloc(sizeof(MatrixGraph));
graph->n = n;
for (int i = 0; i < n; i++) {
graph->visited[i] = false;
for (int j = 0; j < n; j++) {
graph->adj[i][j] = false;
}
}
return graph;
}
void addEdgeToMatrixGraph(MatrixGraph* graph, int u, int v) {
graph->adj[u][v] = true;
graph->adj[v][u] = true;
}
// 邻接链表数据结构
typedef struct _ListNode {
int v;
struct _ListNode* next;
} ListNode;
typedef struct {
int n;
ListNode* adj[N];
bool visited[N];
} ListGraph;
ListGraph* createListGraph(int n) {
ListGraph* graph = (ListGraph*)malloc(sizeof(ListGraph));
graph->n = n;
for (int i = 0; i < n; i++) {
graph->visited[i] = false;
graph->adj[i] = NULL;
}
return graph;
}
void addEdgeToListGraph(ListGraph* graph, int u, int v) {
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->v = v;
node->next = graph->adj[u];
graph->adj[u] = node;
}
// 邻接矩阵数据结构实现
void solveA(MatrixGraph* graph, int u, int out[], int* idx) {
out[*idx] = u;
(*idx)++;
graph->visited[u] = true;
for (int v = 0; v < graph->n; v++) {
if (graph->adj[u][v] && !graph->visited[v]) {
solveA(graph, v, out, idx);
}
}
}
void solveA(int n, int m, int e[M][2], int out[]) {
MatrixGraph* graph = createMatrixGraph(n);
for (int i = 0; i < m; i++) {
addEdgeToMatrixGraph(graph, e[i][0], e[i][1]);
}
int idx = 0;
solveA(graph, 0, out, &idx);
}
// 邻接链表数据结构实现
void solveB(ListGraph* graph, int u, int out[], int* idx) {
out[*idx] = u;
(*idx)++;
graph->visited[u] = true;
for (ListNode* p = graph->adj[u]; p; p = p->next) {
int v = p->v;
if (!graph->visited[v]) {
solveB(graph, v, out, idx);
}
}
}
void solveB(int n, int m, int e[M][2], int out[]) {
ListGraph* graph = createListGraph(n);
for (int i = 0; i < m; i++) {
addEdgeToListGraph(graph, e[i][0], e[i][1]);
}
int idx = 0;
solveB(graph, 0, out, &idx);
}
int main() {
int n = 5, m = 10;
int e[M][2] = {{2, 4}, {3, 0}, {0, 2}, {3, 1}, {4, 1}, {0, 1}, {3, 4}, {2, 3}, {1, 2}, {0, 4}};
int outA[N], outB[N];
solveA(n, m, e, outA);
solveB(n, m, e, outB);
for (int i = 0; i < n; i++) {
printf("%d ", outA[i]);
}
putchar('\n');
for (int i = 0; i < n; i++) {
printf("%d ", outB[i]);
}
putchar('\n');
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 3001
int n, m;
int e[MAX_N][MAX_N];
int visited[MAX_N];
int out[MAX_N];
int out_index;
void dfs(int u) {
visited[u] = 1;
out[out_index++] = u;
for (int v = 0; v < n; v++) {
if (e[u][v] && !visited[v]) {
dfs(v);
}
}
}
void solveA(int n, int m, int e[][2], int out[]) {
for (int i = 0; i < n; i++) {
visited[i] = 0;
}
out_index = 0;
dfs(0);
}
int main() {
n = 5;
m = 10;
int edges[][2] = {{2, 4}, {3, 0}, {0, 2}, {3, 1}, {4, 1}, {0, 1}, {3, 4}, {2, 3}, {1, 2}, {0, 4}};
for (int i = 0; i < m; i++) {
int u = edges[i][0];
int v = edges[i][1];
e[u][v] = e[v][u] = 1;
}
solveA(n, m, edges, out);
for (int i = 0; i < n; i++) {
printf("%d ", out[i]);
}
printf("\n");
return 0;
}
在理解DFS深度优先搜索之后本题应该并不难求解，CSDN内有很多相关程序，可以搜索参考一下。