/*
图（有向有权图）
2018.12.16 初步完成
2018.12.18 加入文件 *** 作
*/
#include
#include
#define MAXSIZE 100
#define INF 1000
int visit[MAXSIZE];//【深度/广度优先遍历使用】全局数组，存放元素访问标记，访问为1，未访问为0
int dist[MAXSIZE];//【单源最短路径使用】从源结点到每个结点的最短路径的长度
int path[MAXSIZE];//【单源最短路径使用】保存path[vi]从v0到vi最短路径上vi的前一个结点
//【边--链表存储】定义 边 ------存储边的数据结构是 链表
typedef struct EdgeNode
{
int adjacentVertex;//该边指向的结点位置（下一个节点)，相当于指是记录指向的结点的下标 adjacent vertex 临接结点
int weight;//定义边的权值
struct EdgeNode *nextEdge;//指向下一条边的指针
}EdgeNode;
//【顶点--数组存储】定义 顶点 -------存储顶点的数据结构是 数组
typedef struct VertexNode
{
char data;//顶点信息
EdgeNode *firstEdge;//指向第一条边的指针
}VertexNode;
//定义 图
typedef struct
{
VertexNode adjacentList[MAXSIZE];//【邻接链表表头数组】[是一个结构体数组]（每个元素都含有 顶点信息 和 指向第一条边的指针）
int vertexnumber;//顶点数
int edgeNumber;//边数
int edgeWeight[MAXSIZE][MAXSIZE];//【有向有权图-邻接矩阵】两顶点的权值（有向有权图），无法直接到达设为INF
}Graph;
//置0一个一维数组
voID setZero(int *visit)
{
for (int i = 0; i < MAXSIZE; i++)
{
visit[i] = 0;
}
return;
}
//链表建立方式为 头插法
voID createGraphF(Graph *g)
{
//初始化图的 顶点数 边数
int vertexnumber;
int edgeNumber;
printf("请输入要建立的图的 顶点数 边数：");
scanf("%d %d",&vertexnumber,&edgeNumber);
g->vertexnumber = vertexnumber;
g->edgeNumber = edgeNumber; //图的顶点数和边数初始化完毕
//初始化图的 权重数组 全部赋值为INF
for (int i = 0; i < g->vertexnumber; i++)
for (int j = 0; j < g->vertexnumber; j++)
{
g->edgeWeight[i][j] = INF;
}
//建立了只有顶点的图
for(int i =0;i { g->adjacentList[i].data = i; g->adjacentList[i].firstEdge = NulL; } EdgeNode *newNode;//用来临时存放边结点 //插入边--边的开始 结束/边的权值 for (int i = 0; i < g->edgeNumber; i++) { //插入边和权值 int startSubscript;//前驱结点的下标 int endSubscript;//后继结点的下表 int weight;//边的权重 scanf("%d %d %d",&startSubscript,&endSubscript,&weight); g->edgeWeight[startSubscript][endSubscript] = weight;//一边输入，一遍把图的 权重二维数组建立好 newNode = (EdgeNode*)malloc(sizeof(EdgeNode));//申请边的空间 newNode->adjacentVertex = endSubscript;//边的后继结点 newNode->weight = weight;//边的权值 newNode->nextEdge = g->adjacentList[startSubscript].firstEdge;//新结点指向 表头结点的下一结点（是一条边NulL） g->adjacentList[startSubscript].firstEdge = newNode; //表头结点的下一结点 指向 新结点 } } //链表建立方式为 尾插法 voID createGraphR(Graph *g) { //初始化图的 顶点数 边数 int vertexnumber; int edgeNumber; printf("请输入要建立的图的 顶点数 边数："); //直接通过文件输入数据 file *fin; fin = fopen("input.txt","r"); fscanf(fin,"%d %d",&edgeNumber); //scanf("%d %d",&edgeNumber); g->vertexnumber = vertexnumber; g->edgeNumber = edgeNumber; //图的顶点数和边数初始化完毕 //初始化图的 权重数组 全部赋值为INF for(int i =0;i for (int j = 0; j < g->vertexnumber; j++) { g->edgeWeight[i][j] = INF; } //建立了只有顶点的图 for (int i = 0; i < vertexnumber; i++) { g->adjacentList[i].data = i; g->adjacentList[i].firstEdge = NulL; } EdgeNode *newNode;//用来临时存放边结点 //插入边--边的开始 结束/边的权值 //边结点temp直接定位到第一个边结点，用来辅助进行尾插法 EdgeNode *temp; //temp = (EdgeNode*)malloc(sizeof(EdgeNode)); for (int i = 0; i < g->edgeNumber; i++) { //插入边和权值 int startSubscript;//前驱结点的下标 int endSubscript;//后继结点的下表 int weight;//边的权重 //scanf("%d %d %d",&weight); fscanf(fin,"%d %d %d",&weight); g->edgeWeight[startSubscript][endSubscript] = weight;//一边输入，一遍把图的 权重二维数组建立好 newNode = (EdgeNode*)malloc(sizeof(EdgeNode));//申请边的空间 newNode->nextEdge = NulL;//因为要进行尾插法，所以newNode作为最后一个结点，其next为NulL newNode->adjacentVertex = endSubscript;//边的后继结点 newNode->weight = weight;//边的权值 //如果链表只有表头结点，直接将 newNode接在表头结点（第一个结点）后面 if (g->adjacentList[startSubscript].firstEdge == NulL) { newNode->nextEdge = g->adjacentList[startSubscript].firstEdge;//新结点指向 表头结点的下一结点（是一条边NulL） g->adjacentList[startSubscript].firstEdge = newNode; //表头结点的下一结点 指向 新结点 } //如果链表既有表头结点，又有边结点，那么直接定位到边结点，然后进行循环判空，找到 最后一个边结点 //然后在最后一个边结点后面插入 newNode else //if(g->adjacentList[startSubscript].firstEdge != NulL) { temp = g->adjacentList[startSubscript].firstEdge;//将第一个边结点 赋给 temp，由temp辅助尾插法进行 *** 作 while (temp->nextEdge != NulL)//temp不是最后一个边结点，那么temp往后移动 { temp = temp->nextEdge; } //接下来，如果temp是最后一个结点，那么将newNode作为 temp->nextEdge,及将newNode作为最后的边结点 temp->nextEdge = newNode; } } } //以邻接链表的方式打印图 voID printGraph(Graph g,file* fout) { printf("图的邻接链表表示为："); int i; EdgeNode *p; for (i = 0; i < g.vertexnumber; i++) { printf("n%d",g.adjacentList[i].data);//打印表头结点 fprintf(fout,"n%d",g.adjacentList[i].data);//打印表头结点 p = g.adjacentList[i].firstEdge;//p现在是第一条边 while (p != NulL) { printf("-->%d",p->adjacentVertex); //打印第一条边指向的顶点 fprintf(fout,"-->%d",p->adjacentVertex); //打印第一条边指向的顶点 p = p->nextEdge;//之后p到下一条边 } } return; printf("n"); } //以邻接表的方式打印图 voID printWeight(Graph g,file* fout) { printf("图的邻接矩阵为：n"); fprintf(fout,"图的邻接矩阵为：n"); for(int i =0;i { for (int j = 0; j < g.vertexnumber; j++) { printf("%4d ",g.edgeWeight[i][j]); fprintf(fout,"%4d ",g.edgeWeight[i][j]); } printf("n"); fprintf(fout,"n"); } } //深度优先遍历 voID dfs(Graph *g,int vertex,file* fout) { //【开始】遍历 从顶点vertex出发的连通子图 EdgeNode *p; visit[vertex] = 1; printf("V%d ",vertex); //遍历 *** 作 fprintf(fout,"V%d ",vertex); //遍历 *** 作 p = g->adjacentList[vertex].firstEdge;//p指向表头结点指向的第一条边 while (p != NulL) { if (visit[p->adjacentVertex] == 0) dfs(g,p->adjacentVertex,fout);//因为函数定义 g为Graph类型的指针，所以在接下来的递归中语句不会出错 p = p->nextEdge; } //【结束】遍历 从顶点vertex出发的连通子图 //【开始】遍历其他 子图 for (int i = 0; i < g->vertexnumber; i++) // { if (visit[i] == 0) { dfs(g,i,fout);//因为函数定义 g为Graph类型的指针，所以在接下来的递归中语句不会出错 } } //【结束】遍历其他 子图 } //广度优先遍历 voID bfs(Graph *g,file* fout) { EdgeNode *p; int queue[MAXSIZE],front = 0,rear = 0;//队列的便捷定义方式 visit[vertex] = 1; //全局数组标记为1：表示已经访问过 printf("V%d ",vertex);//【遍历 *** 作】访问过后打印输出 fprintf(fout,vertex);//【遍历 *** 作】访问过后打印输出 rear = (rear + 1) % MAXSIZE;//入队 *** 作 queue[rear] = vertex; int temp; while (front != rear)//当队列空的时候说明遍历完成 { front = (front + 1) % MAXSIZE;//顶点出队 temp = queue[front]; p = g->adjacentList[temp].firstEdge;//将p指向出队顶点的第一条边 while (p != NulL) { if (visit[p->adjacentVertex] == 0)//如果p的邻接结点未被访问，则入队 { visit[p->adjacentVertex] = 1; printf("V%d ",p->adjacentVertex); fprintf(fout,p->adjacentVertex); rear = (rear + 1) % MAXSIZE;//入队 *** 作 queue[rear] = p->adjacentVertex; } p = p->nextEdge; } } //【开始】遍历其他 子图 for (int i = 0; i < g->vertexnumber; i++) // { if (visit[i] == 0) { bfs(g,fout);//因为函数定义 g为Graph类型的指针，所以在接下来的递归中语句不会出错 } } //【结束】遍历其他 子图 } //dijkstra算法-有向有权图-单源最短路径算法 voID dijkstra(Graph g,int v,int *dist,int *path) { int set[MAXSIZE];//顶点已进入最短路径标志位 int min,j,u; //初始化算法所用的数组 for (i = 0; i < g.vertexnumber; i++) { dist[i] = g.edgeWeight[v][i]; set[i] = 0; if (g.edgeWeight[v][i] < INF) path[i] = v; else path[i] = -1; } set[v] = 1; path[v] = -1; //关键算法 for (i = 0; i < g.vertexnumber; i++) { //从不在最短路径的顶点中，找出dist[]最短的，加入最短路径 min = INF; for(j=0;j if (set[j] == 0 && dist[j] < min) { u = j; min = dist[j]; } set[u] = 1; //更新dist[] for (j = 0; j < g.vertexnumber; j++) { if (set[j] == 0 && dist[u]+g.edgeWeight[u][j] { dist[j] = dist[u] + g.edgeWeight[u][j]; path[j] = u; } } } } //需要创建两个文件 input.txt output.txt //数据内容输入文件 input.txt /* 6 11 0 1 50 0 2 10 0 4 45 1 2 15 1 4 10 2 0 20 2 3 15 3 1 20 3 4 35 4 3 30 5 3 3 */ int main() { Graph g; //createGraphF(&g); createGraphR(&g); file* fout; fout = fopen("output.txt","w"); printGraph(g,fout); printf("nn"); fprintf(fout,"nn"); printWeight(g,"nn"); printf("从顶点1开始的深度优先遍历："); fprintf(fout,"从顶点1开始的深度优先遍历："); setZero(visit); dfs(&g,1,"nn"); printf("从顶点1开始的广度优先遍历："); fprintf(fout,"从顶点1开始的广度优先遍历："); setZero(visit); bfs(&g,"nn"); printf("顶点0到顶点的最短路径：n"); fprintf(fout,"顶点0到顶点的最短路径：n"); int start = 0; dijkstra(g,start,dist,path); for (int i = 0; i < g.vertexnumber; i++) { if (i == start)continue; printf("V%d->V%d：%dn",dist[i]); fprintf(fout,"V%d->V%d：%dn",dist[i]); } return 0; } 以上是内存溢出为你收集整理的数据结构--基于天勤--有向有权图全部内容，希望文章能够帮你解决数据结构--基于天勤--有向有权图所遇到的程序开发问题。 如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）