数据结构--基于天勤--有向有权图
|
/* 图（有向有权图） 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; } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |