一、算法思想

【DFS】

本算法以无向网为例，存储方式采用邻接矩阵

1）将该网以邻接矩阵的方式存储，由于这里的示例采用无向图，因此它是一个对称阵
2）选取A点为起始点，访问此顶点，用一个visit的bool型数组记录访问状态（false表示未被访问，true表示已访问）
3）从A的未被访问的邻接点出发，深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到

二、算法复杂度：O(n^2)

        存储方式采用邻接矩阵，本身是一个二维数组，要查找每个顶点的邻接点都需要访问矩阵中的所有元素，因此需要O(n^2)的时间

三、算法测试用例

    本算法的测试用例为《大话数据结构》p239中的图7-5-2，如下图所示：

四、C代码邻接矩阵的DFS实现

/*******************************************************************************************
【DFS】
Author:tmw
date:2018-2-19
********************************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


#define MAX_VERTEX 100
#define inf 65535  //表示两点之间没有边相连

int visit[MAX_VERTEX];   //标记顶点是否被访问

/**图的邻接矩阵的建立**/
//邻接矩阵数据结构定义
typedef struct Martrix_Graph
{
    char vertex[MAX_VERTEX]; //存储顶点信息
    int edge[MAX_VERTEX][MAX_VERTEX]; //存储边信息
    int vertex_number,edge_number;//存储顶点数和边数
}Martrix_Graph;

void Create_non_direction_martrix_Graph( Martrix_Graph *G )
{
    int i,j,k,m;
    printf("请输入构造的无向图的顶点数和边数：\n");
    scanf("%d %d",&G->vertex_number,&G->edge_number);

    printf("请输入无向图顶点信息（如ABCDEF....）：\n");
    char ch;
    while( ( ch = getchar() != '\n' ) );  //过滤掉前面的\n，防止\n被scanf进去
    for(i=0;i<G->vertex_number;i++)
        scanf("%c",&G->vertex[i]);

    //不相连的顶点之间的权值设为inf，包括顶点自身
    //初始化邻接矩阵
    for(i=0;i<G->vertex_number;i++)
        for(j=0;j<G->vertex_number;j++)
            G->edge[i][j] = inf;

    //更新无向图边信息
    printf("请输入无向图邻接矩阵相连的边信息，相连标记为1\n");
    for(k=0;k<G->edge_number;k++)
    {
        scanf("%d %d %d",&i,&j,&m);
        G->edge[i][j] = m;
        G->edge[j][i] = G->edge[i][j];//无向图是对称阵
    }


    //打印邻接矩阵存储信息，检查正确性
    printf("---------------------构造出来的无向图邻接矩阵如下---------------------\n");
    for(i=0;i<G->vertex_number;i++)
    {
        for(j=0;j<G->vertex_number;j++)
            printf("%d\t",G->edge[i][j]);
        printf("\n");
    }
}

//从当前第i个顶点出发，DFS遍历
void DFS(Martrix_Graph G, int i)
{
    int j;
    //标记当前顶点为已访问状态
    visit[i] = true;
    printf("%c ",G.vertex[i]);

    //对与该顶点相连的其他未访问顶点进行DFS
    for(j=0;j<G.vertex_number;j++)
    {
        if( G.edge[i][j]==1 && !visit[j] )
            DFS(G,j);
    }
}
//对整个图进行DFS
void DFS_Travel(Martrix_Graph G)
{
    //初始化visit数组
    int i;
    for(i=0;i<G.vertex_number;i++)
        visit[i] = false;

    //整张图的DFS
    printf("对该无向图进行DFS的结果如下：\n");
    for(i=0;i<G.vertex_number;i++)
    {
        if( !visit[i] )
            DFS(G,i);
    }
}

五、测试程序及运行结果

int main()
{
    printf("测试代码\n");
    Martrix_Graph G;
    Create_non_direction_martrix_Graph(&G);
    DFS_Travel(G);
    return 0;
}

运行结果：

/*
图的存储结构  邻接矩阵
用一个一维数组 存放图中所有的顶点信息
用一个二维数组 存放边的信息  有向图称为弧 无向图称为边
*/
#include <iostream>
#include <vector>
#include <string>
#include <deque>


using namespace std;


#define MAXSIZE 32
#define INVAILDVALUE -1
typedef int Node;
//点和边集
struct Graph
{
public:
Graph()
{
nVert = 0;
Vertex.clear();
nEdge = 0;
isDirection = false;
isWeight = false;
edgeInfo = NULL;
}


bool Init(bool bDirection = false);


void print();


void depth();


void depthSearch(int index,bool *visit);


void Breadth();


void BreadthSearch(int index ,bool *visit);
public:
//顶点数
int nVert;
vector<string> Vertex;
//边
int nEdge;
int ** edgeInfo;


//是否有向
bool isDirection;


//是否带权
bool isWeight;

};


bool Graph::Init(bool bDirection)
{
cout << "请输入顶点数" << endl;
cin >> nVert;
getchar();
if (nVert <= 0 || nVert >= MAXSIZE) return false;
string s;
char test[256];
cout << "请输入顶点信息" << endl;
for (int  i = 0; i < nVert; i++)
{
if (getline(cin, s))
{
Vertex.push_back(s);
}
else
{
sprintf_s(test, "%d", i + 1);
Vertex.push_back(test);
}
}


cout << "请输入边数" << endl;


cin >> nEdge;
//n*(n-1)/2  顶点与边的关系
if (nEdge <= 0 || nEdge >= MAXSIZE || nEdge > nVert*(nVert-1)/2 ) return false;


isDirection = bDirection;


edgeInfo = new int*[nVert];
for (int i = 0; i < nVert; i++)
{
edgeInfo[i] = new int[nVert];
memset(edgeInfo[i], INVAILDVALUE, sizeof(int)*nVert);
}


for (int i = 0; i < nEdge; i++)
{
int Horizontal, Longitudinal,n;
cin >> Horizontal >> Longitudinal>>n;
edgeInfo[Horizontal][Longitudinal] = n;
if (!isDirection)
edgeInfo[Longitudinal][Horizontal] = n;
}
return true;
}


void Graph::print()
{
if (nVert <= 0) return;
for (int i = 0; i < nVert; i++)
{
for (int  j = 0; j < nVert; j++)
{
cout << edgeInfo[i][j] << " ";
}
cout << endl;
}
}


//深度优先遍历
void Graph::depth()
{
cout << "深度优先遍历开始" << endl;
bool visit[MAXSIZE];
memset(visit, true, sizeof(visit));
for (int i = 0; i < nVert; i++)
{
visit[i] = false;
}


for (int i = 0; i < nVert; i++)
{
depthSearch(i, visit);
}
}


void Graph::depthSearch(int index, bool *visit)
{
if (visit[index] )
{
return;
}
cout << "访问" << Vertex[index] << endl;
visit[index] = true;
for (int i = 0; i < nVert; i++)
{
if (!visit[i] && edgeInfo[index][i] != INVAILDVALUE)
{
depthSearch(i, visit);
}
}
}


void Graph::Breadth()
{
cout << "广度优先遍历开始" << endl;
bool visit[MAXSIZE];
memset(visit, true, sizeof(visit));
memset(visit, false, nVert*sizeof(bool));


for (int i = 0; i < nVert; i++)
{
BreadthSearch(i, visit);
}
}


deque<int> tDeque;
void Graph::BreadthSearch(int index, bool *visit)
{
if (visit[index])
{
return;
}
cout << "visit " << Vertex[index] << endl;
visit[index] = true;
for (int i = index + 1; i < nVert; i++)
{
if (!visit[i] && edgeInfo[index][i] != INVAILDVALUE)
{
tDeque.push_back(i);
}
}
while (tDeque.size() > 0)
{
int t = tDeque.front();
tDeque.pop_front();
BreadthSearch(t, visit);
}
}


int main()
{
while (true)
{
Graph t;
if (t.Init())
{
//t.print();
t.depth();
t.Breadth();
}
}
return 0;
}

先附上程序效果：

邻接表：

邻接矩阵，也就是使用二维数组用来存放每个顶点与对应边的关系，例如两个顶点存在边，那么就将这个二维数组对应的下标设置为一个非0值。如下图：
无向图情况：

有向图情况：

邻接矩阵是一种不错的图存储结构，但是对于边数使用较少的图，比较浪费存储空间，
比如下面这种情况：

而学习线性表的时候我们都知道顺序存储结构浪费空间，所以引出了链式存储结构来节约空间。
因此，同样的我们可以对弧或边使用链式存储结构来避免空间浪费的问题。
于是我们引出了新的图存储结构，邻接表。
我们通过将数组与链表结合来存储一张图，而这种链表与数组相结合的的存储方法称为邻接表。


那么邻接表大概我们知道是什么样子了，那么实现起来就容易了。
接下来是结构体的定义：

typedef struct Adjvex		//邻接域
{
	int adjvex;		//顶点的邻接点在数组的下标
	int weight;		//权值 有没有都可以 看你用的是有向还是无向图
	Adjvex* next;	//下一个邻接点在数组的下标
}*Edgenode,Adjvex;
typedef struct Vertxnode	//顶点节点 顶点数组 存放节点以及邻接的顶点的下标指针
{
	ElemType data;
	Adjvex* firstedge;
}Vertexnode,Adjlist[MAXSIZE];
typedef struct Graphlist		//邻接表 将顶点数组与顶点数和边数结合
{
	Adjlist adjlist;		//顶点数组以及邻接域
	int vexnum, edgenum;	//顶点和边数目;
}Graphlist,*p_Graphlist;

int Visited[MAXSIZE] = {0}; //用来表示当前顶点是否被访问 1表示访问 0表示没有访问
int AdjRectangle[MAXSIZE][MAXSIZE]; //二维数组模拟邻接矩阵

对于无向图的构建，我们遵循对称原则，这是由于无向图一条边指向的两个顶点是互相指向对方的，所以在对方的邻接顶点域中都需要将对方的下标存放进来。

void CreateGraphlist(p_Graphlist p)
{
	int i, j, k;
	Edgenode e;
	cout << "输入顶点数和边数" << endl;
	cin >> p->vexnum >> p->edgenum;   //输入边数和表数
	for (i = 0; i < p->vexnum; i++)		//初始化顶点表
	{
		cout << "输入顶点数据" << endl;
		cin >> p->adjlist[i].data;  //顶点数据赋值
		p->adjlist[i].firstedge = NULL;	//暂定邻接边表为空
	}
	for (i = 0; i < p->vexnum; i++)//二维数组模拟邻接矩阵|0 0 1| 
	{										    //例如	 |0 0 1|
		for (k = 0; k < p->vexnum; k++)			//		 |1 1 0|
		{
			AdjRectangle[i][k] = 0;				//暂定初始化为全0
		}
	}
	for (k = 0; k < p->edgenum; k++)//这个for循环用于输入edgenum个边
	{
		cout << "输入边(vi,vj)上的顶点序号" << endl; //vi为边尾，vj为边头
		cin >> i >> j;			 //输入0，1则代表边尾为v0，边头尾v1
		AdjRectangle[i][j] = 1;  //对应的数组位置设置为1，代表有一个表
		AdjRectangle[j][i] = 1;	 //矩阵是对称的，对应的位置也置为1
		e = (Edgenode)malloc(sizeof(Adjvex)); //创建邻接顶点表指针
		e->adjvex = j;						  //邻接表的顶点指向j
		//e->next = p->adjlist[i].firstedge;
		p->adjlist[i].firstedge = e;		  //第一个边指向第一个边表
		e = (Edgenode)malloc(sizeof(Adjvex));  //对称式结构
		e->adjvex = i;
		//e->next = p->adjlist[j].firstedge;
		p->adjlist[j].firstedge = e;
	}
	for (int i = 0; i < p->vexnum; i++) {  //输出邻接矩阵
		for (int j = 0; j < p->vexnum; j++)
		{
			cout << AdjRectangle[i][j] << "  ";
		}
		cout << endl;
	}
	DFSTraverse(p);
}

注意:
这里必须着重讲解一下一个节点有多个邻接点的情况。

图中的每一个节点都不止一个邻接点，那么这些邻接点的next是如何指向下一个邻接点的呢？
光看程序不好想象，那么就让我们debug一下吧。
我们以v0点为例，输入v1与v3两条边(只是为了debug而已，了解一次过程就可以推导下一次的过程)
先建立v0与v1的一条边

中途由于不小心点了一下关闭所以可能和下面图片v1的地址是不一样的，但是要表达的意思一样。



可以发现我先输入了v1节点，firstedge会先指向v1节点，而由于firstedge的初始化是NULL，所以v1的next节点是NULL，而之后我输入了v3节点之后，firstedge指向了v3节点，v3节点的next会指向v1节点，这样就形成了一个环路，也就是先输入的反倒在越后面。

那么创建就结束了，比较好理解这个创建，如果实在不理解是怎么创建的，可以进行dubug查看。
那么最后就是重头戏如何遍历整个图了。
我们使用深度优先遍历的方法
那么什么是深度优先遍历？

深度优先遍历：

思路大概是从图的某个节点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直到所有图中和v有路径的相通的顶点都被访问到。上图中v0节点先访问v1，v1被访问后v1先访问自己的邻接点v2，v2又访问自己的邻接点v3，v3访问自己的邻接点v0，之后发现v0已经被访问过了，那么就从v3退回到v2再从v2退回到v1，v1再退回到v0，这样就形成了深度优先遍历。可以发现这是由递归来实现的。
那么最后直接放代码吧。分为了邻接表和邻接矩阵的递归遍历。

代码：

头文件代码：

#pragma once
#include<iostream>
#include <cstdio>
#include<cstdlib>
typedef int Status;
typedef int ElemType;
typedef char cElemType;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSIZE 20
#define make (struct student*)malloc(sizeof(struct student));
using namespace std;

实现代码

#include<algo.h>
typedef struct Adjvex		//邻接域
{
	int adjvex;		//顶点的邻接点在数组的下标
	int weight;		//权值
	Adjvex* next;	//下一个邻接点在数组的下标
}*Edgenode,Adjvex;
typedef struct Vertxnode	//顶点节点
{
	ElemType data;
	Adjvex* firstedge;
}Vertexnode,Adjlist[MAXSIZE];
typedef struct Graphlist		//邻接表
{
	Adjlist adjlist;		//顶点数组以及邻接域
	int vexnum, edgenum;	//顶点和边数目;
}Graphlist,*p_Graphlist;

int Visited[MAXSIZE] = {0}; //用来表示当前顶点是否被访问 1表示访问 0表示没有访问
int AdjRectangle[MAXSIZE][MAXSIZE]; //二维数组模拟邻接矩阵
void DFS(p_Graphlist p, int i)//邻接矩阵的深度优先递归遍历
{
	int j;
	Visited[i] = 1;  //如果访问了该节点则设置为1
	cout << "顶点数据为:" << p->adjlist[i].data << endl; //输出当前节点数据
	for (j = 0; j < p->vexnum; j++)//循环调用递归
	{
		if (AdjRectangle[i][j] == 1 && !Visited[j])//如果边表是1且当前节点没有被访问过则调用递归
		{
			DFS(p, j);//j=0，1，2，3，4...,直到将每一个节点都递归访问了一次之后才结束
		}
	}
}
void DFSTraverse(p_Graphlist p)
{
	int i;
	for (i = 0; i < p->vexnum; i++)
	{
		Visited[i] = 0; //先将所有数据设置为未遍历状态0
	}
	cout << "数据如下：" << endl;
	for (i = 0; i < p->vexnum; i++)//
	{
		if (!Visited[i])
		{
			DFS(p,i);
		}
	}
}
//邻接表的深度优先递归算法
void AdjDFS(p_Graphlist p, int i)
{
	Edgenode e;
	Visited[i] = 1; //访问了当前节点就设置为1	
	cout << p->adjlist[i].data << endl; //输出当前数据
	e = p->adjlist[i].firstedge;  //将第一个邻接点赋值给边表结构体指针
	while (e)
	{
		if (!Visited[e->adjvex])//判断节点是否被访问过 没有则进行递归遍历
		{
			AdjDFS(p, e->adjvex);
		}
		e = e->next;//让e指向自己的下一个位置
	}
}
void AdjDFSTraverse(p_Graphlist p)
{
	int i;
	for (i = 0; i < p->vexnum; i++)
		Visited[i] = 0;//初始化访问数组
	for (i = 0; i < p->vexnum; i++)
	{
		if (!Visited[i])
		{
			AdjDFS(p, i);
		}
	}
}

void CreateGraphlist(p_Graphlist p)
{
	int i, j, k;
	Edgenode e;
	cout << "输入顶点数和边数" << endl;
	cin >> p->vexnum >> p->edgenum;   //输入边数和表数
	for (i = 0; i < p->vexnum; i++)		//初始化顶点表
	{
		cout << "输入顶点数据" << endl;
		cin >> p->adjlist[i].data;  //顶点数据赋值
		p->adjlist[i].firstedge = NULL;	//暂定邻接边表为空
	}
	for (i = 0; i < p->vexnum; i++)//二维数组模拟邻接矩阵|0 0 1| 
	{										    //例如	 |0 0 1|
		for (k = 0; k < p->vexnum; k++)			//		 |1 1 0|
		{
			AdjRectangle[i][k] = 0;				//暂定初始化为全0
		}
	}
	for (k = 0; k < p->edgenum; k++)//这个for循环用于输入edgenum个边
	{
		cout << "输入边(vi,vj)上的顶点序号" << endl; //vi为边尾，vj为边头
		cin >> i >> j;			 //输入0，1则代表边尾为v0，边头尾v1
		AdjRectangle[i][j] = 1;  //对应的数组位置设置为1，代表有一个表
		AdjRectangle[j][i] = 1;	 //矩阵是对称的，对应的位置也置为1
		e = (Edgenode)malloc(sizeof(Adjvex)); //创建邻接顶点表指针
		e->adjvex = j;						  //邻接表的顶点指向j
		e->next = p->adjlist[i].firstedge;	  //这句话的作用是为了使得
		p->adjlist[i].firstedge = e;		  //第一个边指向第一个边表
		e = (Edgenode)malloc(sizeof(Adjvex));  //对称式结构
		e->adjvex = i;
		e->next = p->adjlist[j].firstedge;
		p->adjlist[j].firstedge = e;
	}
	for (int i = 0; i < p->vexnum; i++) {  //输出邻接矩阵
		for (int j = 0; j < p->vexnum; j++)
		{
			cout << AdjRectangle[i][j] << "  ";
		}
		cout << endl;
	}
	DFSTraverse(p);
	AdjDFSTraverse(p);
}

int main()
{
	p_Graphlist p;
	p = (p_Graphlist)malloc(sizeof(Graphlist));
	CreateGraphlist(p);
	
}

可以发现邻接矩阵的遍历结果是1 4 3 2，这与我们debug得出的结果是一样的，我们先插入的节点反倒再链表的末尾，后插入的再链表的开头，所以最后插入的v3节点中的数据4最先输出。
那么另一种遍历情况是使用数组判断方法，由于数据是从小到大增加的，所以先插入的节点会先输出，这是邻接矩阵的遍历方法。

最后，如果文章对你有帮助的话请点个赞！！！