数据结构小学期-算法演示程序实验报告(2)

石家庄铁道大学实习报告

for(i=1;i<=Top;i++) { Father[i]=i; } cout<<\树的各组成边有：\ for(i=0;i

if(Find(Map[i].Priority)!=Find(Map[i].Next)) { Union(Map[i].Priority,Map[i].Next); count++;

if(Map[i].Priority>Map[i].Next)

cout<

cout<

//--------------------------------------floyd算法---------------------------------------------------------------// //图的创建

void F_Creategraph(F_MGraph *F_MGraph){ cout << \请输入顶点数和边数\

cin >> F_MGraph->Vcount >> F_MGraph->Ecount;

for (int row = 1; row <= F_MGraph->Vcount; row++){ //初始化为无穷,即不连通 for (int col = 1; col <= F_MGraph->Vcount; col++){ F_MGraph->edges[row][col] = MAX_VALUE; } }

cout << \请输入起始结点 最终结点 权重\ for (int i = 1; i <= F_MGraph->Ecount; i++){ //赋值 cin >> row >> col >> weight;

F_MGraph->edges[row][col] = weight; } }

//佛洛依德算法

void Floyd(F_MGraph *F_MGraph, int **iArrPath){ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){ iArrPath[i][j] = i; } } //初始化路径表

for (int k = 1; k <= F_MGraph->Vcount; k++){ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){ if (F_MGraph->edges[i][k] + F_MGraph->edges[k][j] <

6 / 22

石家庄铁道大学实习报告

F_MGraph->edges[i][j]){

F_MGraph->edges[i][j] = F_MGraph->edges[i][k] F_MGraph->edges[k][j];

iArrPath[i][j] = iArrPath[k][j]; } } } } }

//打印佛洛依德算法最短路径

void PrintResult(F_MGraph *F_MGraph, int **iArrPath){ cout << \起点 ->终点\\t距离\\t\\t最短路径\ for (int i = 1; i <= F_MGraph->Vcount; i++){ for (int j = 1; j <= F_MGraph->Vcount; j++){ if (i != j){

cout << i << \

if (F_MGraph->edges[i][j] == MAX_VALUE){ cout << \无连通路径\ } else{

cout << F_MGraph->edges[i][j] << \ std::stack stackVertices; do {

k = iArrPath[i][k]; stackVertices.push(k); } while (k != i);

cout << stackVertices.top(); stackVertices.pop();

unsigned int nLength = stackVertices.size();

for (unsigned int nIndex = 0; nIndex < nLength; nIndex++) {

cout << \ stackVertices.pop(); }

cout << \ } } } } }

//调用弗洛伊德相关代码 void show_floyd(){

for (int i = 0; i < MAX_VALUE; i++){ iArrPath[i] = new int[MAX_VALUE];

7 / 22

+

石家庄铁道大学实习报告

}

F_MGraph F_MGraph;

for (int i = 0; i < MAX_VALUE; i++){

F_MGraph.edges[i] = new int[MAX_VALUE]; }

F_Creategraph(&F_MGraph); Floyd(&F_MGraph, iArrPath);

PrintResult(&F_MGraph, iArrPath); }

//-----------------------------Dijkstra算法------------------------------------// //创建图函数

void createGraph(HeadNode *G, int nodeNum, int arcNum) {//G表示指向头结点数组的第一个结点的指针 nodeNum表示结点个数 arcNum表示边的个数

cout << \开始创建图(\ << \ //初始化头结点

for (int i = 0; i < nodeNum; i++) {

G[i].nodeName = i+1; //位置0上面存储的是结点v1,依次类推 G[i].inDegree = 0; //入度为0 G[i].link = NULL; //指针置空 }

//给边赋权值

for (int j = 0; j < arcNum; j++) {

int begin, end, weight; //起点 终点 权值 cout << \请输入 起始顶点 结束顶点 权值: \

cin >> begin >> end >> weight; //输入起点 终点 权值

D_Node *node = new D_Node; //创建边表插入链接表 node->adjvex = end - 1; //记录终点信息 node->weight = weight; //赋权值

++G[end-1].inDegree; //边的终点入度加1

node->next = G[begin-1].link; //前插法 即后输入的先打印（打印图的时候是倒着的） G[begin-1].link = node; //插入链接表的第一个位置 } }

//打印图函数

void printGraph(HeadNode *G, int nodeNum) { //输出结点入度及以其为起点的边

for (int i = 0; i < nodeNum; i++) {

cout << \结点v\的入度为\以它为起始顶点的边为(起点---权重---终点): \ D_Node *node = G[i].link;

while (node != NULL) { //依附于该顶点的指针不为空，即还存在以该结点为起点的边

cout << \<< G[i].nodeName<<\<< G[node->adjvex].nodeName<

8 / 22

石家庄铁道大学实习报告

node = node->next; //依次向后遍历 }

cout << endl; } }

//得到begin->end权重

int getWeight(HeadNode *G, int begin, int end) { D_Node *node = G[begin-1].link; while (node) {

if (node->adjvex == end - 1) { return node->weight; }

node = node->next; } }

//从begin开始，计算其到每一个顶点的最短路径 void Dijkstra(HeadNode *G, int nodeNum, int begin) { //初始化所有结点的

for (int i = 0; i < nodeNum; i++) {

G[i].d = INT_MAX; //到每一个顶点的距离初始 …… 此处隐藏：2188字，全部文档内容请下载后查看。喜欢就下载吧 ……