原帖及讨论：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    1 2 下一页 尾页