/*
图（有向有权图）
2018.12.16 初步完成
2018.12.18 加入文件操作
*/
#include<stdio.h>
#include<stdlib.h>
#d...
/*
图（有向有权图）
2018.12.16 初步完成
2018.12.18 加入文件操作
*/
#include<stdio.h>
#include<stdlib.h>
#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<vertexNumber;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\", &vertexNumber, &edgeNumber);
//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 < 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\", &startSubscript, &endSubscript, &weight);
fscanf(fin,\"%d %d %d\", &startSubscript, &endSubscript, &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<g.vertexNumber;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, int vertex, FILE* fout)
{
EdgeNode *p;
int queue[MAXSIZE], front = 0, rear = 0;//队列的便捷定义方式
visit[vertex] = 1; //全局数组标记为1：表示已经访问过
printf(\"V%d \", vertex);//【遍历操作】访问过后打印输出
fprintf(fout,\"V%d \", 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,\"V%d \", 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, i,fout);//因为函数定义 g为Graph类型的指针，所以在接下来的递归中语句不会出错
}
}
//【结束】遍历其他 子图
}
//dijkstra算法-有向有权图-单源最短路径算法
void dijkstra(Graph g, int v, int *dist, int *path)
{
int set[MAXSIZE];//顶点已进入最短路径标志位
int min, i, 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<g.vertexNumber;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[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(\"\\n\\n\"); fprintf(fout,\"\\n\\n\");
printWeight(g,fout);
printf(\"\\n\\n\"); fprintf(fout, \"\\n\\n\");
printf(\"从顶点1开始的深度优先遍历：\");
fprintf(fout,\"从顶点1开始的深度优先遍历：\");
setZero(visit);
dfs(&g, 1,fout);
printf(\"\\n\\n\"); fprintf(fout, \"\\n\\n\");
printf(\"从顶点1开始的广度优先遍历：\");
fprintf(fout,\"从顶点1开始的广度优先遍历：\");
setZero(visit);
bfs(&g, 1,fout);
printf(\"\\n\\n\"); fprintf(fout, \"\\n\\n\");
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：%d\\n\",start,i, dist[i]);
fprintf(fout,\"V%d->V%d：%d\\n\", start, i, dist[i]);
}
return 0;
}
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：【JavaWeb】客户关系管理系统 下一篇：【JavaWeb】权限管理系统
