深度優先周遊(鄰接矩陣，鄰接表)

    深度優先周遊也稱為深度優先搜尋，簡稱為DFS。

    深度優先周遊的思路是從圖中某個頂點V出發，通路此頂點，然後從V的未被通路過的鄰接點出發深度優先周遊圖，直到圖中所有與V路徑相通的頂點都被通路到

    該周遊過程用到遞歸。

    深度優先周遊用到了一個輔助數組Graph_sign【】，該數組的下标與頂點數組的下标對應，即當Graph_sign【1】中儲存的标記為true就表示頂點數組vexs【1】中儲存的頂點已被周遊到

代碼：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
typedef char VertexType;//頂點類型
typedef int EdgeType;//邊上的權值類型
#define MAXVEX 20//最大頂點數（開辟儲存頂點的一維數組的空間大小）
#define INFINITY 10000//用10000來代表無窮（在儲存邊的二維數組中，對沒有該邊存在的表格，權值設為無窮）
//定義圖的結構體（圖由儲存頂點的一維數組和儲存邊的二維數組，以及記錄圖中結點數和邊數的int類型的變量組成）
struct MGraph
{
	VertexType vexs[MAXVEX];//儲存頂點的一維數組
	EdgeType arc[MAXVEX][MAXVEX];//儲存邊的二維數組
	int Num_vex, Num_arc;//圖中的頂點數和邊數
};

//無向網圖的建立
void Create_MGraph(MGraph& G)
{
	int m, n;
	cout << "請輸入圖的頂點數和邊數" << endl;
	cin >> G.Num_vex >> G.Num_arc;
	cout << "請依次輸入圖的頂點：" << endl;
	for (int i = 0; i < G.Num_vex; i++)
	{
		cin >> G.vexs[i];
	}
	//初始化儲存邊的二維數組
	for (int i = 0; i < G.Num_vex; i++)
		for (int j = 0; j < G.Num_vex; j++)
		{
			G.arc[i][j] = INFINITY;
		}
	//向二維數組中輸入對應邊的權值
	for (int k = 0; k < G.Num_arc; k++)
	{
		cout << "請依次輸入邊（Vm,Vn）的下标m，n" << endl;
		cin >> m >> n;
		cout << "請輸入邊(" << G.vexs[m-1] << "," << G.vexs[n - 1] << ")的權值" << endl;
		cin >> G.arc[m - 1][n - 1];
		//由于是無向網圖，是以存在邊（m，n），就存在邊（n，m）是以我們還應該向二維數組的（n，m）位置輸入權值
		G.arc[n - 1][m - 1] = G.arc[m - 1][n - 1];
	}
}

//深度優先周遊輸出所有頂點
//記錄頂點是否被周遊過的标志數組
bool Graph_sign[MAXVEX];
//鄰接矩陣的深度優先算法
void DFS(MGraph& G,int i)//i是作為第一個周遊的頂點的下标
{
	cout << G.vexs[i] << " ";
	//下标為i的頂點已經周遊到改變标志
	Graph_sign[i] = true;
	//周遊其餘頂點，判斷由頂點i能到達的下一個頂點
	for (int j = 0; j < G.Num_vex; j++)
	{
		if (G.arc[i][j] != INFINITY && !Graph_sign[j])
		{
			DFS(G, j);
		}
	}
}

//鄰接矩陣的深度周遊操作
void DFS_MGraph(MGraph& G)
{
	//初始化标志數組
	for (int i = 0; i < G.Num_vex; i++)
	{
		Graph_sign[i] = false;
	}
	//圖不連通的情況要有多個頂點作為第一個周遊的頂點
	for (int j = 0; j < G.Num_vex; j++)
	{
		if (!Graph_sign[j])
			DFS(G, j);
	}
}


int main()
{
	MGraph G;
	Create_MGraph(G);
	DFS_MGraph(G);
	system("pause");
	return 0;
}
           

        鄰接表和鄰接矩陣大同小異：

代碼如下：

#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#define MAXSIZE 20
//頂點類型
typedef char VetexType;
//權值類型
typedef int InfoType;
//邊表結點
struct EdgeNode
{
	//鄰結點域儲存頂點的下标
	int adjvex;
	//權值
	InfoType m_info;
	//指向下一個邊表結點的指針
	EdgeNode* next;
};

//頂點表結點
struct VertexNode
{
	//頂點
	VetexType vetex;
	//指向邊表的頭指針
	EdgeNode* FirstEdge;
};

//鄰接表
struct GraphAdiList
{
	//頂點數組
	VertexNode Adjext[MAXSIZE];
	//頂點個數，邊條數
	int numVertex, numEdges;
};

//建立鄰接表
void CreaterADGraph(GraphAdiList& G)
{
	int m, n, info;
	cout << "請輸入頂點個數和邊條數" << endl;
	cin >> G.numVertex >> G.numEdges;
	//初始化頂點表
	for (int i = 0; i < G.numVertex; i++)
	{
		cout << "請輸入第" << i + 1 << "個頂點" << endl;
		//初始化頂點表中的兩個屬性
		cin >> G.Adjext[i].vetex;
		G.Adjext[i].FirstEdge = NULL;
	}
	//建立邊表
	for (int k = 0; k < G.numEdges; k++)
	{
		EdgeNode* p;
		p = new EdgeNode;
		cout << "請輸入邊（vm,vn）上的頂點序号（m，n）和權值" << endl;
		cin >> m >> n >> info;
		//初始化建立的邊表結點p
		p->adjvex = n - 1;
		p->m_info = info;
		//将邊表結點p按頭插法插入鄰接表
		p->next = G.Adjext[m - 1].FirstEdge;
		G.Adjext[m - 1].FirstEdge = p;
		//由于該圖是無向圖是以還要考慮（n，m）的情況
		p = new EdgeNode;
		p->adjvex = m - 1;
		p->m_info = info;
		p->next = G.Adjext[n - 1].FirstEdge;
		G.Adjext[n - 1].FirstEdge = p;
	}
	cout << "鄰接表建立完成" << endl;
}

//深度優先周遊輸出所有頂點
//鄰接表的深度優先周遊算法
bool Graph_sign[MAXSIZE];//标志數組，用來判斷頂點是否被周遊過，被周遊過的為true，否則為false
void DFS(GraphAdiList& G, int i)//i是頂點在頂點表中的下标
{

	//說明下标為i的頂點已經被周遊
	Graph_sign[i] = true;
	cout << G.Adjext[i].vetex;
	EdgeNode* p;
	p = G.Adjext[i].FirstEdge;
	if (!Graph_sign[p->adjvex])
	{
		DFS(G, p->adjvex);
	}
}

//鄰接表的深度周遊操作
void ADGraph(GraphAdiList& G)
{
	//初始化标志數組
	for (int i = 0; i < G.numVertex; i++)
	{
		Graph_sign[i] = false;
	}
	//找到未被周遊到的頂點作為第一個周遊的頂點進行周遊（要是圖是全部連通的就隻會周遊一次）
	for (int j = 0; j < G.numVertex; j++)
	{
		if (!Graph_sign[j])
		{
			DFS(G, j);
		}
	}
}

int main()
{
	GraphAdiList G;
	CreaterADGraph(G);
	ADGraph(G);
}
           

    以上兩個代碼都是完整的可調式的程式，相應的關于鄰接矩陣和鄰接表的建立可以看這裡：

鄰接表建立，鄰結矩陣的建立。

    深度優先周遊的流程圖如下：

  ps：以上圖來自于大話資料結構

    我們注意到在深度周遊操作中我們還要利用for循環周遊所有頂點，再将其傳入深度優先周遊算法DFS中，其實我們的深度優先周遊算法DFS隻要傳入一個頂點就已經可以周遊完一個連通圖了，那為什麼我們還要周遊所有頂點判斷出沒有周遊到的頂點再調用DFS函數呢：-------因為我們的圖不一定是連通的，要是圖不連通的話就會分為幾個連通的部分，而深度優先周遊算法DFS隻會周遊出與傳入的首個頂點連通的所有頂點，而未與首個頂點連通的頂點是周遊不出來的。是以要再對所有頂點進行周遊，找出其他連通部分的頂點作為該連通部分的首個頂點，傳入到DFS算法中

    （若圖中尚有頂點未被通路，則另選圖中一個未曾被通路的頂點作起始點，重複DFS算法直到圖中所有頂點都被通路到為止）