图的最短路径算法实现实现.zip

图的最短路径算法实现实现

#include 
#include 
#include 
 
 
#define MAX         100                 // 矩阵最大容量
#define INF         65535        		// 最大值65535
#define isLetter（a） （（（（a）>=‘a‘）&&（（a）<=‘z‘）） || （（（a）>=‘A‘）&&（（a）<=‘Z‘）））
#define LENGTH（a）   （sizeof（a）/sizeof（a[0]））
 
// 图的邻接矩阵存储
typedef struct _graph
{
    char vexs[MAX];       // 顶点集合
    int vexnum;           // 顶点数
    int edgnum;           // 边数
    int matrix[MAX][MAX]; // 邻接矩阵
}Graph *PGraph;
 
// 边的结构体
typedef struct _EdgeData
{
    char start; // 边的起点
    char end;   // 边的终点
    int weight; // 边的权重
}EData;
 
/*
 * 返回ch在matrix矩阵中的位置
 */
static int get_position（Graph G char ch）
{
    int i;
    for（i=0; i        if（G.vexs[i]==ch）
            return i;
    return -1;
}
 
/*
 * 读取一个输入字符
 */
static char read_char（）
{
    char ch;
 
    do {
        ch = getchar（）;
    } while（!isLetter（ch））;
 
    return ch;
}
 
/*
 * 创建图（自己输入）
 */
Graph* create_graph（）
{
    char c1 c2;
    int v e;
    int i j weight p1 p2;
    Graph* pG;
    
    // 输入“顶点数“和“边数“
    printf（“请输入顶点的数目:\n “）;
    scanf（“%d“ &v）;
    printf（“请输入边的数目: \n“）;
    scanf（“%d“ &e）;
    if （ v < 1 || e < 1 || （e > （v * （v-1））））
    {
        printf（“输入有误！！!\n“）;
        return NULL;
    }
    
    if （（pG=（Graph*）malloc（sizeof（Graph））） == NULL ）
        return NULL;
    memset（pG 0 sizeof（Graph））;						//初始化
 
    // 初始化“顶点数“和“边数“
    pG->vexnum = v;
    pG->edgnum = e;
    // 初始化“顶点“
    for （i = 0; i < pG->vexnum; i++）
    {
        printf（“vertex（%d）: “ i）;
        pG->vexs[i] = read_char（）;
    }
 
    // 1. 初始化“边“的权值
    for （i = 0; i < pG->vexnum; i++）
    {
        for （j = 0; j < pG->vexnum; j++）
        {
            if （i==j）
                pG->matrix[i][j] = 0;
            else
                pG->matrix[i][j] = INF;
        }
    }
    // 2. 初始化“边“的权值: 根据用户的输入进行初始化
    for （i = 0; i < pG->edgnum; i++）
    {
        // 读取边的起始顶点，结束顶点，权值
        printf（“edge（%d）:“ i）;
        c1 = read_char（）;
        c2 = read_char（）;
        scanf（“%d“ &weight）;
 
        p1 = get_position（*pG c1）;
        p2 = get_position（*pG c2）;
        if （p1==-1 || p2==-1）
        {
            printf（“输入有误!!!\n“）;
            free（pG）;
            return NULL;
        }
 
        pG->matrix[p1][p2] = weight;
        pG->matrix[p2][p1] = weight;
    }
 
    return pG;
}
 
/*
 * 创建图（用已提供的矩阵）
 */
Graph* create_example_graph（）
{
    char vexs[] = {‘A‘ ‘B‘ ‘C‘ ‘D‘ ‘E‘ ‘F‘ ‘G‘};
    int matrix[][9] = {
             /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
      /*A*/ {   0  12 INF INF INF  16  14}
      /*B*/ {  12   0  10 INF INF   7 INF}
      /*C*/ { INF  10   0   3   5   6 INF}
      /*D*/ { INF INF   3   0   4 INF INF}
      /*E*/ { INF INF   5   4   0   2   8}
      /*F*/ {  16   7   6 INF   2   0   9}
      /*G*/ {  14 IN

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-12-09 12:16  计科1702 2017040306陈家辉题目6.6--程序题--图的最短路径算法实现实现\
     文件       14431  2018-12-09 12:15  计科1702 2017040306陈家辉题目6.6--程序题--图的最短路径算法实现实现\题目6.6--程序题--图的最短路径算法实现.cpp
     文件      141247  2018-12-09 12:15  计科1702 2017040306陈家辉题目6.6--程序题--图的最短路径算法实现实现\题目6.6--程序题--图的最短路径算法实现.exe