| 网站首页 | 技术文章 | 下载频道 | 博客 | 编程论坛 |
 
| 技术教程首页 | 开发语言 | WEB开发 | .NET技术 | 数据库 | 操作系统 | 网页制作 |
 
 
您现在的位置: 编程中国 >> 技术教程 >> 开发语言 >> 数据结构 >> 正文
  ►  有向图转换&遍历&拓扑&最短路径
有向图转换&遍历&拓扑&最短路径
作者:haroldi    阅读人次:……    文章来源:本站原创    发布时间:2007/6/12    网友评论()条
 

原帖及讨论:http://bbs.bccn.net/thread-130955-1-1.html

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MaxStr 20
typedef int Status;
typedef int ElemType;
typedef struct{    
    ElemType VNode;
    int indgree;
    }VexType;
typedef struct Arc{
    VexType Adj;
    unsigned int Weight;
    struct Arc *NextArc;
    }ArcType;
typedef struct{                                    
    VexType *Vex;
    ArcType **FirstArc;                  //邻接表;
//    ArcType **InvertArc;               //逆邻接表;
    int VexNums;                         //顶点总数;
    }DLGraph;                            //图的邻接表结构定义;
typedef struct{
    ElemType *Vex;
    unsigned int **Arc;                                
    int VexNums;
    }DMGraph;                            //图的邻接矩阵结构定义;
//========================================================================================
Status CreateDMGraph(DMGraph *DMG);            //创建图的邻接矩阵;
Status DMG_Traver(DMGraph DMG);                //邻接矩阵的遍历;
Status DMG_DFS(DMGraph DMG,int v,int *Visited);      //邻接矩阵深度遍历(递  归);
Status DMG_DFS_Uni(DMGraph DMG,int v,int *Visited);  //邻接矩阵深度遍历(非递归);
Status DMG_BFS(DMGraph DMG,int v,int *Visited);      //邻接矩阵广度遍历;
Status DMG2DLG(DMGraph DMG,DLGraph *DLG);      //邻接矩阵转换为邻接表;
Status DLG_Traver(DLGraph DLG);                //邻 接 表的遍历;
Status DLG_DFS(DLGraph DLG,int v,int *Visited);      //邻 接 表深度遍历(递  归);
Status DLG_DFS_Uni(DLGraph DLG,int v,int *Visited);  //邻 接 表深度遍历(非递归);
Status DLG_BFS(DLGraph DLG,int v,int *Visited);      //邻 接 表广度遍历;
//---------------------------------------------------------
Status Topsort(DLGraph DLG,ElemType **ts);        //邻接表有向图的Topsort;
Status Dijkstra(DMGraph DMG,ElemType v,unsigned int *dist);//Dijkstra;
Status PRN_DK(DMGraph DMG,unsigned int ***dis);        //输出Dijkstra算法;
Status Floyd(DMGraph DMG,unsigned int ***flyd);        //Floyd;
Status PRN_DMGraph(DMGraph DMG);            //输出邻接矩阵;
Status PRN_DLGraph(DLGraph DLG);            //输出邻接表;
//========================================================================================
int main(void)
{
    int i,j;
    DMGraph DMG;    
    DLGraph DLG;
    ElemType *ts;
    unsigned int **dist,**flyd;
    printf(    " 一、创立有向图的邻接矩阵:\n");    
        CreateDMGraph(&DMG);
        PRN_DMGraph(DMG);
    printf("\n\n 二、有向图-邻接矩阵的遍历:\n");
        DMG_Traver(DMG);
    printf("\n\n 三、邻接矩阵转换为邻接表:\n");
        DMG2DLG(DMG,&DLG);    
        PRN_DLGraph(DLG);
    printf("\n\n 四、有向图-邻接表的遍历:\n");
        DLG_Traver(DLG);
    printf("\n\n 五、邻接表有向图的拓扑排序:\n");
        Topsort(DLG,&ts);
    printf("\n\n\n");system("pause");
    printf("\n\n 六、邻接矩阵有向图的各点最短路径:\n\n  1. Dijkstra(迪杰斯特拉算法):");
        PRN_DK(DMG,&dist);
    printf("\n\n\n  2. Floyd(弗洛伊德算法):");
        Floyd(DMG,&flyd);

    printf("\n");    system("pause");
    printf("\n\n\nDijkstra最短路径测试输出:\n 某两点 : 最短路径");
    for(i = 1;i <= DMG.VexNums;i++)
        for(j = 1;j <= DMG.VexNums;j++)
            if(dist[i][j] < INT_MAX) printf("\n[%2d,%2d] : %5d ",i,j,dist[i][j]);
    printf("\n\nFloyd最短路径测试输出:\n 某两点 : 最短路径");
    for(i = 1;i <= DMG.VexNums;i++)
        for(j = 1;j <= DMG.VexNums;j++)
            if(flyd[i][j] < INT_MAX) printf("\n[%2d,%2d] : %5d ",i,j,flyd[i][j]);
    printf("\n");    system("pause");
    return 0;
}

//    文件格式参见"无向图"说明:
//http://bbs.bc-cn.net/dispbbs.asp?boardID=179&ID=129767

[1] [2] 下一页

 

 
文章录入:静夜思    责任编辑:静夜思 
  • 上一篇文章:

  • 下一篇文章:

  •  
    相关文章
    没有相关文章
    原创地带
    24小时热门帖子