//?ConsoleApplication1.cpp?:?定義控制臺應用程序的入口點。
//

#include?“stdafx.h“
#include???
#include?
#include???
using?namespace?std;

struct?Node
{
	int?key;
	int?flag;
	Node（）
	{
		flag?=?0;
	}
};

class?Graph
{
public:
	vector>?resultPath;
	vector?result;
	int?_maxEdgePath;
	int?_pointNum;

	Node?headNode;//起始節點??
	Node?endNode;//終止節點??
	stack?tempStack;
	int?pathNum;
	int?nPos;
	vector?Mark;

public:
	Graph（int?maxEdgePath?int?pointNum）
	{
		_maxEdgePath?=?maxEdgePath;
		_pointNum?=?pointNum;
		//將矩陣中的元素置為空??
		for?（int?i?=?0;?i		{
			vector?tmpresultPath;
			for?（int?j?=?0;?j			{
				tmpresultPath.push_back（0）;
			}
			resultPath.push_back（tmpresultPath）;
			result.push_back（0）;
			Mark.push_back（false）;
		}
		result.push_back（0）;
		pathNum?=?0;
		nPos?=?0;
	}

	vector?CalcPath（vector>?Matrix）
	{
		//開始節點??
		headNode.key?=?2;
		headNode.flag?=?1;

		//結束節點??
		endNode.key?=?8;

		FindAllPath（Matrix?headNode?endNode）;
		if?（pathNum?==?1）
			return?resultPath[0];
		else
			return?result;
	}

	/************************************************************************/
	/*?函數功能：找到圖中兩個節點之間的所有路徑
	參數說明：1、Matrix???初始矩陣，將路徑矩陣的形式存儲，本程序對應的是一個無向圖。
	2、headNode?初始節點
	3、endNode??結束節點

	主要的思想??利用深度優先遍歷的算法
	1、利用result來存放每次從棧中出棧的數據，里面很可能就是要找的路徑，為什么要單獨提取出來，因為包含了多條路徑
	2、通過設置?訪問是否的變量來避免回路/
	/************************************************************************/
	void?FindAllPath（vector>?Matrix?Node?startNodeKey?Node?endNodeKey）
	{
		result[nPos]?=?startNodeKey.key;??//將當前元素放入結果集中??
		Mark[startNodeKey.key?-?1]?=?true;??//將訪問標記為已訪問??
		nPos++;??//結果集索引加1??
		while?（nPos?!=?0）
		{
			int?tempVal?=?result[nPos?-?1];//獲取到最前面的元素????
			if?（tempVal?==?endNodeKey.key）??//若當前元素為目標節點??
			{
				for?（int?j?=?0;?j				{
					resultPath[pathNum][j]?=?result[j];??//將結果集復制于最后的路徑矩陣中??
				}
				nPos--;??//回溯至上一個節點??
				result[nPos]?=?0;??//結果集對應索引置為空??
				pathNum++;??//路徑數目加1??
				Mark[endNodeKey.key?-?1]?=?false;
				break;
			}
			while?（startNodeKey.flag<_pointNum）//利用flag來指示每次的元素的索引????
			{
				if?（Matrix[tempVal?-?1][startNodeKey.flag]?==?1）
				{
					if?（Mark[startNodeKey.flag]?==?false）//利用Mark來判斷是否已經訪問過該節點????
					{
						Node?tempNode;
						tempNode.key?=?startNodeKey.flag?+?1;
						FindAllPath（Matrix?tempNode?endNodeKey）;//深度優先遍歷算法，????
					}
				}
				startNodeKey.flag++;//索引值相應的加一????
			}

			if?（startNodeKey.flag?==?_pointNum）//如果已經是到最后的鄰居，說明訪問結束，????
			{???????????????????????????//將對應的值置為空????
				nPos--;??//再次向上回溯??
				startNodeKey.flag?=?0;??//將節點的索引置為空??
				result[nPos]?=?0;??//將結果集中對應的索引置為空??
				Mark[startNodeKey.key?-?1]?=?false;??//訪問之后標記為未訪問。因為下面的元素已經訪問結束，便于下次的訪問??
				break;
			}
		}
	}
};

int?main（）
{
	//對應無向圖的矩陣
	vector>?Matrix;
	for?（int?i?=?0;?i?	{