本文會(huì)圍繞算法中DFS求有向圖或無(wú)向圖兩點(diǎn)間所有路徑，先講解DFS以及有向圖或無(wú)向圖的意思。

有向圖在圖中的邊是有方向的，表現(xiàn)出來(lái)就是有個(gè)箭頭指示方向，節(jié)點(diǎn)只能單向通信或傳遞消息，相當(dāng)于單行道，無(wú)向圖邊沒(méi)方向是雙向的，邊連接的兩個(gè)節(jié)點(diǎn)有通路可以雙向通信，類(lèi)似于雙行道。

無(wú)向圖，邊沒(méi)有方向的圖稱(chēng)為無(wú)向圖。鄰接矩陣則是對(duì)稱(chēng)的，且只有0和1，因?yàn)闆](méi)有方向的區(qū)別后，要么有邊，要么沒(méi)邊。

DFS作為搜索算法，最常用于圖，對(duì)圖的遍歷，探尋路徑，甚至是求一些情況下的最短路。我在這里就介紹一下dfs求兩點(diǎn)的的所有路徑。

以這張圖為介紹，v1是出發(fā)點(diǎn)，v3是終點(diǎn)。

（1）v1開(kāi)始出發(fā)，v1被標(biāo)記訪(fǎng)問(wèn)過(guò)，并入棧，到v2，標(biāo)記并入棧；

（2）到v3，此時(shí)v3是終點(diǎn)，到達(dá)函數(shù)開(kāi)始的判斷條件，輸入堆棧經(jīng)過(guò)的路徑。一條路找到（1,2,3）。此時(shí)雖然v3可以到v5，但也沒(méi)有必要探尋下去：算法的角度來(lái)說(shuō)如果繼續(xù)探尋下去v3就會(huì)被標(biāo)記，就算有路可以到，下次就不會(huì)背進(jìn)入遞歸了；實(shí)際應(yīng)用來(lái)說(shuō)也沒(méi)必要繞一圈再到一個(gè)地方。這算是一個(gè)剪枝吧。

（3）v3回溯到v2，v2沒(méi)有可走的路了，堆棧中的v2出棧，v2并取消標(biāo)記；

（4）v2回溯到v1，有v4可走，入棧并標(biāo)記。探尋v2可走，入棧并標(biāo)記。v2到v3，另一條路找到（1,4,2,3）；

（5）從v3回溯到v4，探尋到v5可走，入棧并標(biāo)記；

（6）v5沒(méi)路可走了，回溯到v4到v1，程序結(jié)束。

算法時(shí)間復(fù)雜度是O(n*m)。

輸入樣例

5 6

1 2
2 3
3 5
1 4
4 2
4 5

1 3

輸出樣例

1 2 3
1 4 2 3

代碼如下：

#include<stdio.h>
#include<math.h>
int map[100][100]={0};///map[i][j]為0表示i, j兩點(diǎn)之間不通，為1表示有一條路
int stack[120],v[100]={0},top=0,m,n,start,end;
void dfs(int pos)//從pos點(diǎn)開(kāi)始訪(fǎng)問(wèn)
{
	int i;
	if(pos==end){//到達(dá)終點(diǎn)
		for(i=0;i<top;i++)
			printf("%d ",stack[i]);
		printf("%d\n",end);	
		return;
	}
	v[pos]=1;//標(biāo)記被訪(fǎng)問(wèn)過(guò) 
	stack[top++]=pos;//經(jīng)過(guò)的路徑加入隊(duì)列
	for(i=1;i<=n;i++){
		if(!v[i]&&map[pos][i])//如果這個(gè)點(diǎn)沒(méi)有被訪(fǎng)問(wèn)過(guò)，而且b與這個(gè)點(diǎn)相連，就繼續(xù)搜索
			dfs(i);
	}
	v[pos]=0;//刪除標(biāo)記 
	top--;//隊(duì)列里刪除b
}

int main()
{
    int i,x,y;
    printf("分別輸入頂點(diǎn)數(shù)n和路徑數(shù)m："); 
    scanf("%d %d",&n,&m);//n是頂點(diǎn)數(shù)，m是邊數(shù) 
    
    printf("輸入m條路徑："); 
    for(i=1; i<=m; i++) {
        scanf("%d %d", &x,&y);
        map[x][y] = 1;//這兩點(diǎn)之間有路徑
		//map[y][x] = 1; //無(wú)向圖加上這一句即可 
    }
    
    printf("輸入起始點(diǎn)和終點(diǎn)：");
    scanf("%d %d", &start,&end);
    
    printf("\n程序執(zhí)行結(jié)果為：\n"); 
    dfs(start);
    return 0;
    
}

知道每條路徑的長(zhǎng)度也很容易，輸入信息的時(shí)候加上路徑長(zhǎng)度，函數(shù)多一個(gè)參數(shù)，每次遞歸的時(shí)候加上這兩點(diǎn)路徑的長(zhǎng)度，到達(dá)終點(diǎn)輸出就行了，求最短路的話(huà)每次到終點(diǎn)比較一下即可。