黑龙江新闻夜航/短视频seo是什么
/* *Copyright (c) 2016,烟台大学计算机学院 *All rights reserved. *文件名称：graph.cpp *作者：衣龙川 *完成日期：2016年12月8日 *版本号：vc++6.0 * *问题描述： 从一个顶点到其余各顶点的最短路径*输入描述：无 *程序输出：
*/
graph.cpp：
#include <stdio.h>
#include <malloc.h>
#include "graph.h"//功能：由一个反映图中顶点邻接关系的二维数组，构造出用邻接矩阵存储的图
//参数：Arr - 数组名，由于形式参数为二维数组时必须给出每行的元素个数，在此将参数Arr声明为一维数组名（指向int的指针）
// n - 矩阵的阶数
// g - 要构造出来的邻接矩阵数据结构
void ArrayToMat(int *Arr, int n, MGraph &g)
{int i,j,count=0; //count用于统计边数，即矩阵中非0元素个数g.n=n;for (i=0; i<g.n; i++)for (j=0; j<g.n; j++){g.edges[i][j]=Arr[i*n+j]; //将Arr看作n×n的二维数组，Arr[i*n+j]即是Arr[i][j]，计算存储位置的功夫在此应用if(g.edges[i][j]!=0 && g.edges[i][j]!=INF)count++;}g.e=count;
}void ArrayToList(int *Arr, int n, ALGraph *&G)
{int i,j,count=0; //count用于统计边数，即矩阵中非0元素个数ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph));G->n=n;for (i=0; i<n; i++) //给邻接表中所有头节点的指针域置初值G->adjlist[i].firstarc=NULL;for (i=0; i<n; i++) //检查邻接矩阵中每个元素for (j=n-1; j>=0; j--)if (Arr[i*n+j]!=0) //存在一条边，将Arr看作n×n的二维数组，Arr[i*n+j]即是Arr[i][j]{p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个节点*pp->adjvex=j;p->info=Arr[i*n+j];p->nextarc=G->adjlist[i].firstarc; //采用头插法插入*pG->adjlist[i].firstarc=p;}G->e=count;
}void MatToList(MGraph g, ALGraph *&G)
//将邻接矩阵g转换成邻接表G
{int i,j;ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph));for (i=0; i<g.n; i++) //给邻接表中所有头节点的指针域置初值G->adjlist[i].firstarc=NULL;for (i=0; i<g.n; i++) //检查邻接矩阵中每个元素for (j=g.n-1; j>=0; j--)if (g.edges[i][j]!=0) //存在一条边{p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个节点*pp->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc; //采用头插法插入*pG->adjlist[i].firstarc=p;}G->n=g.n;G->e=g.e;
}void ListToMat(ALGraph *G,MGraph &g)
//将邻接表G转换成邻接矩阵g
{int i,j;ArcNode *p;g.n=G->n; //根据一楼同学“举报”改的。g.n未赋值，下面的初始化不起作用g.e=G->e;for (i=0; i<g.n; i++) //先初始化邻接矩阵for (j=0; j<g.n; j++)g.edges[i][j]=0;for (i=0; i<G->n; i++) //根据邻接表，为邻接矩阵赋值{p=G->adjlist[i].firstarc;while (p!=NULL){g.edges[i][p->adjvex]=p->info;p=p->nextarc;}}
}void DispMat(MGraph g)
//输出邻接矩阵g
{int i,j;for (i=0; i<g.n; i++){for (j=0; j<g.n; j++)if (g.edges[i][j]==INF)printf("%3s","∞");elseprintf("%3d",g.edges[i][j]);printf("\n");}
}void DispAdj(ALGraph *G)
//输出邻接表G
{int i;ArcNode *p;for (i=0; i<G->n; i++){p=G->adjlist[i].firstarc;printf("%3d: ",i);while (p!=NULL){printf("-->%d/%d ",p->adjvex,p->info);p=p->nextarc;}printf("\n");}
}graph.h：
#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED#define MAXV 100 //最大顶点个数
#define INF 32767 //INF表示∞
typedef int InfoType;//以下定义邻接矩阵类型
typedef struct
{int no; //顶点编号InfoType info; //顶点其他信息，在此存放带权图权值
} VertexType; //顶点类型typedef struct //图的定义
{int edges[MAXV][MAXV]; //邻接矩阵int n,e; //顶点数，弧数VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵类型//以下定义邻接表类型
typedef struct ANode //弧的结点结构类型
{int adjvex; //该弧的终点位置struct ANode *nextarc; //指向下一条弧的指针InfoType info; //该弧的相关信息,这里用于存放权值
} ArcNode;typedef int Vertex;typedef struct Vnode //邻接表头结点的类型
{Vertex data; //顶点信息int count; //存放顶点入度,只在拓扑排序中用ArcNode *firstarc; //指向第一条弧
} VNode;typedef VNode AdjList[MAXV]; //AdjList是邻接表类型typedef struct
{AdjList adjlist; //邻接表int n,e; //图中顶点数n和边数e
} ALGraph; //图的邻接表类型//功能：由一个反映图中顶点邻接关系的二维数组，构造出用邻接矩阵存储的图
//参数：Arr - 数组名，由于形式参数为二维数组时必须给出每行的元素个数，在此将参数Arr声明为一维数组名（指向int的指针）
// n - 矩阵的阶数
// g - 要构造出来的邻接矩阵数据结构
void ArrayToMat(int *Arr, int n, MGraph &g); //用普通数组构造图的邻接矩阵
void ArrayToList(int *Arr, int n, ALGraph *&); //用普通数组构造图的邻接表
void MatToList(MGraph g,ALGraph *&G);//将邻接矩阵g转换成邻接表G
void ListToMat(ALGraph *G,MGraph &g);//将邻接表G转换成邻接矩阵g
void DispMat(MGraph g);//输出邻接矩阵g
void DispAdj(ALGraph *G);//输出邻接表G#endif // GRAPH_H_INCLUDEDmain.cpp：
#include <stdio.h>
#include <malloc.h>
#include "graph.h"
#define MaxSize 100
void Ppath(int path[],int i,int v) //前向递归查找路径上的顶点
{int k;k=path[i];if (k==v) return; //找到了起点则返回Ppath(path,k,v); //找顶点k的前一个顶点printf("%d,",k); //输出顶点k
}
void Dispath(int dist[],int path[],int s[],int n,int v)
{int i;for (i=0; i<n; i++)if (s[i]==1){printf(" 从%d到%d的最短路径长度为:%d\t路径为:",v,i,dist[i]);printf("%d,",v); //输出路径上的起点Ppath(path,i,v); //输出路径上的中间点printf("%d\n",i); //输出路径上的终点}else printf("从%d到%d不存在路径\n",v,i);
}
void Dijkstra(MGraph g,int v)
{int dist[MAXV],path[MAXV];int s[MAXV];int mindis,i,j,u;for (i=0; i<g.n; i++){dist[i]=g.edges[v][i]; //距离初始化s[i]=0; //s[]置空if (g.edges[v][i]<INF) //路径初始化path[i]=v;elsepath[i]=-1;}s[v]=1;path[v]=0; //源点编号v放入s中for (i=0; i<g.n; i++) //循环直到所有顶点的最短路径都求出{mindis=INF; //mindis置最小长度初值for (j=0; j<g.n; j++) //选取不在s中且具有最小距离的顶点uif (s[j]==0 && dist[j]<mindis){u=j;mindis=dist[j];}s[u]=1; //顶点u加入s中for (j=0; j<g.n; j++) //修改不在s中的顶点的距离if (s[j]==0)if (g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j]){dist[j]=dist[u]+g.edges[u][j];path[j]=u;}}Dispath(dist,path,s,g.n,v); //输出最短路径
}int main()
{MGraph g;int A[7][7]={{0,4,6,6,INF,INF,INF},{INF,0,1,INF,7,INF,INF},{INF,INF,0,INF,6,4,INF},{INF,INF,2,0,INF,5,INF},{INF,INF,INF,INF,0,INF,6},{INF,INF,INF,INF,1,0,8},{INF,INF,INF,INF,INF,INF,0}};ArrayToMat(A[0], 7, g);Dijkstra(g,0);return 0;
}
运行截图：
