// LIN.cpp : 定义控制台应用程序的入口点。
//
//注意的点：
//1.写代码的技巧
//2.记住掌握某一个命令的作用，什么是应用型的代码，这个才是最重要的
//3.看别人的代码之前一定要知道什么是重要的代码，不然看了就和不看是一样的
#include "stdafx.h"
#include<iostream>
#pragma warning(disable:4996)
#include<vector>
using namespace std;
void *p = freopen("add.txt", "rt", stdin);
#define N 100 // 图的顶点数
int visited[N];
vector<int> dis, path; // path用来记录路径长度，dis用来记录距离长度
vector<vector<int> > V; // 多条路径向量
int min = 1000, count = 0, s = 0, Q = 0; // min为当前的最短路径
//==========================图的矩阵表示法
typedef struct ArcCell
{
int weight;//权值
}ArcCell, AdjMatrix[N][N];
struct MGraph
{
char vexs[N];
AdjMatrix arcs;
int vexnum, arcnum;
};
//================================顶点
int LocateVex(MGraph &G, char v)
{
for (int m = 0; m < G.vexnum; m++)
{
if (G.vexs[m] == v)
return m;
}
}
//============================创建图
int CreateUDG(MGraph &G)//这个创建图真的让我学到了不少，还可以这么创建的，我也是醉了
{
cin >> G.vexnum;
int i, j;
for (i = 0; i < G.vexnum; i++)
cin >> G.vexs[i];
for (i = 0; i < G.vexnum; i++)//对权值矩阵进行初始化
for (j = 0; j < G.vexnum; j++)
G.arcs[i][j].weight = 0;
cin >> G.arcnum;//一共有几个顶点，这个是很重要的
for (i = 0; i < G.arcnum; i++)
{
int i, j, w;
char v1, v2;
cin >> v1 >> v2 >> w;//第一个点和第二个点以及他们的权值
i = LocateVex(G, v1);//输出横坐标
j = LocateVex(G, v2);//输出纵坐标
G.arcs[i][j].weight = G.arcs[j][i].weight = w;//对权值的图进行赋值
}
return 1;
}
//==================================输出图的距阵
void PrintMGraph(MGraph &G)
{
for (int i = 0; i < G.vexnum; i++)
{
for (int j = 0; j < G.vexnum; j++)
cout << G.arcs[i][j].weight << " ";
cout << endl;
}
}
//================================判断最短距离
void Judge(MGraph &G, int index)
{
int i, sum = 0; int j;
for (i = 0; i < dis.size(); i++)
sum += dis[i];
path.push_back(sum);//在动态数组path中路径的结尾添加这个路径的距离之和
for (i = 0; i < path.size() - 1 ; i++)
{
if (i == 0)
cout << G.vexs[path[i]];
else
cout << "->" << G.vexs[path[i]];
}cout << " " << sum << endl;
V.push_back(path);//将这个动态数组路径path添加到动态二维数组V的一行中
path.pop_back();//删除path中的最后一个元素
if (sum < min) // 找寻最短距离
min = sum;
}
//====================================DFS深度优先遍历图
//通过递归如果当前结点为指定的终止结点，则比较当前路径的距离和最短路径的大小来重置最短路径
//如果不是终止结点则继续下一个结点进行查找，如果被遍历过，则跳出循环到下一个结点
//对于没有遍历过的顶点，通过visited来标记兵修改此时路径参数
void DFS(MGraph &G, int p, int num, int aim)//num表示已经访问的
{//变量p,num,aim分别为当前访问顶点，当前访问的顶点数，目标顶点
int i;
int j;
int number = 0;
if (p == aim) // 如果当前顶点到达目标顶点，就结束递归
{
number++;
Judge(G, num); // 判断最短距离
return;
}
for (i = 0; i<G.vexnum; i++)
{
if (G.arcs[p][i].weight)//判断两个点之间是否有关系
{
if (!visited[i])//对未访问过的顶点，长度累加
{
s += G.arcs[p][i].weight;
//if (s > min) // 对已访问过顶点的长度判断，当目前长度大于min则不需要再往下递归
//{
// s -= G.arcs[p][i].weight;
// continue; // 结束当前递归
//}
path.push_back(i);//将每一个点在路径path的后面进行插入
dis.push_back(G.arcs[p][i].weight);//将距离的数组
visited[i] = 1;//将顶点表示为已经访问过了
DFS(G, i, num + 1, aim); // DFS递归调用
//对没有下一个顶点的点进行回溯
s -= G.arcs[p][i].weight; // 回溯//下面的都是回溯的过程，现在怎么对回溯进行操作
visited[i] = 0;//将最后一个点从数组尾部进行删除，并表示为尚未进行访问
dis.pop_back();//将路径的最后一个距离给从数组尾部进行删除
path.pop_back();//将最后一个从path的数组的尾部进行删除
}
}
}
}
//=============================输出最短路径
void PrintRouts(MGraph G)
{
int i, j;
cout << "最短路径: " << endl;
for (i = 0; i < V.size(); i++)//V.size数组表示行的长度
{
if (V[i][V[i].size() - 1] == min)
{
for (j = 0; j < V[i].size() - 1; j++)
{
if (j == 0)
cout << G.vexs[V[i][j]];
else
cout << "->" << G.vexs[V[i][j]];
}
cout << "路径 :" << V[i][j] << endl;
}
}
}
//=================================main函数
int _tmain(int argc, _TCHAR* argv[])
{
char c1, c2;
memset(visited, 0, sizeof(visited));//初始化visited矩阵
MGraph G;//定义一个图的对象
CreateUDG(G);//创建无向网
PrintMGraph(G);//打印出距离矩阵
cout << endl;
cin >> c1 >> c2;//从文件中读入起始点与终止点
path.push_back(LocateVex(G, c1));//将起始点从path中进行插入
visited[LocateVex(G, c1)] = 1;//将起始点标志为1，表示已经访问过了
DFS(G, LocateVex(G, c1), 1, LocateVex(G, c2));//进行DFS递归
PrintRouts(G);//打印出最短路径
return 0;
}
