需求：
1、基于下图构造图；
2、分别使用深度优先遍历(DFS)、Prim、Dijkstra算法从任意用户输入的节点开始对图进行遍历、求MST及最短路径；
3、三个算法同时动态显示构造过程（非节点动态打印）；
4、每一步都要求显示/打印所有试探的路径。
三个算法同时运行，每一步需要把所有试探/考虑的边突出显示（上图中的绿色边），并分别基于三个算法打印出辅助数据以便进行下一步路径的判定
补充需求：
1、鼓励使用MFC进行可视化，如使用命令行
程序，必须使用EGE等图形库绘图；
2、如果能同时实现A*算法的可视化可加分。
graph.h
#ifndef GRAPH01 #define GRAPH01 #includeconst int maxweight = 65535; using namespace std; class graph { public: graph(int sz); ~graph() { delete[]edge; } int getweight(int v1, int v2) { if (v1 != -1 && v2 != -1) return edge[v1][v2]; else return 0; }//取得两节点之间边的权值 int getfirstnei(int v);//得到第一个相邻结点 int getnextnei(int v, int w);//得到下一个相邻节点 int numedg;//边总数 int numver;//结点总数 int maxver;//最大结点数 string verlist;//结点数组 int** edge;//边的邻接矩阵 }; class node//结点类 { public: friend graph; node() {}; ~node() {}; int x;//结点的X坐标 int y;//结点的Y坐标 string data;//结点的数据 int sign = 0;//判断是否被访问过的标志 }; #endif #define SHOW_CONSOLE #include #include #include using namespace std; graph::graph(int sz)//初始化一个图 { maxver = sz; numedg = 0; numver = 0; int i, j; edge = (int**)new int* [maxver]; for (i = 0; i < maxver; i++) edge[i] = new int[maxver]; for (i = 0; i < maxver; i++) for (j = 0; j < maxver; j++) edge[i][j] = (i == j) ? 0 : maxweight; numver = 10; numedg = 17; verlist = "ABCDEFGHIJ"; edge[0][1] = edge[1][0] = 750; edge[0][2] = edge[2][0] = 680; edge[1][2] = edge[2][1] = 800; edge[1][4] = edge[4][1] = 970; edge[1][3] = edge[3][1] = 650; edge[3][2] = edge[2][3] = 820; edge[3][4] = edge[4][3] = 570; edge[3][6] = edge[6][3] = 530; edge[3][5] = edge[5][3] = 975; edge[4][8] = edge[8][4] = 840; edge[2][5] = edge[5][2] = 960; edge[6][5] = edge[5][6] = 680; edge[9][5] = edge[5][9] = 990; edge[6][7] = edge[7][6] = 900; edge[6][9] = edge[9][6] = 980; edge[7][8] = edge[8][7] = 840; edge[7][9] = edge[9][7] = 985; } int graph::getfirstnei(int v) { if (v != -1) { for (int num = 0; num < numver; num++) if (edge[v][num] > 0 && edge[v][num] < maxweight)return num; return -1; } } int graph::getnextnei(int v, int w) { if (v != -1 && w != -1) { for (int num = w + 1; num < numver; num++) if (edge[v][num] > 0 && edge[v][num] < maxweight)return num; } return -1; }
Graph.cpp
#define SHOW_CONSOLE #include"graph.h" #include#include #include #include using namespace std; void show(graph& gra, int& num, node* n); void DFS(graph& gra, node* n, int m)//深度优先遍历算法 { cout << n[m].data << endl; n[m].sign = 1; int temp = gra.getfirstnei(m); setlinewidth(5); setcolor(RED); while (temp != -1) { if (n[temp].sign == 0) { Sleep(500); line(n[m].x, n[m].y, n[temp].x, n[temp].y); DFS(gra, n, temp); }//递归 temp = gra.getnextnei(m, temp); } } int prim(graph& gra, node* n, int m, int* d)//prim算法 { for (int p = 0; p < gra.numver; p++)//将所有的距离初始化，设置为int类型最大值 { d[p] = INT_MAX; } d[m] = 0;//到自己的距离为0 int sum = 0; for (int i = 0; i < gra.numver; i++) { int u = -1;//u点到某一结点最小 int min = INT_MAX; for (int j = 0; j < gra.numver; j++) { if (n[j].sign == 0 && d[j] < min) { min = d[j]; u = j; } } if (u == -1) { return -1; }//找不到d[j]说明不连通 n[u].sign = 1; setlinewidth(5); setcolor(RED); sum += d[u]; for (int l = 0; l < gra.numver; l++)//画边 { for (int k = l + 1; k < gra.numver; k++) { if (gra.edge[l][k] == d[u]) { Sleep(500); line(n[l].x, n[l].y, n[k].x, n[k].y); } } } for (int v = 0; v < gra.numver; v++) //寻找该结点相邻的最小边 { if (n[v].sign == 0 && gra.edge[u][v] < d[v]) { d[v] = gra.edge[u][v]; } } } cout << sum << endl;//输出最小生成树的总权值 return sum; } void dijkstra(graph& gra, node* n, int* d, int ch, int path[])//ch是终点，d为存储最短距离的数组，path是存储最短路径所经结点的数组 { int min; for (int i = 0; i < gra.numver; i++) { d[i] = gra.getweight(ch, i); if (i != ch && d[i] < INT_MAX)path[i] = ch; else path[i] = -1; } n[ch].sign = 1; d[ch] = 0;//将标志置为1，到自己距离为0 for (int i = 0; i < gra.numver - 1; i++) { min = INT_MAX; int u = ch; for (int j = 0; j < gra.numver; j++) { if (n[j].sign == 0 && d[j] < min) { u = j; min = d[j]; } n[u].sign = 1; for (int k = 0; k < gra.numver; k++) { int w = gra.getweight(u, k); if (n[k].sign == 0 && w < INT_MAX && d[u] + w < d[k]) { d[k] = d[u] + w;//最短路径权值的累加 path[k] = u; } } } } setlinewidth(5); setcolor(RED); line(n[3].x, n[3].y, n[6].x, n[6].y); line(n[6].x, n[6].y, n[9].x, n[9].y); } void printpath(graph& gra, node* n, int v, int* dist, int path[], int zhongdian)//输出最短路径所经过的结点 { int i, j, k, num = gra.numver; int* d = new int[num]; for (i = 0; i < num; i++) { if (i != v && i == zhongdian) { j = i; k = 0; while (j != v) { d[k++] = j; j = path[j]; } cout << n[v].data << " "; while (k > 0) { cout << n[d[--k]].data << " "; } cout << "最短路径长度：" << dist[i] << endl; } } } int main() { initgraph(1000, 1000, INIT_RENDERMANUAL); //初始化窗口 setfillcolor(YELLOW); setbkcolor(WHITE); setfontbkcolor(WHITE); cout << "结点：0-A;1-B;2-C;3-D;4-E;5-F;6-G;7-H;8-I;9-J" << endl; int num = 0; graph gra(20); cout << "结点总数：" << gra.numver << " " << "边总数：" << gra.numedg << endl;//输出结点总数，边总数 for (int i = 0; i < gra.numver; i++)//输出有权值的边 for (int j = i + 1; j < gra.numver; j++) { int w = gra.getweight(i, j); if (w > 0 && w < maxweight) { char e1 = gra.verlist[i]; char e2 = gra.verlist[j]; cout << "(" << e1 << "," << e2 << "," << w << ")" << endl; } } system("pause"); node* no = new node[10];//创建十个结点 for (int p = 0; p < gra.numver; p++) { no[p].data = gra.verlist[p]; } show(gra, num, no); cout << "请选择算法：1.DFS算法 2.Prim算法 3.Dijkstra算法" << endl; int choice; cin >> choice; if (choice == 1) { int start; cout << "输入初始节点(0-9)" << endl; cin >> start; DFS(gra, no, start); } if (choice == 2) { int* vec = new int[10];//用于prim算法 int start; cout << "输入初始节点(0-9)" << endl; cin >> start; prim(gra, no, start, vec); } if (choice == 3) { int start, end; cout << "请输入：" << endl; cin >> start >> end; int* arr = new int[10]; int path[10]; dijkstra(gra, no, arr, start, path); printpath(gra, no, start, arr, path, end); } //line(num[4].x, num[4].y, num[7].x, num[7].y); getch(); closegraph(); } void show(graph& gra, int& num, node* n)//构建图 { if (gra.numver == 0)return; fillellipse(800, 100, 23, 23);//A n[0].x = 800; n[0].y = 100; char ch[100] = { NULL }; for (int i = 0; i < 1; i++) { ch[i] = gra.verlist[num]; } xyprintf(800, 100, ch); num++; Sleep(500); fillellipse(700, 160, 23, 23);//B n[1].x = 700; n[1].y = 160; for (int i = 0; i < 1; i++) { ch[i] = gra.verlist[num]; } xyprintf(700, 160, ch); num++; Sleep(500); fillellipse(780, 220, 23, 23);//C n[2].x = 780; n[2].y = 220; for (int i = 0; i < 1; i++) { ch[i] = gra.verlist[num]; } xyprintf(780, 220, ch); num++; Sleep(500); fillellipse(700, 250,23,23);//D n[3].x = 700; n[3].y = 250; for (int i = 0; i < 1; i++) { ch[i] = gra.verlist[num]; } xyprintf(700, 250, ch); num++; Sleep(500); fillellipse(580, 260, 23, 23);//E n[4].x = 580; n[4].y = 260; for (int i = 0; i < 1; i++) { ch[i] = gra.verlist[num]; } xyprintf(580, 260, ch); num++; Sleep(500); fillellipse(800, 400,23,23);//F n[5].x = 800; n[5].y = 400; for (int i = 0; i < 1; i++) { ch[i] = gra.verlist[num]; } xyprintf(800, 400, ch); num++; Sleep(500); fillellipse(700, 420,23,23);//G n[6].x = 700; n[6].y = 420; for (int i = 0; i < 1; i++) { ch[i] = gra.verlist[num]; } xyprintf(700, 420, ch); num++; Sleep(500); fillellipse(520, 440, 23,23);//H n[7].x = 520; n[7].y = 440; for (int i = 0; i < 1; i++) { ch[i] = gra.verlist[num]; } xyprintf(520, 440, ch); num++; Sleep(500); fillellipse(480, 380,23,23);//I n[8].x = 480; n[8].y = 380; for (int i = 0; i < 1; i++) { ch[i] = gra.verlist[num]; } xyprintf(480, 380, ch); num++; Sleep(500); fillellipse(680, 600,23, 23);//J n[9].x = 680; n[9].y = 600; for (int i = 0; i < 1; i++) { ch[i] = gra.verlist[num]; } xyprintf(680, 600, ch); Sleep(500); //num++; //下面要输出每一条路径上的权值，因为没有找到更好方法，所以只能让数字的位数保持一致，其实可以不用显示权值 //这样，题目中原值可以保留 char c[4]; for (int i = 0; i < gra.numver; i++) for (int j = i + 1; j < gra.numver; j++) { int w = gra.getweight(i, j); if (w > 0 && w < maxweight) { line(n[i].x, n[i].y, n[j].x, n[j].y); for (int p = 0; p < 4; p++) { c[p] = to_string(gra.edge[i][j])[p]; c[3] = ' '; } outtextxy((n[i].x + n[j].x) / 2, (n[i].y + n[j].y) / 2, c); } } }
