IT小白

这个屌丝很懒，什么也没留下！

热门标签

南京邮电大学数据结构实验三（图的基本运算及飞机换乘次数最少问题）_图相关操作的实现南京邮电大学数据结构

作者：IT小白 | 2024-03-01 10:37:02

踩

图相关操作的实现南京邮电大学数据结构

文章目录

实验一、图的基本运算

1、邻接矩阵表示

（1）验证基本运算

a、邻接矩阵表示图的数据结构

//邻接矩阵的结构体定义
typedef struct {
    ElemType** a;     //邻接矩阵
    int n;            //图的当前顶点数
    int e;            //图的当前边数
    ElemType noEdge;  //两顶点间无边时的值
}mGraph;
1
2
3
4
5
6
7

分析：内含3个成员变量，分别为图的邻接矩阵二维数组，图的顶点数和图的边数。

b、图的初始化

//邻接矩阵的初始化
Status Init(mGraph* mg, int nSize, ElemType noEdgeValue) {
    int i, j;
    mg->n = nSize;               //初始化顶点数
    mg->e = 0;                   //初始化时没有边
    mg->noEdge = noEdgeValue;    //初始化没有边时的取值
    mg->a = (ElemType**)malloc(nSize * sizeof(ElemType*));  //生成长度为n的一维指针数组
    if (!mg->a) return ERROR;
    for (i = 0; i < mg->n; i++) {   //动态生成二维数组
        mg->a[i] = (ElemType*)malloc(nSize * sizeof(ElemType));
        for (j = 0; j < mg->n; j++) {
            mg->a[i][j] = mg->noEdge;  //初始化时权重都设为-1
        }
        mg->a[i][i] = 0;        //自回路设置为0
    }
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

分析：先为邻接矩阵申请动态空间，然后将每条边权值都设为1，其中自回路设置为0。

c、插入边

//邻接矩阵的边的插入
Status Insert(mGraph* mg, int u, int v, ElemType w) {
    if (u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v) return ERROR;
    if (mg->a[u][v] != mg->noEdge) return Duplicate;  //若待插入边已存在,则返回出错信息
    mg->a[u][v] = w;                                 //插入新边
    mg->e++;                                        //增加一条边
    return OK;
}
1
2
3
4
5
6
7
8

d、搜索边

//邻接矩阵的边的搜索
Status Exist(mGraph* mg, int u, int v) {
    if (u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v || mg->a[u][v] == mg->noEdge) return ERROR;
    return OK;
}
1
2
3
4
5

e、删除边

//邻接矩阵的边的删除
Status Remove(mGraph* mg, int u, int v) {
    if (u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v) return ERROR;
    if (mg->a[u][v] == mg->noEdge) return NotPresent;  //若待删除边不存在,则返回出错信息
    mg->a[u][v] = mg->noEdge;                         //删除边
    mg->e--;
    return OK;
}
1
2
3
4
5
6
7
8

f、图的销毁

//邻接矩阵的销毁,先释放一维数组,再释放指针数组
int Destory(mGraph* mg) {
    int i;
    for (i = 0; i < mg->n; i++) {
        free(mg->a[i]);  //释放n个一维数组的存储空间
    }
    free(mg->a);         //释放一维数组的存储空间
    return 1;
}
1
2
3
4
5
6
7
8
9

分析：先释放一维数组,再释放指针数组

（2）图的深度和宽度优先遍历(邻接矩阵)

a、深度优先遍历(DFS)

//邻接矩阵的单一顶点DFS
void DFS(int v, int visited[], mGraph g) {
    int j;
    printf("%d ", v);              //访问顶点v
    visited[v] = 1;               //为顶点v打上访问标记       
    for (j = 0; j < g.n; j++) {      //遍历v的邻接点
        if (!visited[j] && g.a[v][j] > 0) {  //当未被访问且有权值
            DFS(j, visited, g);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

b、邻接矩阵的深度优先算法（DFS）

//邻接矩阵DFS
void DFSGraph(mGraph g) {
    int i;
    int* visited = (int*)malloc(g.n * sizeof(int)); //动态生成标记数组visted
    for (i = 0; i < g.n; i++) {
        visited[i] = 0;          //visted数组初始化
    }                            //visted数组初始化
    for (i = 0; i < g.n; i++) {     //逐一检查每个顶点,若未被访问,则调用DFS
        if (!visited[i]) {   //当未被访问且有权值
            DFS(i, visited, g);
        }
    }
    free(visited);                       //释放visted数组
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

c、邻接矩阵的广度优先遍历(BFS)

//邻接矩阵的单一顶点BFS
void BFS(int v, int visited*, mGraph g) {
    Queue q;
    Create(&q, g.n);                        //初始化队列
    visited[v] = 1;                         //顶点v标记为已访问
    printf("%d ", v);                       //访问顶点v
    EnQueue(&q, v);                         //将顶点v放入队列
    while (!IsEmpty(&q)) {
        Front(&q, &v);
        DeQueue(&q);                                   //队首顶点出队列
        for (int i = 0; i < g.n; i++) {                //遍历v的每一项
            if (!visited[i] && g.a[v][i] > 0) {        //若未被访问且有权值,则将其访问并放入队列 
                visited[i] = 1;
                printf("%d ", i);
                EnQueue(&q, i);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

d、邻接矩阵的全图BFS

//邻接矩阵的全图BFS
void BFSGraph(mGraph g) {
    int i;
    int* visited = (int*)malloc(g.n * sizeof(int));     //动态生成visited数组
    for (i = 0; i < g.n; i++) {                         //初始化visited数组
        visited[i] = 0;
    }
    for (i = 0; i < g.n; i++) {                         //逐一检查每个顶点,若未被访问,则调用BFS
        if (!visited[i]) {
            BFS(i, visited, g);
        }
    }
    free(visited);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试数据：
在这里插入图片描述

2、邻接表表示

（1）验证基本运算

a、邻接表的数据结构

//邻接表的节点定义
typedef struct ENode {
    int adjVex;             //任意顶点u相邻的顶点
    ElemType w;             //边的权值
    struct ENode* nextArc;  //指向下一个边结点
}ENode; 
//邻接表的结构体定义
typedef struct {
    int n;             //图的当前顶点数
    int e;             //图的当前边数
    ENode** a;         //指向一维指针数组
}LGraph;
1
2
3
4
5
6
7
8
9
10
11
12

分析：内含三个成员变量，分别为图的顶点个数，图的边数和图的各个邻接表数组。

b、图的初始化(邻接表)

//邻接表的初始化
Status Init(LGraph* lg, int nSize) {
    int  i;
    lg->n = nSize;
    lg->e = 0;
    lg->a = (ENode**)malloc(nSize * sizeof(ENode*));  //动态生成长度为n的一维指针数组
    if (!lg->a) return ERROR;
    else {
        for (i = 0; i < lg->n; i++) {
            lg->a[i] = NULL;                        //将指针数组a置空
        }
        return OK;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

分析：

c、插入边(邻接表)

//邻接表的插入边
Status Insert(LGraph* lg, int u, int v, ElemType w) {
    ENode* p;
    if (u < 0 || v < 0 || u > lg->n - 1 || v > lg->n - 1 || u == v) return ERROR;
    if (Exist(lg, u, v)) return Duplicate;  //此边已存在,返回错误
    p = (ENode*)malloc(sizeof(ENode));   //为新的边结点分配存储空间
    p->adjVex = v;
    p->w = w;
    p->nextArc = lg->a[u];             //将新的边结点插入单链表的最前面
    lg->a[u] = p;
    lg->e++;                            //边加1
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

d、搜索边(邻接表)

//邻接表的搜索边
Status Exist(LGraph* lg, int u, int v) {
    ENode* p;
    if (u < 0 || v < 0 || u > lg->n - 1 || v > lg->n - 1 || u == v) return ERROR;
    p = lg->a[u];                   //指针p指向顶点u的单链表的第一个边结点
    while (p != NULL && p->adjVex != v) {
        p = p->nextArc;
    }
    if (!p) return ERROR;            //若未找到此边,则返回ERROR
    else return OK;
}
1
2
3
4
5
6
7
8
9
10
11

e、删除边(邻接表)

//邻接表的删除边
Status Remove(LGraph* lg, int u, int v) {
    ENode* p, * q;
    if (u < 0 || v < 0 || u > lg->n - 1 || v > lg->n - 1 || u == v) return ERROR;
    p = lg->a[u];
    q = NULL;
    while (p && p->adjVex != v) {         //查找待删除边是否存在
        q = p;
        p = p->nextArc;
    }
    if (!p) return NotPresent;          //p为空,待删除边不存在
    if (q) q->nextArc = p->nextArc;     //从单链表删除此边
    else lg->a[u] = p->nextArc;
    free(p);
    lg->e--;
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

分析：函数参数传入图对象和要删除的边的两个相邻节点。先检测要删除的边是否存在，若存在，则删除邻接表中的那个节点。

f、图的销毁(邻接表)

//邻接表的销毁
int Destory(LGraph* lg) {
    int i;
    ENode* p, * q;
    for (i = 0; i < lg->n; i++) {
        p = lg->a[i];                 //指针p指向顶点i的单链表的第一个边结点
        q = p;
        while (p) {                     //释放顶点i的单链表中所有边结点
            p = p->nextArc;
            free(q);
            q = p;
        }
    }
    free(lg->a);                     //释放一维指针数组a的存储空间
    return 1;                        //改为int型函数,有返回值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

分析：先释放存储邻接表的数组，再释放各个邻接表的空间。

（2）图的深度和宽度优先遍历(邻接表)

a、深度优先遍历(DFS)

//邻接表的单一顶点DFS
void DFS(int v, int visited[], LGraph g) {
    ENode* w;
    printf("%d ", v);                           //访问顶点v
    visited[v] = 1;                            //为顶点v打上访问标记
    for (w = g.a[v]; w; w = w->nextArc) {          //遍历v的邻接点
        if (!visited[w->adjVex]) {
            DFS(w->adjVex, visited, g);          //若w未被访问,则递归调用DFS
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

b、邻接表的全图DFS

//邻接表的全图DFS
void DFSGraph(LGraph g) {
    int i;
    int* visited = (int*)malloc(g.n * sizeof(int)); //动态生成标记数组visted
    for (i = 0; i < g.n; i++) {
        visited[i] = 0;                             //visted数组初始化
    }
    for (i = 0; i < g.n; i++) {                        //逐一检查每个顶点,若未被访问,则调用DFS
        if (!visited[i]) {
            DFS(i, visited, g);
        }
    }
    free(visited);                                 //释放visted数组
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

c、广度优先遍历(BFS)

//邻接表的单一顶点BFS
void BFS(int v, int visited[], LGraph g) {
    ENode* w;
    Queue q;
    Create(&q, g.n);                        //初始化队列
    visited[v] = 1;                        //为顶点v打上访问标记
    printf("%d ", v);                       //访问顶点v
    EnQueue(&q, v);                         //将顶点v放入队列
    while (!IsEmpty(&q)) {
        Front(&q, &v);
        DeQueue(&q);                       //队首顶点出队列
        for (w = g.a[v]; w; w = w->nextArc) {  //遍历v的所有邻接点
            if (!visited[w->adjVex]) {       //若w未被访问,则将其访问并放入队列
                visited[w->adjVex] = 1;
                printf("%d ", w->adjVex);
                EnQueue(&q, w->adjVex);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

d、邻接表的全图BFS

//邻接表的全图BFS
void BFSGraph(LGraph g) {
    int i;
    int* visited = (int*)malloc(g.n * sizeof(int));  //动态生成visited数组
    for (i = 0; i < g.n; i++) {                         //初始化visited数组
        visited[i] = 0;
    }
    for (i = 0; i < g.n; i++) {                        //逐一检查每个顶点,若未被访问,则调用BFS
        if (!visited[i]) {
            BFS(i, visited, g);
        }
    }
    free(visited);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

测试数据：
在这里插入图片描述

实验二、飞机最少换乘次数问题

1、以邻接矩阵存储有向图

{
int i, j, a, b, ans;

// s[50][50] 全部以0初始化，获取城市数量
    memset(s, 0, sizeof(s));
    printf("请输入城市数量\n");
    scanf_s("%d", &n);
    
    // 遍历邻接矩阵
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (i == j)
                s[i][j] = 0;
            else
                s[i][j] = 99999;

    printf("请输入公交线路数量\n");
    scanf_s("%d", &m);

    // 如果可达，则边的权值设为1
    for (i = 0; i < m; i++)
    {
        printf("请输入可达的两个站台\n");
        scanf_s("%d%d", &a, &b);
        s[a][b] = 1;
	}

    // 获取起点和终点，用Dijkstra算法计算中转次数
    printf("请输入起点和终点\n");
	scanf_s("%d%d", &a, &b);
	ans = Dijkstra(a, b);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

2、Dijkstra算法分析

  /// <summary>
/// Dijkstra算法
/// </summary>
/// <param name="start">起点</param>
/// <param name="end">终点</param>
/// <returns>中转次数</returns>
int Dijkstra(int start, int end)
{
    int i = 0, j = 0, k = 0;
    int min;
    int distance[100];
    int visited[100];
    memset(distance, 0, sizeof(distance));
    memset(visited, 0, sizeof(visited));

    // distance[i] 表示start节点到第i个节点的距离(如果等于1，则表示可达；如果等于9999，则表示不可达)
    for (i = 0; i < n; i++)
        distance[i] = s[start][i];

    for (i = 1; i <= n - 1; i++)
    {
        min = 99999;
        for (j = 0; j < n; j++) {
            if (distance[j] < min && !visited[j])
            {
                k = j;
                min = distance[j];
            }
        }
        visited[k] = 1;
        for (j = 0; j < n; j++)
            // 找到一条更短的
            if (distance[j] > distance[k] + s[k][j])
                distance[j] = distance[k] + s[k][j];
    }
    // 中转的站台数 = 经过的站台数 - 1
    return distance[end] - 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

算法分析：从起点开始查找，如果找到短的路径则替换，否则一直找到终点为止。其换乘次数等于经过的站台数量-1。
测试数据：
在这里插入图片描述

全部代码

1、邻接表

#include<stdio.h>
#include<stdlib.h>
#include <windows.h>
#define ERROR 0
#define OK 1
#define Overflow 2     //表示上溢
#define Underflow 3    //表示下溢
#define NotPresent 4   //表示元素不存在
#define Duplicate 5    //表示有重复元素
typedef int ElemType;
typedef int Status;


//邻接表的结构体定义
typedef struct ENode {
    int adjVex;             //任意顶点u相邻的顶点
    ElemType w;             //边的权值
    struct ENode* nextArc;  //指向下一个边结点
}ENode;

typedef struct {
    int n;             //图的当前顶点数
    int e;             //图的当前边数
    ENode** a;         //指向一维指针数组
}LGraph;


//邻接表的初始化
Status Init(LGraph* lg, int nSize) {
    int  i;
    lg->n = nSize;
    lg->e = 0;
    lg->a = (ENode**)malloc(nSize * sizeof(ENode*));  //动态生成长度为n的一维指针数组
    if (!lg->a) return ERROR;
    else {
        for (i = 0; i < lg->n; i++) {
            lg->a[i] = NULL;                        //将指针数组a置空
        }
        return OK;
    }
}


//邻接表的撤销(改成了int型，有返回值)
int Destory(LGraph* lg) {
    int i;
    ENode* p, * q;
    for (i = 0; i < lg->n; i++) {
        p = lg->a[i];                 //指针p指向顶点i的单链表的第一个边结点
        q = p;
        while (p) {                     //释放顶点i的单链表中所有边结点
            p = p->nextArc;
            free(q);
            q = p;
        }
    }
    free(lg->a);                     //释放一维指针数组a的存储空间
    return 1;                        //改为int型函数,有返回值
}


//邻接表的搜索边
Status Exist(LGraph* lg, int u, int v) {
    ENode* p;
    if (u < 0 || v < 0 || u > lg->n - 1 || v > lg->n - 1 || u == v) return ERROR;
    p = lg->a[u];                   //指针p指向顶点u的单链表的第一个边结点
    while (p != NULL && p->adjVex != v) {
        p = p->nextArc;
    }
    if (!p) return ERROR;            //若未找到此边,则返回ERROR
    else return OK;
}


//邻接表的插入边
Status Insert(LGraph* lg, int u, int v, ElemType w) {
    ENode* p;
    if (u < 0 || v < 0 || u > lg->n - 1 || v > lg->n - 1 || u == v) return ERROR;
    if (Exist(lg, u, v)) return Duplicate;  //此边已存在,返回错误
    p = (ENode*)malloc(sizeof(ENode));   //为新的边结点分配存储空间
    p->adjVex = v;
    p->w = w;
    p->nextArc = lg->a[u];             //将新的边结点插入单链表的最前面
    lg->a[u] = p;
    lg->e++;                            //边加1
    return OK;
}


//邻接表的删除边
Status Remove(LGraph* lg, int u, int v) {
    ENode* p, * q;
    if (u < 0 || v < 0 || u > lg->n - 1 || v > lg->n - 1 || u == v) return ERROR;
    p = lg->a[u];
    q = NULL;
    while (p && p->adjVex != v) {         //查找待删除边是否存在
        q = p;
        p = p->nextArc;
    }
    if (!p) return NotPresent;          //p为空,待删除边不存在
    if (q) q->nextArc = p->nextArc;     //从单链表删除此边
    else lg->a[u] = p->nextArc;
    free(p);
    lg->e--;
    return OK;
}



int main() {
    LGraph g;
    int i, u, v, enode, edge;
    ElemType w;
    printf("Please enter the number of the ENodes:");
    scanf_s("%d", &enode);
    Init(&g, enode);
    printf("Please enter the number of the edges:");
    scanf_s("%d", &edge);
    printf("Now init the graph.\n");
    for (i = 0; i < edge; i++) {
        printf("Please enter the edge:");
        scanf_s("%d%d%d", &u, &v, &w);
        Insert(&g, u, v, w);
    }
    //delete one edge
    printf("Please enter the deleted edge:");
    printf("\nPlease enter the u of the edge:");
    scanf_s("%d", &u);
    printf("Please enter the v of the edge:");
    scanf_s("%d", &v);
    printf("Now search the edge:");
    if (Exist(&g, u, v)) printf("OK");
    else printf("ERROR");
    printf("\nNow delete the edge:");
    //search the deleted edge
    if (Remove(&g, u, v)) printf("OK");
    else printf("ERROR");
    //destory
    printf("\nNow destory the graph:");
    if (Destory(&g)) printf("OK");
    else printf("ERROR");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

2、邻接表遍历

#include<stdio.h>
#include<stdlib.h>
#include <windows.h>
#define ERROR 0
#define OK 1
#define Overflow 2      //表示上溢
#define Underflow 3     //表示下溢
#define NotPresent 4    //表示元素不存在
#define Duplicate 5     //表示有重复元素
typedef int ElemType;
typedef int Status;


//邻接表的结构体定义
typedef struct ENode {
    int adjVex;              //任意顶点u相邻的顶点
    ElemType w;              //边的权值
    struct ENode* nextArc;   //指向下一个边结点
}ENode;

typedef struct {
    int n;           //图的当前顶点数
    int e;           //图的当前边数
    ENode** a;       //指向一维指针数组
}LGraph;


//循环队列的结构体定义
typedef struct {
    int front;
    int rear;
    int maxSize;    //最大容量
    ElemType* element;
}Queue;


//创建一个能容纳mSize个单元的空队列
void Create(Queue* Q, int mSize) {
    Q->maxSize = mSize;
    Q->element = (ElemType*)malloc(sizeof(ElemType) * mSize);
    Q->front = Q->rear = 0;
}


//判断队列是否为空,若是,则返回TRUE;否则返回FALSE
BOOL IsEmpty(Queue* Q) {
    return Q->front == Q->rear;
}


//判断队列是否已满,若是,则返回TRUE,否则返回FALSE
BOOL IsFULL(Queue* Q) {
    return (Q->rear + 1) % Q->maxSize == Q->front;
}


//获取队头元素,并通过x返回.若操作成功,则返回TRUE,否则返回FALSE
BOOL Front(Queue* Q, ElemType* x) {
    if (IsEmpty(Q))      //空队列处理
        return FALSE;
    *x = Q->element[(Q->front + 1) % Q->maxSize];
    return TRUE;
}


//入队.在队列Q的队尾插入元素x(入队操作)。操作成功,则返回TRUE,否则返回FALSE
BOOL EnQueue(Queue* Q, ElemType x) {
    if (IsFULL(Q))      //溢出处理
        return FALSE;
    Q->rear = (Q->rear + 1) % Q->maxSize;
    Q->element[Q->rear] = x;
    return TRUE;
}


//出队.从队列Q中删除队头元素(出队操作)。操作成功,则返回TRUE,否则返回FALSE
BOOL DeQueue(Queue* Q) {
    if (IsEmpty(Q)) {   //空队列处理
        return FALSE;
    }
    Q->front = (Q->front + 1) % Q->maxSize;
    return TRUE;
}


//邻接表的初始化
Status Init(LGraph* lg, int nSize) {
    int  i;
    lg->n = nSize;
    lg->e = 0;
    lg->a = (ENode**)malloc(nSize * sizeof(ENode*)); //动态生成长度为n的一维指针数组
    if (!lg->a) return ERROR;
    else {
        for (i = 0; i < lg->n; i++) {
            lg->a[i] = NULL;                       //将指针数组a置空
        }
        return OK;
    }
}


//邻接表的搜索边
Status Exist(LGraph* lg, int u, int v) {
    ENode* p;
    if (u < 0 || v < 0 || u > lg->n - 1 || v > lg->n - 1 || u == v) return ERROR;
    p = lg->a[u];                 //指针p指向顶点u的单链表的第一个边结点
    while (p && p->adjVex != v) {
        p = p->nextArc;
    }
    if (!p) return ERROR;          //若未找到此边,则返回ERROR
    else return OK;
}


//邻接表的插入边
Status Insert(LGraph* lg, int u, int v, ElemType w) {
    ENode* p;
    if (u < 0 || v < 0 || u > lg->n - 1 || v > lg->n - 1 || u == v) return ERROR;
    if (Exist(lg, u, v)) return Duplicate;       //此边已存在,返回错误
    p = (ENode*)malloc(sizeof(ENode));        //为新的边结点分配存储空间
    p->adjVex = v;
    p->w = w;
    p->nextArc = lg->a[u];                  //将新的边结点插入单链表的最前面
    lg->a[u] = p;
    lg->e++;                                 //边加1
    return OK;
}


//邻接表的单一顶点DFS
void DFS(int v, int visited[], LGraph g) {
    ENode* w;
    printf("%d ", v);                           //访问顶点v
    visited[v] = 1;                            //为顶点v打上访问标记
    for (w = g.a[v]; w; w = w->nextArc) {          //遍历v的邻接点
        if (!visited[w->adjVex]) {
            DFS(w->adjVex, visited, g);          //若w未被访问,则递归调用DFS
        }
    }
}


//邻接表的全图DFS
void DFSGraph(LGraph g) {
    int i;
    int* visited = (int*)malloc(g.n * sizeof(int)); //动态生成标记数组visted
    for (i = 0; i < g.n; i++) {
        visited[i] = 0;                             //visted数组初始化
    }
    for (i = 0; i < g.n; i++) {                        //逐一检查每个顶点,若未被访问,则调用DFS
        if (!visited[i]) {
            DFS(i, visited, g);
        }
    }
    free(visited);                                 //释放visted数组
}


//邻接表的单一顶点BFS
void BFS(int v, int visited[], LGraph g) {
    ENode* w;
    Queue q;
    Create(&q, g.n);                        //初始化队列
    visited[v] = 1;                        //为顶点v打上访问标记
    printf("%d ", v);                       //访问顶点v
    EnQueue(&q, v);                         //将顶点v放入队列
    while (!IsEmpty(&q)) {
        Front(&q, &v);
        DeQueue(&q);                       //队首顶点出队列
        for (w = g.a[v]; w; w = w->nextArc) {  //遍历v的所有邻接点
            if (!visited[w->adjVex]) {       //若w未被访问,则将其访问并放入队列
                visited[w->adjVex] = 1;
                printf("%d ", w->adjVex);
                EnQueue(&q, w->adjVex);
            }
        }
    }
}


//邻接表的全图BFS
void BFSGraph(LGraph g) {
    int i;
    int* visited = (int*)malloc(g.n * sizeof(int));  //动态生成visited数组
    for (i = 0; i < g.n; i++) {                         //初始化visited数组
        visited[i] = 0;
    }
    for (i = 0; i < g.n; i++) {                        //逐一检查每个顶点,若未被访问,则调用BFS
        if (!visited[i]) {
            BFS(i, visited, g);
        }
    }
    free(visited);
}



int main() {
    LGraph g;
    int i, u, v, enode, edge;
    ElemType w;
    printf("Please enter the number of the ENodes:");
    scanf_s("%d", &enode);
    Init(&g, enode);
    printf("Please enter the number of the edges:");
    scanf_s("%d", &edge);
    printf("Now init the graph.\n");
    for (i = 0; i < edge; i++) {
        printf("Please enter the edge:");
        scanf_s("%d%d%d", &u, &v, &w);
        Insert(&g, u, v, w);
    }
    printf("DFS:\n");
    DFSGraph(g);
    printf("\nBFS:\n");
    BFSGraph(g);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218

3、邻接矩阵

#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
#define Overflow 2    //表示上溢
#define Underflow 3   //表示下溢
#define NotPresent 4  //表示元素不存在
#define Duplicate 5   //表示有重复元素
typedef int ElemType;
typedef int Status;

//邻接矩阵的结构体定义
typedef struct {
    ElemType** a;     //邻接矩阵
    int n;            //图的当前顶点数
    int e;            //图的当前边数
    ElemType noEdge;  //两顶点间无边时的值
}mGraph;


//邻接矩阵的初始化
Status Init(mGraph* mg, int nSize, ElemType noEdgeValue) {
    int i, j;
    mg->n = nSize;               //初始化顶点数
    mg->e = 0;                   //初始化时没有边
    mg->noEdge = noEdgeValue;    //初始化没有边时的取值
    mg->a = (ElemType**)malloc(nSize * sizeof(ElemType*));  //生成长度为n的一维指针数组
    if (!mg->a) return ERROR;
    for (i = 0; i < mg->n; i++) {   //动态生成二维数组
        mg->a[i] = (ElemType*)malloc(nSize * sizeof(ElemType));
        for (j = 0; j < mg->n; j++) {
            mg->a[i][j] = mg->noEdge;  //初始化时权重都设为-1
        }
        mg->a[i][i] = 0;        //自回路设置为0
    }
    return OK;
}


//邻接矩阵的撤销(改成了int型，有返回值),先释放一维数组,再释放指针数组
int Destory(mGraph* mg) {
    int i;
    for (i = 0; i < mg->n; i++) {
        free(mg->a[i]);  //释放n个一维数组的存储空间
    }
    free(mg->a);         //释放一维数组的存储空间
    return 1;
}


//邻接矩阵的边的搜索
Status Exist(mGraph* mg, int u, int v) {
    if (u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v || mg->a[u][v] == mg->noEdge) return ERROR;
    return OK;
}


//邻接矩阵的边的插入
Status Insert(mGraph* mg, int u, int v, ElemType w) {
    if (u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v) return ERROR;
    if (mg->a[u][v] != mg->noEdge) return Duplicate;  //若待插入边已存在,则返回出错信息
    mg->a[u][v] = w;                                 //插入新边
    mg->e++;                                        //增加一条边
    return OK;
}


//邻接矩阵的边的删除
Status Remove(mGraph* mg, int u, int v) {
    if (u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v) return ERROR;
    if (mg->a[u][v] == mg->noEdge) return NotPresent;  //若待删除边不存在,则返回出错信息
    mg->a[u][v] = mg->noEdge;                         //删除边
    mg->e--;
    return OK;
}



int main() {
    mGraph g;
    int nSize, edge, u, v, i, j;
    ElemType w;
    printf("请输入图的节点个数:");
    scanf_s("%d", &nSize);
    Init(&g, nSize, -1);
    printf("请输入边的个数:");
    scanf_s("%d", &edge);
    printf("Now init the graph.\n");
    for (i = 0; i < edge; i++) {
        printf(":");
        scanf_s("%d%d%d", &u, &v, &w);
        Insert(&g, u, v, w);
    }
    //delete one edge
    printf("Please enter the deleted edge:");
    printf("\nPlease enter the u of the edge:");
    scanf_s("%d", &u);
    printf("Please enter the v of the edge:");
    scanf_s("%d", &v);
    printf("Now search the edge:");
    if (Exist(&g, u, v)) printf("OK");
    else printf("ERROR");
    printf("\nNow delete the edge:");
    //search the deleted edge
    if (Remove(&g, u, v)) printf("OK");
    else printf("ERROR");
    //destory
    printf("\nNow destory the graph:");
    if (Destory(&g)) printf("OK");
    else printf("ERROR");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

4、邻接矩阵遍历

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<windows.h>
#include<queue>
#define ERROR 0
#define OK 1
#define Overflow 2  //表示上溢
#define Underflow 3  //表示下溢
#define NotPresent 4 //表示元素不存在
#define Duplicate 5  //表示有重复元素
typedef int ElemType;
typedef int Status;

//邻接矩阵的结构体定义
typedef struct {
    ElemType** a;     //邻接矩阵
    int n;            //图的当前顶点数
    int e;            //图的当前边数
    ElemType noEdge;  //两顶点间无边时的值
}mGraph;


//循环队列的结构体定义
typedef struct {
    int front;
    int rear;
    int maxSize;    //最大容量
    ElemType* element;
}Queue;


//创建一个能容纳mSize个单元的空队列
void Create(Queue* Q, int mSize) {
    Q->maxSize = mSize;
    Q->element = (ElemType*)malloc(sizeof(ElemType) * mSize);
    Q->front = Q->rear = 0;
}


//判断队列是否为空,若是,则返回TRUE;否则返回FALSE
BOOL IsEmpty(Queue* Q) {
    return Q->front == Q->rear;
}


//判断队列是否已满,若是,则返回TRUE,否则返回FALSE
BOOL IsFULL(Queue* Q) {
    return (Q->rear + 1) % Q->maxSize == Q->front;
}


//获取队头元素,并通过x返回.若操作成功,则返回TRUE,否则返回FALSE
BOOL Front(Queue* Q, ElemType* x) {
    if (IsEmpty(Q))      //空队列处理
        return FALSE;
    *x = Q->element[(Q->front + 1) % Q->maxSize];
    return TRUE;
}


//入队.在队列Q的队尾插入元素x(入队操作)。操作成功,则返回TRUE,否则返回FALSE
BOOL EnQueue(Queue* Q, ElemType x) {
    if (IsFULL(Q))      //溢出处理
        return FALSE;
    Q->rear = (Q->rear + 1) % Q->maxSize;
    Q->element[Q->rear] = x;
    return TRUE;
}


//出队.从队列Q中删除队头元素(出队操作)。操作成功,则返回TRUE,否则返回FALSE
BOOL DeQueue(Queue* Q) {
    if (IsEmpty(Q)) {   //空队列处理
        return FALSE;
    }
    Q->front = (Q->front + 1) % Q->maxSize;
    return TRUE;
}


//邻接矩阵的初始化
Status Init(mGraph* mg, int nSize, ElemType noEdgeValue) {
    int i, j;
    mg->n = nSize;               //初始化顶点数
    mg->e = 0;                   //初始化时没有边
    mg->noEdge = noEdgeValue;    //初始化没有边时的取值
    mg->a = (ElemType**)malloc(nSize * sizeof(ElemType*));  //生成长度为n的一维指针数组
    if (!mg->a) return ERROR;
    for (i = 0; i < mg->n; i++) {   //动态生成二维数组
        mg->a[i] = (ElemType*)malloc(nSize * sizeof(ElemType));
        for (j = 0; j < mg->n; j++) {
            mg->a[i][j] = mg->noEdge;
        }
        mg->a[i][i] = 0;        //自回路设置为0
    }
    return OK;
}


//邻接矩阵的撤销(改成了int型，有返回值),先释放一维数组,再释放指针数组
int Destory(mGraph* mg) {
    int i;
    for (i = 0; i < mg->n; i++) {
        free(mg->a[i]);  //释放n个一维数组的存储空间
    }
    free(mg->a);         //释放一维数组的存储空间
    return 1;
}


//邻接矩阵的边的搜索
Status Exist(mGraph* mg, int u, int v) {
    if (u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v || mg->a[u][v] == mg->noEdge) return ERROR;
    return OK;
}


//邻接矩阵的边的插入
Status Insert(mGraph* mg, int u, int v, ElemType w) {
    if (u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v) return ERROR;
    if (mg->a[u][v] != mg->noEdge) return Duplicate;  //若待插入边已存在,则返回出错信息
    mg->a[u][v] = w;                                 //插入新边
    mg->e++;                                        //增加一条边
    return OK;
}


//邻接矩阵的边的删除
Status Remove(mGraph* mg, int u, int v) {
    if (u < 0 || v < 0 || u > mg->n - 1 || v > mg->n - 1 || u == v) return ERROR;
    if (mg->a[u][v] == mg->noEdge) return NotPresent;  //若待删除边不存在,则返回出错信息
    mg->a[u][v] = mg->noEdge;                         //删除边
    mg->e--;
    return OK;
}


//邻接矩阵的单一顶点DFS
void DFS(int v, int visited[], mGraph g) {
    int j;
    printf("%d ", v);              //访问顶点v
    visited[v] = 1;               //为顶点v打上访问标记       
    for (j = 0; j < g.n; j++) {      //遍历v的邻接点
        if (!visited[j] && g.a[v][j] > 0) {  //当未被访问且有权值
            DFS(j, visited, g);
        }
    }
}


//邻接矩阵的全图DFS
void DFSGraph(mGraph g) {
    int i;
    int* visited = (int*)malloc(g.n * sizeof(int)); //动态生成标记数组visted
    for (i = 0; i < g.n; i++) {
        visited[i] = 0;          //visted数组初始化
    }                            //visted数组初始化
    for (i = 0; i < g.n; i++) {     //逐一检查每个顶点,若未被访问,则调用DFS
        if (!visited[i]) {   //当未被访问且有权值
            DFS(i, visited, g);
        }
    }
    free(visited);                       //释放visted数组
}


//邻接矩阵的单一顶点BFS
void BFS(int v, int visited[], mGraph g) {
    Queue q;
    Create(&q, g.n);                        //初始化队列
    visited[v] = 1;                        //为顶点v打上访问标记
    printf("%d ", v);                       //访问顶点v
    EnQueue(&q, v);                         //将顶点v放入队列
    while (!IsEmpty(&q)) {
        Front(&q, &v);
        DeQueue(&q);                       //队首顶点出队列
        for (int i = 0; i < g.n; i++) {       //遍历v的每一项
            if (!visited[i] && g.a[v][i] > 0) {       //若未被访问且有权值,则将其访问并放入队列,注意这里判断的是g.a[v][i]二维数组
                visited[i] = 1;
                printf("%d ", i);
                EnQueue(&q, i);
            }
        }
    }
}


//邻接矩阵的全图BFS
void BFSGraph(mGraph g) {
    int i;
    int* visited = (int*)malloc(g.n * sizeof(int));  //动态生成visited数组
    for (i = 0; i < g.n; i++) {                         //初始化visited数组
        visited[i] = 0;
    }
    for (i = 0; i < g.n; i++) {                        //逐一检查每个顶点,若未被访问,则调用BFS
        if (!visited[i]) {
            BFS(i, visited, g);
        }
    }
    free(visited);
}



int main() {
    mGraph g;
    int nSize, edge, u, v, i;
    ElemType w;
    printf("Please enter the size of the mgraph:");
    scanf_s("%d", &nSize);
    Init(&g, nSize, -1);
    printf("Please enter the number of the edges:");
    scanf_s("%d", &edge);
    printf("Now init the graph.\n");
    /*
    for(i = 0;i < nSize;i ++){
        for(j = 0;j < nSize;j ++){
            printf("Please enter the edge:");
            scanf_s("%d%d%d",&u,&v,&w);
            Insert(&g,u,v,w);
        }
    }
    */
    for (i = 0; i < edge; i++) {
        printf("Please enter the edge:");
        scanf_s("%d%d%d", &u, &v, &w);
        Insert(&g, u, v, w);
    }
    printf("DFS:\n");
    DFSGraph(g);
    printf("\nBFS:\n");
    BFSGraph(g);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235

5、中转

#include <stdio.h>
#include <string.h>
int n, m;
int s[50][50];

 // 有向图

/// <summary>
/// Dijkstra算法
/// </summary>
/// <param name="start">起点</param>
/// <param name="end">终点</param>
/// <returns>中转次数</returns>
int Dijkstra(int start, int end)
{
    int i = 0, j = 0, k = 0;
    int min;
    int distance[100];
    int visited[100];
    memset(distance, 0, sizeof(distance));
    memset(visited, 0, sizeof(visited));

    // distance[i] 表示start节点到第i个节点的距离(如果等于1，则表示可达；如果等于9999，则表示不可达)
    for (i = 0; i < n; i++)
        distance[i] = s[start][i];

    for (i = 1; i <= n - 1; i++)
    {
        min = 99999;
        for (j = 0; j < n; j++) {
            if (distance[j] < min && !visited[j])
            {
                k = j;
                min = distance[j];
            }
        }
        visited[k] = 1;
        for (j = 0; j < n; j++)
            // 找到一条更短的
            if (distance[j] > distance[k] + s[k][j])
                distance[j] = distance[k] + s[k][j];
    }
    // 中转的站台数 = 经过的站台数 - 1
    return distance[end] - 1;
}
int main()
{
    int i, j, a, b, ans;
    memset(s, 0, sizeof(s));
    printf("请输入城市数量\n");
    scanf_s("%d", &n);
    
    // 遍历邻接矩阵
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (i == j)
                s[i][j] = 0;
            else
                s[i][j] = 99999;

    printf("请输入公交线路数量\n");
    scanf_s("%d", &m);

    for (i = 0; i < m; i++)
    {
        printf("请输入可达的两个站台\n");
        scanf_s("%d%d", &a, &b);
        s[a][b] = 1;
    }

    printf("请输入起点和终点\n");
    scanf_s("%d%d", &a, &b);

    ans = Dijkstra(a, b);

    if (ans == 99998)
        printf("无法到达\n");
    else if (ans > 0)
        printf("最少换乘次数为%d\n", ans);
    else if(ans == 0)
        printf("不需要换乘\n");
    return 0;
}


//#include<stdio.h>
//#include<stdlib.h>
//#include <windows.h>
//#define ERROR 0
//#define OK 1
//#define Overflow 2     //表示上溢
//#define Underflow 3    //表示下溢
//#define NotPresent 4   //表示元素不存在
//#define Duplicate 5    //表示有重复元素
//#define INFTY 32767    //表示极大值正无穷
//typedef int ElemType;
//typedef int Status;
//
//
邻接矩阵的结构体定义
//typedef struct {
//    ElemType** a;     //邻接矩阵
//    int size_vertex;            //顶点数
//    int size_edge;            //边数
//    ElemType noEdge;  //两顶点间无边时的值
//}mGraph;
//
//
邻接矩阵的初始化
//Status Init(mGraph* mg, int nSize, ElemType noEdgeValue) {
//    int i, j;
//    mg->size_vertex = nSize;               //初始化顶点数
//    mg->size_edge = 0;                   //初始化时没有边
//    mg->noEdge = noEdgeValue;    //初始化没有边时的取值
//    mg->a = (ElemType**)malloc(nSize * sizeof(ElemType*));  //生成长度为size_vertex的一维指针数组
//    if (!mg->a) return ERROR;
//    for (i = 0; i < mg->size_vertex; i++) {   //动态生成二维数组
//        mg->a[i] = (ElemType*)malloc(nSize * sizeof(ElemType));
//        for (j = 0; j < mg->size_vertex; j++) {
//            mg->a[i][j] = mg->noEdge;  //初始化时权重都设为-1
//        }
//        mg->a[i][i] = 0;        //自回路设置为0
//    }
//    return OK;
//}
//
//
邻接矩阵的撤销(改成了int型，有返回值),先释放一维数组,再释放指针数组
//int Destory(mGraph* mg) {
//    int i;
//    for (i = 0; i < mg->size_vertex; i++) {
//        free(mg->a[i]);  //释放size_vertex个一维数组的存储空间
//    }
//    free(mg->a);         //释放一维数组的存储空间
//    return 1;
//}
//
//
邻接矩阵的边的搜索
//Status Exist(mGraph* mg, int u, int v) {
//    if (u < 0 || v < 0 || u > mg->size_vertex - 1 || v > mg->size_vertex - 1 || u == v || mg->a[u][v] == mg->noEdge) return ERROR;
//    return OK;
//}
//
//
/ <summary>
/ 邻接矩阵的边的插入
/ </summary>
/ <param name="mg">邻接矩阵对象</param>
/ <param name="v1">顶点1</param>
/ <param name="v2">顶点2</param>
/ <param name="weight">权值</param>
/ <returns></returns>
//Status Insert(mGraph* mg, int v1, int v2) {
//    if (v1 < 0 || v2 < 0 || v1 > mg->size_vertex - 1 || v2 > mg->size_vertex - 1 || v1 == v2) return ERROR;
//    if (mg->a[v1][v2] != mg->noEdge) return Duplicate;  //若待插入边已存在,则返回出错信息
//    mg->a[v1][v2] = 1;                                 //插入新边
//    mg->size_edge++;                                        //增加一条边
//    return OK;
//}
//
//
邻接矩阵的边的删除
//Status Remove(mGraph* mg, int v1, int v2) {
//    if (v1 < 0 || v2 < 0 || v1 > mg->size_vertex - 1 || v2 > mg->size_vertex - 1 || v1 == v2) return ERROR;
//    if (mg->a[v1][v2] == mg->noEdge) return NotPresent;  //若待删除边不存在,则返回出错信息
//    mg->a[v1][v2] = mg->noEdge;                         //删除边
//    mg->size_edge--;
//    return OK;
//}
//
//

//
/ <summary>
/ 选出最小的distance[i],i ∈ V-S (全部顶点的集合 - 已选顶点的集合)
/ </summary>
/ <param name="d">distance数组</param>
/ <param name="size_vertex">图的顶点个数</param>
/ <param name="s">已选顶点的集合</param>
/ <returns>返回最小 distance[i] 的索引</returns>
//int Choose(int d[], int size_vertex, int s[]) { 
//    int i, minpos;
//    ElemType min;
//    min = INFTY;
//    minpos = -1;
//
//    // 遍历 distance[] 数组
//    for (i = 0; i < size_vertex; i++) {       
//        // 如果distance[i] 较小 && i 在未插入的集合中
//        if (d[i] <= min && !s[i]) {  //<改为<=
//            min = d[i];
//            minpos = i;
//        }
//    }
//    return minpos;                //返回下标位置
//}
//
/ <summary>
/ Dijkstra(迪杰斯特拉)算法
/ </summary>
/ <param name="g">邻接矩阵对象</param>
/ <param name="v0">源顶点(传入的参数为0)</param>
/ <param name="d">distance数组</param>
/ <param name="path">路径顺序数组</param>
/ <returns></returns>
//Status Dijkstra(mGraph g, int v0, int distance[], int path[]) { 
//    int vi, k, w, min_distance = 0;       //增加了一个distance记录最短距离之和
//
//    if (v0 < 0 || v0 > g.size_vertex - 1) {
//        return ERROR;
//    }
//
//    // int[] s; s表示已经排好的的顶点的集合S
//    int* s = (int*)malloc(g.size_vertex * sizeof(int));
//
//    // 初始化; 将s[i] = 0, 即表示S集合为空
//    for (vi = 0; vi < g.size_vertex; vi++) {      
//        s[vi] = 0;                 //表示顶点vi是否在s中
//        distance[vi] = g.a[v0][vi];         // distance[vi] = v0到vi边的权值
//        if (vi != v0 && distance[vi] < INFTY) {
//            path[vi] = v0;          //标识指向vi的源点v0
//        }
//        else path[vi] = -1;
//    }
//
//    // 顶点 v0 为源点,将源点 v0 加入集合 S
//    s[v0] = 1;     
//
//    //输出源点 v0
//    printf("路径为: %d ", v0);               
//    distance[v0] = 0;
//
//    //产生size_vertex-1条最短路径
//    for (vi = 1; vi < g.size_vertex; vi++) {   
//        k = Choose(distance, g.size_vertex, s);            //求当前路径最短者k
//        s[k] = 1;                                   //将k加入集合S中
//        printf("%d ", k);
//        for (w = 0; w < g.size_vertex; w++) {       //更新distance和path
//
//
//            if (!s[w] && distance[k] + g.a[k][w] < distance[w]) {
//                distance[w] = distance[k] + g.a[k][w];
//                min_distance = distance[w];  //计算min距离
//                path[w] = k;
//            }
//        }
//    }
//    printf("\n最短的距离为:%d\n", min_distance);
//    return OK;
//}
//
//
//
//int main() {
//    mGraph g;
//    int size_vertex, size_edge, v1, v2, i;
//    int d[100];
//    int path[100];
//    printf("请输入节点个数:");
//    scanf_s("%d", &size_vertex);
//    Init(&g, size_vertex, INFTY);
//    printf("请输入边的个数:");
//    scanf_s("%d", &size_edge);
//    printf("请初始化图\n");
//    for (i = 0; i < size_edge; i++) {
//        printf("请输入边(格式为：顶点 顶点):");
//        scanf_s("%d%d", &v1, &v2);
//        Insert(&g, v1, v2);
//    }
//    Dijkstra(g, 0, d, path);
//    return 0;
//}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/173186