图编程整理

MG：邻接矩阵

ALG：邻接表

任务：

一、图的创建与转换

1.采用邻接矩阵表示法创建无向图（c）

  • 通过文件输入:
1
2
3
4
5
6
7
8
9
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE
  • 输出：
1
2
3
4
5
6
7
8
Create adjacency matrix from the read file
print adjacency matrix :
    A  B  C  D  E
A   0  1  0  1  0
B   1  0  1  0  1
C   0  1  0  1  1
D   1  0  1  0  1
E   0  1  1  1  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
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

#define MaxVertexNum 100

// 定义邻接矩阵结构
typedef struct{
    int vexNum, arcNum; // 顶点数和边数
    char vexs[MaxVertexNum]; // 存顶点
    int arcs[MaxVertexNum][MaxVertexNum]; // 将边
}MGraph;

// 查找顶点在数组中的索引
int locateVexIndex(MGraph G, char v) {
    for (int i = 0; i < G.vexNum; ++i) {
        if (G.vexs[i] == v) {
            return i;
        }
    }
    return -1;
}

// 创建邻接矩阵
void createUDN(MGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexNum >> G.arcNum; // 读取顶点数和边数
    // 读取顶点名称
    for (int i = 0; i < G.vexNum; i++) {
        infile >> G.vexs[i];
    }

    // 初始化邻接矩阵
    for (int i = 0; i < G.vexNum; i++) {
        for (int j = 0; j < G.vexNum; j++) {
            G.arcs[i][j] = 0;
        }
    }

    // 读取邻接关系（边）
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        // 找到顶点下标
        int i = locateVexIndex(G, v1);
        int j = locateVexIndex(G, v2);

        // 构建邻接关系
        if (i == -1 || j == -1) {
            continue;
        }
        // 无向图：边是双向的，矩阵对称
        G.arcs[i][j] = 1;
        G.arcs[j][i] = 1;
    }
}

// 输出邻接矩阵
void printMG(MGraph MG) {
    cout << "  "; // 第一行第一列留空（与左侧顶点列对齐）
    for (int j = 0; j < MG.vexNum; j++) {
        cout << setw(3) << MG.vexs[j]; // 输出顶点名称（如 'A'、'B'）
    }
    cout << endl; // 标题行结束换行

    for (int i = 0; i < MG.vexNum; i++) {
        cout << MG.vexs[i] << " "; // 输出左侧顶点名称
        for (int j = 0; j < MG.vexNum; j++) {
            cout << setw(3) << MG.arcs[i][j];
        }
        cout << endl;
    }
}

int main() {
    // 指定文件位置
    string filename = "graph_data.txt";

    MGraph MG;

    // 根据文件读取信息创建邻接矩阵
    cout << "Create adjacency matrix from the read file" << endl;
    createUDN(MG, filename);

    // 将邻接矩阵打印
    cout << "print adjacency matrix :" << endl;
    printMG(MG);
}

2.采用邻接表创建无向图

  • 通过文件输入:
1
2
3
4
5
6
7
8
9
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE
  • 输出：
1
2
3
4
5
6
Create adjacency list from the read file:
A: ->D ->B
B: ->E ->C ->A
C: ->E ->D ->B
D: ->E ->C ->A
E: ->D ->C ->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
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
#include <iostream>
#include <fstream>
using namespace std;

#define MaxVertexNum 100

// 定义边结点结构
typedef struct ArcNode {
    int adjvex; // 邻接点（存下标）
    struct ArcNode *nextarc;
    int info; // 边信息：存权值之类的
} ArcNode;

// 定义顶点结构
typedef struct VNode {
    char data;
    ArcNode *firstArc;
} VNode, AdjList[MaxVertexNum];

// 定义邻接表结构
typedef struct {
    VNode vertices[MaxVertexNum];
    int vexNum, arcNum;
} ALGraph;

// 定位下标
int LocateVexIndex(ALGraph G, char v) {
    for (int i = 0; i < G.vexNum; ++i) {
        if (v == G.vertices[i].data) {
            return i;
        }
    }
    return -1;
}

void createUDG(ALGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexNum >> G.arcNum;
    // 读取顶点信息
    for (int i = 0; i < G.vexNum; ++i) {
        infile >> G.vertices[i].data;
        G.vertices[i].firstArc = NULL;
    }
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        int i = LocateVexIndex(G, v1);
        int j = LocateVexIndex(G, v2);

        // 将邻接边头插入链表
        ArcNode *p1 = new ArcNode();
        p1->nextarc = G.vertices[i].firstArc;
        p1->adjvex = j;
        G.vertices[i].firstArc = p1;

        // 双向
        ArcNode *p2 = new ArcNode();
        p2->nextarc = G.vertices[j].firstArc;
        p2->adjvex = i;
        G.vertices[j].firstArc = p2;
    }
}

// 输出邻接表
void printALG(ALGraph ALG) {
    for (int i = 0; i < ALG.vexNum; ++i) {
        cout << ALG.vertices[i].data << ":";
        // 定义指针用于遍历邻接的点
        ArcNode *p = ALG.vertices[i].firstArc;
        while (p != NULL) {
            cout << " ->" << ALG.vertices[p->adjvex].data;
            p = p->nextarc;
        }
        cout << endl;
    }
}

int main() {
    // 指定文件读取名称
    string filename = "graph_data.txt";

    ALGraph ALG;

    // 创建邻接表
    cout << "Create adjacency list from the read file:" << endl;
    createUDG(ALG, filename);

    // 将读取的邻接表输出
    printALG(ALG);
}

3.邻接矩阵转邻接表

文件输入:

1
2
3
4
5
6
7
8
9
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Create adjacency Matrix from the read file
    A  B  C  D  E
A   0  1  0  1  0
B   1  0  1  0  1
C   0  1  0  1  1
D   1  0  1  0  1
E   0  1  1  1  0
Convert adjacency matrix to adjacency list
Conversion result:
A: ->D ->B
B: ->E ->C ->A
C: ->E ->D ->B
D: ->E ->C ->A
E: ->D ->C ->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
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
#include <iostream>
#include <fstream>
#include <iomanip>

#define MaxVexNum 100
using namespace std;

// 定义邻接矩阵结构
typedef struct MGraph{
    int vexnum, arcnum;
    char vexs[MaxVexNum];
    int arcs[MaxVexNum][MaxVexNum];
}MGraph;

// 定义邻接点结构
typedef struct ArcNode {
    int adjVex; // 存放邻接点下标
    struct ArcNode *nextArc;
}ArcNode;

// 定义顶点结构
typedef struct VNode {
    char data;
    ArcNode *firstArc;
}VNode;

// 定义邻接表结构
typedef struct{
    VNode vertices[MaxVexNum];
    int vexnum, arcnum;
}ALGraph;

// 根据控制台输入创建邻接矩阵
void createM(MGraph &G, const string &filename) {
    ifstream infile(filename);
    // 读取顶点和边的数量
    infile >> G.vexnum >> G.arcnum;
    // 读取顶点名称
    for (int i = 0; i < G.vexnum; ++i) {
        infile >> G.vexs[i];
    }
    // 初始化邻接矩阵
    for (int i = 0; i < G.vexnum; ++i) {
        for (int j = 0; j < G.vexnum; ++j) {
            G.arcs[i][j] = 0;
        }
    }
    // 读取邻接边关系
    for (int k = 0; k < G.arcnum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;
        int a, b;
        for (int i = 0; i < G.vexnum; ++i) {
            if (G.vexs[i] == v1) {
                a = i;
            }
            if (G.vexs[i] == v2) {
                b = i;
            }
        }
        G.arcs[a][b] = 1;
        G.arcs[b][a] = 1;
    }
}

// 根据邻接矩阵转邻接表
void createALGByMG(MGraph &MG, ALGraph &ALG) {
    // 将顶点数和边数读取进邻接表
    ALG.vexnum = MG.vexnum;
    ALG.arcnum = MG.arcnum;
    // 将顶点名读取，并将指向先置空
    for (int i = 0; i < ALG.vexnum; ++i) {
        ALG.vertices[i].data = MG.vexs[i];
        ALG.vertices[i].firstArc = NULL;
    }
    // 读取邻接矩阵邻接关系创建邻接表
    for (int i = 0; i < MG.vexnum; ++i) {
        for (int j = 0; j < MG.vexnum; ++j) {
            if (MG.arcs[i][j] == 1) {
                ArcNode *newNode1 = new ArcNode;
                newNode1->adjVex = j;
                newNode1->nextArc = ALG.vertices[i].firstArc;
                ALG.vertices[i].firstArc = newNode1;
            }
        }
    }
}

// 输出邻接表
void printALG(ALGraph ALG) {
    for (int i = 0; i < ALG.vexnum; ++i) {
        cout << ALG.vertices[i].data << ":";
        // 定义指针用于遍历邻接的点
        ArcNode *p = ALG.vertices[i].firstArc;
        while (p != NULL) {
            cout << " ->" << ALG.vertices[p->adjVex].data;
            p = p->nextArc;
        }
        cout << endl;
    }
}

// 输出邻接矩阵
void printMG(MGraph MG) {
    cout << "  "; // 第一行第一列留空（与左侧顶点列对齐）
    for (int j = 0; j < MG.vexnum; j++) {
        cout << setw(3) << MG.vexs[j]; // 输出顶点名称（如 'A'、'B'）
    }
    cout << endl; // 标题行结束换行

    for (int i = 0; i < MG.vexnum; i++) {
        cout << MG.vexs[i] << " "; // 输出左侧顶点名称
        for (int j = 0; j < MG.vexnum; j++) {
            cout << setw(3) << MG.arcs[i][j];
        }
        cout << endl;
    }
}

int main() {
    // 指定读取文件位置
    string filename = "graph_data.txt";

    ALGraph ALG;
    MGraph MG;

    // 创建邻接矩阵
    createM(MG, filename);

    // 将读取的邻接矩阵输出
    cout << "Create adjacency Matrix from the read file" << endl;
    printMG(MG);

    // 邻接矩阵转邻接表
    cout << "Convert adjacency matrix to adjacency list" << endl;
    createALGByMG(MG, ALG);

    // 输出邻接表
    cout << "Conversion result:" << endl;
    printALG(ALG);
}

4.邻接表转邻接矩阵

创建邻接表→通过邻接表转邻接矩阵

从文件输入:

1
2
3
4
5
6
7
8
9
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE

输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Create adjacency list from the read file:
A: ->D ->B
B: ->E ->C ->A
C: ->E ->D ->B
D: ->E ->C ->A
E: ->D ->C ->B
Convert adjacency list to adjacency matrix,Conversion result
    A  B  C  D  E
A   0  1  0  1  0
B   1  0  1  0  1
C   0  1  0  1  1
D   1  0  1  0  1
E   0  1  1  1  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
#include <iostream>
#include <iomanip>
#include <fstream>

using namespace std;

#define MaxVexNum 100

// 定义邻接结构
typedef struct ArcNode {
    int adjVex; // 邻接点下标
    struct ArcNode *nextArc;
}ArcNode;

// 定义邻接表结点结构
typedef struct VNode {
    char data; // 顶点名称
    ArcNode *firstArc;
}VNode, AdjList[MaxVexNum];

// 定义邻接表结构
typedef struct {
    VNode vertices[MaxVexNum];
    int vexNum, arcNum;
}ALGraph;

// 根据输入的信息创建邻接表
void CreateUDG(ALGraph &G, const string &filename) {
    ifstream infile(filename);
    // 读取顶点数和边数
    infile >> G.vexNum >> G.arcNum;
    // 读取顶点名称
    for (int i = 0; i < G.vexNum; ++i) {
        infile >> G.vertices[i].data;
        G.vertices[i].firstArc = NULL;
    }

    // 读取邻接信息存入邻接表
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;
        int a, b; // 用于定位下标
        for (int i = 0; i < G.vexNum; ++i) {
            if (v1 == G.vertices[i].data) {
                a = i;
            }
            if (v2 == G.vertices[i].data) {
                b = i;
            }
        }
        // 建立v1到v2的边
        ArcNode *newNode1 = new ArcNode;
        newNode1->nextArc = G.vertices[a].firstArc;
        G.vertices[a].firstArc = newNode1;
        newNode1->adjVex = b;

        // 建立v2到v1的边
        ArcNode *newNode2 = new ArcNode;
        newNode2->nextArc = G.vertices[b].firstArc;
        G.vertices[b].firstArc = newNode2;
        newNode2->adjVex = a;
    }
}

// 定义邻接矩阵结构
typedef struct MGraph {
    int vexNum, arcNum;
    int arcs[MaxVexNum][MaxVexNum];
    char vexs[MaxVexNum];
}MGraph;

// 根据已经创建好的邻接表创建邻接矩阵
void CreateMGByALG(ALGraph ALG, MGraph &MG) {
    MG.vexNum = ALG.vexNum;
    MG.arcNum = ALG.arcNum;
    // 读取顶点名称
    for (int i = 0; i < MG.vexNum; ++i) {
        MG.vexs[i] = ALG.vertices[i].data;
    }
    // 初始化邻接矩阵
    for (int i = 0; i < MG.vexNum; ++i) {
        for (int j = 0; j < MG.vexNum; ++j) {
            MG.arcs[i][j] = 0;
        }
    }
    // 读取邻接表将邻接边输入至邻接矩阵
    for (int i = 0; i < ALG.vexNum; ++i) {
        ArcNode *p = ALG.vertices[i].firstArc;
        while (p != NULL) {
            MG.arcs[i][p->adjVex] = 1;
            MG.arcs[p->adjVex][i] = 1;
            p = p->nextArc;
        }
    }
}

// 输出邻接矩阵
void printMG(MGraph MG) {
    cout << "  "; // 第一行第一列留空（与左侧顶点列对齐）
    for (int j = 0; j < MG.vexNum; j++) {
        cout << setw(3) << MG.vexs[j]; // 输出顶点名称（如 'A'、'B'）
    }
    cout << endl; // 标题行结束换行

    for (int i = 0; i < MG.vexNum; i++) {
        cout << MG.vexs[i] << " "; // 输出左侧顶点名称
        for (int j = 0; j < MG.vexNum; j++) {
            cout << setw(3) << MG.arcs[i][j];
        }
        cout << endl;
    }
}

// 输出邻接表
void printALG(ALGraph ALG) {
    for (int i = 0; i < ALG.vexNum; ++i) {
        cout << ALG.vertices[i].data << ":";
        // 定义指针用于遍历邻接的点
        ArcNode *p = ALG.vertices[i].firstArc;
        while (p != NULL) {
            cout << " ->" << ALG.vertices[p->adjVex].data;
            p = p->nextArc;
        }
        cout << endl;
    }
}

int main () {
    // 指定文件名称
    string filename = "graph_data.txt";

    MGraph MG;
    ALGraph ALG;

    // 创建邻接表
    CreateUDG(ALG, filename);

    // 输出创建的邻接表
    cout << "Create adjacency list from the read file:" << endl;
    printALG(ALG);

    // 邻接表转邻接矩阵
    cout << "Convert adjacency list to adjacency matrix,Conversion result" << endl;
    CreateMGByALG(ALG, MG);

    // 输出邻接矩阵
    printMG(MG);
}

二、入度与出度计算

5.根据邻接矩阵求各顶点入度

  • 根据文件输入：
1
2
3
4
5
6
7
8
9
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE
  • 输出:
1
2
3
4
5
6
7
8
9
10
11
12
13
Create adjacency matrix from the read file:
    A  B  C  D  E
A   0  1  0  1  0
B   1  0  1  0  1
C   0  1  0  1  1
D   1  0  1  0  1
E   0  1  1  1  0
Calculate the in-degree of vertices using the adjacency matrix:
A's inDegree: 2
B's inDegree: 3
C's inDegree: 3
D's inDegree: 3
E's inDegree: 3
  • 代码：
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
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

#define MaxVertexNum 100

// 定义邻接矩阵结构
typedef struct{
    int vexNum, arcNum; // 顶点数和边数
    char vexs[MaxVertexNum]; // 存顶点
    int arcs[MaxVertexNum][MaxVertexNum]; // 将边
}MGraph;

// 查找顶点在数组中的索引
int locateVexIndex(MGraph G, char v) {
    for (int i = 0; i < G.vexNum; ++i) {
        if (G.vexs[i] == v) {
            return i;
        }
    }
    return -1;
}

// 创建邻接矩阵
void createUDN(MGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexNum >> G.arcNum; // 读取顶点数和边数
    // 读取顶点名称
    for (int i = 0; i < G.vexNum; i++) {
        infile >> G.vexs[i];
    }

    // 初始化邻接矩阵
    for (int i = 0; i < G.vexNum; i++) {
        for (int j = 0; j < G.vexNum; j++) {
            G.arcs[i][j] = 0;
        }
    }

    // 读取邻接关系（边）
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        // 找到顶点下标
        int i = locateVexIndex(G, v1);
        int j = locateVexIndex(G, v2);

        // 构建邻接关系
        if (i == -1 || j == -1) {
            continue;
        }
        // 无向图：边是双向的，矩阵对称
        G.arcs[i][j] = 1;
        G.arcs[j][i] = 1;
    }
}

// 输出邻接矩阵
void printMG(MGraph MG) {
    cout << "  "; // 第一行第一列留空（与左侧顶点列对齐）
    for (int j = 0; j < MG.vexNum; j++) {
        cout << setw(3) << MG.vexs[j]; // 输出顶点名称（如 'A'、'B'）
    }
    cout << endl; // 标题行结束换行

    for (int i = 0; i < MG.vexNum; i++) {
        cout << MG.vexs[i] << " "; // 输出左侧顶点名称
        for (int j = 0; j < MG.vexNum; j++) {
            cout << setw(3) << MG.arcs[i][j];
        }
        cout << endl;
    }
}

// 根据邻接矩阵求各顶点入度
void getInDegreeByMG(MGraph G) {
    int inDegree[MaxVertexNum] = {0};  // 存储每个顶点的入度，初始为0
    for (int i = 0; i < G.vexNum; ++i) {
        for (int j = 0; j < G.vexNum; ++j) {
            if (G.arcs[i][j] == 1) {
                inDegree[j]++;
            }
        }
    }
    // 输出邻接矩阵入度信息
    cout << "Calculate the in-degree of vertices using the adjacency matrix:" << endl;
    for (int i = 0; i < G.vexNum; ++i) {
        cout << G.vexs[i] << "'s inDegree: " << inDegree[i] << endl;
    }
}

int main () {
    // 指定文件位置
    string filename = "graph_data.txt";

    MGraph MG;
    // 从文件读取邻接矩阵
    cout << "Create adjacency matrix from the read file:" << endl;
    createUDN(MG, filename);

    // 输出邻接矩阵
    printMG(MG);

    // 根据邻接矩阵求入度
    getInDegreeByMG(MG);
}

6.根据邻接矩阵求各顶点出度

  • 根据文件输入：
1
2
3
4
5
6
7
8
9
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE
  • 输出:
1
2
3
4
5
6
7
8
9
10
11
12
13
Create adjacency matrix from the read file:
    A  B  C  D  E
A   0  1  0  1  0
B   1  0  1  0  1
C   0  1  0  1  1
D   1  0  1  0  1
E   0  1  1  1  0
Calculate the out-degree of vertices using the adjacency matrix:
A's inDegree: 2
B's inDegree: 3
C's inDegree: 3
D's inDegree: 3
E's inDegree: 3
  • 代码：
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
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

#define MaxVertexNum 100

// 定义邻接矩阵结构
typedef struct{
    int vexNum, arcNum; // 顶点数和边数
    char vexs[MaxVertexNum]; // 存顶点
    int arcs[MaxVertexNum][MaxVertexNum]; // 将边
}MGraph;

// 查找顶点在数组中的索引
int locateVexIndex(MGraph G, char v) {
    for (int i = 0; i < G.vexNum; ++i) {
        if (G.vexs[i] == v) {
            return i;
        }
    }
    return -1;
}

// 创建邻接矩阵
void createUDN(MGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexNum >> G.arcNum; // 读取顶点数和边数
    // 读取顶点名称
    for (int i = 0; i < G.vexNum; i++) {
        infile >> G.vexs[i];
    }

    // 初始化邻接矩阵
    for (int i = 0; i < G.vexNum; i++) {
        for (int j = 0; j < G.vexNum; j++) {
            G.arcs[i][j] = 0;
        }
    }

    // 读取邻接关系（边）
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        // 找到顶点下标
        int i = locateVexIndex(G, v1);
        int j = locateVexIndex(G, v2);

        // 构建邻接关系
        if (i == -1 || j == -1) {
            continue;
        }
        // 无向图：边是双向的，矩阵对称
        G.arcs[i][j] = 1;
        G.arcs[j][i] = 1;
    }
}

// 输出邻接矩阵
void printMG(MGraph MG) {
    cout << "  "; // 第一行第一列留空（与左侧顶点列对齐）
    for (int j = 0; j < MG.vexNum; j++) {
        cout << setw(3) << MG.vexs[j]; // 输出顶点名称（如 'A'、'B'）
    }
    cout << endl; // 标题行结束换行

    for (int i = 0; i < MG.vexNum; i++) {
        cout << MG.vexs[i] << " "; // 输出左侧顶点名称
        for (int j = 0; j < MG.vexNum; j++) {
            cout << setw(3) << MG.arcs[i][j];
        }
        cout << endl;
    }
}

// 根据邻接矩阵求各顶点入度
void getOutDegreeByMG(MGraph G) {
    int outDegree[MaxVertexNum] = {0};  // 存储每个顶点的入度，初始为0
    // 就是求对应行有几个
    for (int i = 0; i < G.vexNum; ++i) {
        for (int j = 0; j < G.vexNum; ++j) {
            if (G.arcs[i][j] == 1) {
                outDegree[i]++;
            }
        }
    }
    // 输出邻接矩阵入度信息
    cout << "Calculate the out-degree of vertices using the adjacency matrix:" << endl;
    for (int i = 0; i < G.vexNum; ++i) {
        cout << G.vexs[i] << "'s inDegree: " << outDegree[i] << endl;
    }
}

int main () {
    // 指定文件位置
    string filename = "graph_data.txt";

    MGraph MG;
    // 从文件读取邻接矩阵
    cout << "Create adjacency matrix from the read file:" << endl;
    createUDN(MG, filename);

    // 输出邻接矩阵
    printMG(MG);

    // 根据邻接矩阵求入度
    getOutDegreeByMG(MG);
}

7.根据邻接表求各顶点入度

  • 根据文件输入：
1
2
3
4
5
6
7
8
9
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE
  • 输出:
1
2
3
4
5
6
7
8
9
10
11
12
Create adjacency list from the read file:
A: ->D ->B
B: ->E ->C ->A
C: ->E ->D ->B
D: ->E ->C ->A
E: ->D ->C ->B
Calculate the in-degree of vertices using the adjacency list:
A's inDegree: 2
B's inDegree: 3
C's inDegree: 3
D's inDegree: 3
E's inDegree: 3
  • 代码
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
#include <iostream>
#include <fstream>
using namespace std;

#define MaxVertexNum 100

// 定义边结点结构
typedef struct ArcNode {
    int adjvex; // 邻接点（存下标）
    struct ArcNode *nextarc;
    int info; // 边信息：存权值之类的
} ArcNode;

// 定义顶点结构
typedef struct VNode {
    char data;
    ArcNode *firstArc;
} VNode, AdjList[MaxVertexNum];

// 定义邻接表结构
typedef struct {
    VNode vertices[MaxVertexNum];
    int vexNum, arcNum;
} ALGraph;

// 定位下标
int LocateVexIndex(ALGraph G, char v) {
    for (int i = 0; i < G.vexNum; ++i) {
        if (v == G.vertices[i].data) {
            return i;
        }
    }
    return -1;
}

void createUDG(ALGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexNum >> G.arcNum;
    // 读取顶点信息
    for (int i = 0; i < G.vexNum; ++i) {
        infile >> G.vertices[i].data;
        G.vertices[i].firstArc = NULL;
    }
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        int i = LocateVexIndex(G, v1);
        int j = LocateVexIndex(G, v2);

        // 将邻接边头插入链表
        ArcNode *p1 = new ArcNode();
        p1->nextarc = G.vertices[i].firstArc;
        p1->adjvex = j;
        G.vertices[i].firstArc = p1;

        // 双向
        ArcNode *p2 = new ArcNode();
        p2->nextarc = G.vertices[j].firstArc;
        p2->adjvex = i;
        G.vertices[j].firstArc = p2;
    }
}

// 输出邻接表
void printALG(ALGraph ALG) {
    for (int i = 0; i < ALG.vexNum; ++i) {
        cout << ALG.vertices[i].data << ":";
        // 定义指针用于遍历邻接的点
        ArcNode *p = ALG.vertices[i].firstArc;
        while (p != NULL) {
            cout << " ->" << ALG.vertices[p->adjvex].data;
            p = p->nextarc;
        }
        cout << endl;
    }
}

// 求邻接表的入读
void getInDegreeByALG(ALGraph ALG) {
    int inDegree[MaxVertexNum] = {0};
    for (int i = 0; i < ALG.vexNum; ++i) {
        ArcNode *p = ALG.vertices[i].firstArc;
        while (p != NULL) {
            inDegree[p->adjvex]++;
            p = p->nextarc;
        }
    }
    // 输出入读信息
    cout << "Calculate the in-degree of vertices using the adjacency list:" << endl;
    for (int i = 0; i < ALG.vexNum; i++) {
        cout << ALG.vertices[i].data << "'s inDegree: " << inDegree[i] << endl;
    }
}

int main() {
    // 指定文件读取名称
    string filename = "graph_data.txt";

    ALGraph ALG;

    // 创建邻接表
    cout << "Create adjacency list from the read file:" << endl;
    createUDG(ALG, filename);

    // 将读取的邻接表输出
    printALG(ALG);

    // 求邻接表的入度
    getInDegreeByALG(ALG);
}

8.根据邻接表求各顶点出度

  • 根据文件输入：
1
2
3
4
5
6
7
8
9
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE
  • 输出:
1
2
3
4
5
6
7
8
9
10
11
12
Create adjacency list from the read file:
A: ->D ->B
B: ->E ->C ->A
C: ->E ->D ->B
D: ->E ->C ->A
E: ->D ->C ->B
Calculate the out-degree of vertices using the adjacency list:
A's outDegree: 2
B's outDegree: 3
C's outDegree: 3
D's outDegree: 3
E's outDegree: 3
  • 代码
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
#include <iostream>
#include <fstream>
using namespace std;

#define MaxVertexNum 100

// 定义边结点结构
typedef struct ArcNode {
    int adjvex; // 邻接点（存下标）
    struct ArcNode *nextarc;
    int info; // 边信息：存权值之类的
} ArcNode;

// 定义顶点结构
typedef struct VNode {
    char data;
    ArcNode *firstArc;
} VNode, AdjList[MaxVertexNum];

// 定义邻接表结构
typedef struct {
    VNode vertices[MaxVertexNum];
    int vexNum, arcNum;
} ALGraph;

// 定位下标
int LocateVexIndex(ALGraph G, char v) {
    for (int i = 0; i < G.vexNum; ++i) {
        if (v == G.vertices[i].data) {
            return i;
        }
    }
    return -1;
}

void createUDG(ALGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexNum >> G.arcNum;
    // 读取顶点信息
    for (int i = 0; i < G.vexNum; ++i) {
        infile >> G.vertices[i].data;
        G.vertices[i].firstArc = NULL;
    }
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        int i = LocateVexIndex(G, v1);
        int j = LocateVexIndex(G, v2);

        // 将邻接边头插入链表
        ArcNode *p1 = new ArcNode();
        p1->nextarc = G.vertices[i].firstArc;
        p1->adjvex = j;
        G.vertices[i].firstArc = p1;

        // 双向
        ArcNode *p2 = new ArcNode();
        p2->nextarc = G.vertices[j].firstArc;
        p2->adjvex = i;
        G.vertices[j].firstArc = p2;
    }
}

// 输出邻接表
void printALG(ALGraph ALG) {
    for (int i = 0; i < ALG.vexNum; ++i) {
        cout << ALG.vertices[i].data << ":";
        // 定义指针用于遍历邻接的点
        ArcNode *p = ALG.vertices[i].firstArc;
        while (p != NULL) {
            cout << " ->" << ALG.vertices[p->adjvex].data;
            p = p->nextarc;
        }
        cout << endl;
    }
}

// 求邻接表的出度
void getOutDegreeByALG(ALGraph ALG) {
    int outDegree[MaxVertexNum] = {0};
    for (int i = 0; i < ALG.vexNum; ++i) {
        ArcNode *p = ALG.vertices[i].firstArc;
        while (p != NULL) {
            outDegree[i]++;
            p = p->nextarc;
        }
    }
    // 输出入读信息
    cout << "Calculate the out-degree of vertices using the adjacency list:" << endl;
    for (int i = 0; i < ALG.vexNum; i++) {
        cout << ALG.vertices[i].data << "'s outDegree: " << outDegree[i] << endl;
    }
}

int main() {
    // 指定文件读取名称
    string filename = "graph_data.txt";

    ALGraph ALG;

    // 创建邻接表
    cout << "Create adjacency list from the read file:" << endl;
    createUDG(ALG, filename);

    // 将读取的邻接表输出
    printALG(ALG);

    // 求邻接表的出度
    getOutDegreeByALG(ALG);
}

三、边的插入与删除

9.邻接矩阵中插入删除边

  • 从文件读取;
1
2
3
4
5
6
7
8
9
10
11
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE
AC
AB
  • 输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Create adjacency matrix from the read file:
original adjacency matrix:
    A  B  C  D  E
A   0  1  0  1  0
B   1  0  1  0  1
C   0  1  0  1  1
D   1  0  1  0  1
E   0  1  1  1  0
add arc: A between C
after add adjacency matrix:
    A  B  C  D  E
A   0  1  1  1  0
B   1  0  1  0  1
C   1  1  0  1  1
D   1  0  1  0  1
E   0  1  1  1  0
delete arc: A between B
after delete adjacency matrix:
    A  B  C  D  E
A   0  0  1  1  0
B   0  0  1  0  1
C   1  1  0  1  1
D   1  0  1  0  1
E   0  1  1  1  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
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

#define MaxVertexNum 100

// 定义邻接矩阵结构
typedef struct{
    int vexNum, arcNum; // 顶点数和边数
    char vexs[MaxVertexNum]; // 存顶点
    int arcs[MaxVertexNum][MaxVertexNum]; // 将边
}MGraph;

// 查找顶点在数组中的索引
int locateVexIndex(MGraph G, char v) {
    for (int i = 0; i < G.vexNum; ++i) {
        if (G.vexs[i] == v) {
            return i;
        }
    }
    return -1;
}

// 创建邻接矩阵
void createUDN(MGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexNum >> G.arcNum; // 读取顶点数和边数
    // 读取顶点名称
    for (int i = 0; i < G.vexNum; i++) {
        infile >> G.vexs[i];
    }

    // 初始化邻接矩阵
    for (int i = 0; i < G.vexNum; i++) {
        for (int j = 0; j < G.vexNum; j++) {
            G.arcs[i][j] = 0;
        }
    }

    // 读取邻接关系（边）
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        // 找到顶点下标
        int i = locateVexIndex(G, v1);
        int j = locateVexIndex(G, v2);

        // 构建邻接关系
        if (i == -1 || j == -1) {
            continue;
        }
        // 无向图：边是双向的，矩阵对称
        G.arcs[i][j] = 1;
        G.arcs[j][i] = 1;
    }
}

// 输出邻接矩阵
void printMG(MGraph MG) {
    cout << "  "; // 第一行第一列留空（与左侧顶点列对齐）
    for (int j = 0; j < MG.vexNum; j++) {
        cout << setw(3) << MG.vexs[j]; // 输出顶点名称（如 'A'、'B'）
    }
    cout << endl; // 标题行结束换行

    for (int i = 0; i < MG.vexNum; i++) {
        cout << MG.vexs[i] << " "; // 输出左侧顶点名称
        for (int j = 0; j < MG.vexNum; j++) {
            cout << setw(3) << MG.arcs[i][j];
        }
        cout << endl;
    }
}

// 在邻接矩阵中插入一条边
void addArcToMG(MGraph &MG, char x, char y) {
    // 先定位下标
    int i = locateVexIndex(MG, x);
    int j = locateVexIndex(MG, y);
    MG.arcs[i][j] = 1;
    MG.arcs[j][i] = 1;
}

// 在邻接矩阵中删除一条边
void deleteArcToMG(MGraph &MG, char x, char y) {
    // 先定位下标
    int i = locateVexIndex(MG, x);
    int j = locateVexIndex(MG, y);
    MG.arcs[i][j] = 0;
    MG.arcs[j][i] = 0;
}

int main () {
    // 指定文件位置
    string filename = "addAndDeleteArc_data.txt";

    MGraph MG;
    // 从文件读取邻接矩阵
    cout << "Create adjacency matrix from the read file:" << endl;
    createUDN(MG, filename);

    // 输出邻接矩阵
    cout << "original adjacency matrix:" << endl;
    printMG(MG);

    // 增边：
    cout << "add arc: A between C" << endl;
    addArcToMG(MG, 'A', 'C');

    // 输出邻接矩阵
    cout << "after add adjacency matrix:" << endl;
    printMG(MG);

    // 删边：
    cout << "delete arc: A between B" << endl;
    deleteArcToMG(MG, 'A', 'B');

    // 输出邻接矩阵
    cout << "after delete adjacency matrix:" << endl;
    printMG(MG);
}

10.邻接表中插入删除边

  • 从文件读取;
1
2
3
4
5
6
7
8
9
10
11
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE
AC
AB
  • 输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Create adjacency list from the read file:
A: ->D ->B
B: ->E ->C ->A
C: ->E ->D ->B
D: ->E ->C ->A
E: ->D ->C ->B
add arc: A between C
after add adjacency list:
A: ->C ->D ->B
B: ->E ->C ->A
C: ->A ->E ->D ->B
D: ->E ->C ->A
E: ->D ->C ->B
delete arc: A between B
after delete adjacency list:
A: ->C ->D
B: ->E ->C ->A
C: ->A ->E ->D ->B
D: ->E ->C ->A
E: ->D ->C ->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
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
#include <iostream>
#include <fstream>
using namespace std;

#define MaxVertexNum 100

// 定义边结点结构
typedef struct ArcNode {
    int adjvex; // 邻接点（存下标）
    struct ArcNode *nextarc;
    int info; // 边信息：存权值之类的
} ArcNode;

// 定义顶点结构
typedef struct VNode {
    char data;
    ArcNode *firstArc;
} VNode, AdjList[MaxVertexNum];

// 定义邻接表结构
typedef struct {
    VNode vertices[MaxVertexNum];
    int vexNum, arcNum;
} ALGraph;

// 定位下标
int LocateVexIndex(ALGraph G, char v) {
    for (int i = 0; i < G.vexNum; ++i) {
        if (v == G.vertices[i].data) {
            return i;
        }
    }
    return -1;
}

void createUDG(ALGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexNum >> G.arcNum;
    // 读取顶点信息
    for (int i = 0; i < G.vexNum; ++i) {
        infile >> G.vertices[i].data;
        G.vertices[i].firstArc = NULL;
    }
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        int i = LocateVexIndex(G, v1);
        int j = LocateVexIndex(G, v2);

        // 将邻接边头插入链表
        ArcNode *p1 = new ArcNode();
        p1->nextarc = G.vertices[i].firstArc;
        p1->adjvex = j;
        G.vertices[i].firstArc = p1;

        // 双向
        ArcNode *p2 = new ArcNode();
        p2->nextarc = G.vertices[j].firstArc;
        p2->adjvex = i;
        G.vertices[j].firstArc = p2;
    }
}

// 输出邻接表
void printALG(ALGraph ALG) {
    for (int i = 0; i < ALG.vexNum; ++i) {
        cout << ALG.vertices[i].data << ":";
        // 定义指针用于遍历邻接的点
        ArcNode *p = ALG.vertices[i].firstArc;
        while (p != NULL) {
            cout << " ->" << ALG.vertices[p->adjvex].data;
            p = p->nextarc;
        }
        cout << endl;
    }
}

// 在邻接表中插入一条边
void addArcToALG(ALGraph &ALG, char x, char y) {
    // 先定位下标
    int i = LocateVexIndex(ALG, x);
    int j = LocateVexIndex(ALG, y);
    // 将邻接边头插入链表
    ArcNode *p1 = new ArcNode();
    p1->nextarc = ALG.vertices[i].firstArc;
    p1->adjvex = j;
    ALG.vertices[i].firstArc = p1;

    // 双向
    ArcNode *p2 = new ArcNode();
    p2->nextarc = ALG.vertices[j].firstArc;
    p2->adjvex = i;
    ALG.vertices[j].firstArc = p2;
}

// 在邻接表中删除一条边
void deleteArcToALG(ALGraph &ALG, char x, char y) {
    // 先定位下标
    int i = LocateVexIndex(ALG, x);
    int j = LocateVexIndex(ALG, y);
    // 用于定位要删的边
    ArcNode *p = ALG.vertices[i].firstArc;
    if (p->adjvex != j) {
        p = p->nextarc;
        ArcNode *q = ALG.vertices[i].firstArc;
        while (p != NULL) {
            if (p->adjvex == j) {
                q->nextarc = p->nextarc;
            }
            // 移动指针
            q = q->nextarc;
            p = p->nextarc;
        }
    } else {
        ALG.vertices[i].firstArc = p->nextarc;
    }
}

int main() {
    // 指定文件读取名称
    string filename = "addAndDeleteArc_data.txt";

    ALGraph ALG;

    // 创建邻接表
    cout << "Create adjacency list from the read file:" << endl;
    createUDG(ALG, filename);

    // 将读取的邻接表输出
    printALG(ALG);

    // 增边：
    cout << "add arc: A between C" << endl;
    addArcToALG(ALG, 'A', 'C');

    // 输出邻接表
    cout << "after add adjacency list:" << endl;
    printALG(ALG);

    // 删边：
    cout << "delete arc: A between B" << endl;
    deleteArcToALG(ALG, 'A', 'B');

    // 输出邻接表
    cout << "after delete adjacency list:" << endl;
    printALG(ALG);
}

四、特殊转换与遍历

11.邻接表转逆邻接表

  • 通过文件输入:
1
2
3
4
5
6
7
8
9
5 7
ABCDE
AB
AD
BC
BE
CD
CE
DE
  • 输出：
1
2
3
4
5
6
7
8
9
10
11
12
Create adjacency list from the read file:
A: ->D ->B
B: ->E ->C ->A
C: ->E ->D ->B
D: ->E ->C ->A
E: ->D ->C ->B
Convert adjacency list to reverse adjacency list,Conversion result
A: ->D ->B
B: ->E ->C ->A
C: ->E ->D ->B
D: ->E ->C ->A
E: ->D ->C ->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
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
#include <iostream>
#include <iomanip>
#include <fstream>

using namespace std;

#define MaxVexNum 100

// 定义邻接结构
typedef struct ArcNode {
    int adjVex; // 邻接点下标
    struct ArcNode *nextArc;
}ArcNode;

// 定义邻接表结点结构
typedef struct VNode {
    char data; // 顶点名称
    ArcNode *firstArc;
}VNode, AdjList[MaxVexNum];

// 定义邻接表结构
typedef struct {
    VNode vertices[MaxVexNum];
    int vexNum, arcNum;
}ALGraph;

// 根据输入的信息创建邻接表
void CreateUDG(ALGraph &G, const string &filename) {
    ifstream infile(filename);
    // 读取顶点数和边数
    infile >> G.vexNum >> G.arcNum;
    // 读取顶点名称
    for (int i = 0; i < G.vexNum; ++i) {
        infile >> G.vertices[i].data;
        G.vertices[i].firstArc = NULL;
    }

    // 读取邻接信息存入邻接表
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;
        int a, b; // 用于定位下标
        for (int i = 0; i < G.vexNum; ++i) {
            if (v1 == G.vertices[i].data) {
                a = i;
            }
            if (v2 == G.vertices[i].data) {
                b = i;
            }
        }
        // 建立v1到v2的边
        ArcNode *newNode1 = new ArcNode;
        newNode1->nextArc = G.vertices[a].firstArc;
        G.vertices[a].firstArc = newNode1;
        newNode1->adjVex = b;

        // 建立v2到v1的边
        ArcNode *newNode2 = new ArcNode;
        newNode2->nextArc = G.vertices[b].firstArc;
        G.vertices[b].firstArc = newNode2;
        newNode2->adjVex = a;
    }
}

// 根据已经创建好的邻接表创建逆邻接表
void CreateRALGByALG(ALGraph &RALG, ALGraph ALG) {
    RALG.vexNum = ALG.vexNum;
    RALG.arcNum = ALG.arcNum;
    // 读取顶点名称并初始化
    for (int i = 0; i < ALG.vexNum; ++i) {
        RALG.vertices[i].data = ALG.vertices[i].data;
        RALG.vertices[i].firstArc = NULL;
    }
    // 根据邻接表信息创建逆邻接表
    for (int i = 0; i < ALG.vexNum; ++i) {
        // 建立指针遍历邻接边
        ArcNode *p = ALG.vertices[i].firstArc;
        while (p != NULL) {
            ArcNode *newNode = new ArcNode;
            newNode->adjVex = i;
            newNode->nextArc = RALG.vertices[p->adjVex].firstArc;
            RALG.vertices[p->adjVex].firstArc = newNode;
            p = p->nextArc;
        }
    }
}

// 输出邻接表
void printALG(ALGraph ALG) {
    for (int i = 0; i < ALG.vexNum; ++i) {
        cout << ALG.vertices[i].data << ":";
        // 定义指针用于遍历邻接的点
        ArcNode *p = ALG.vertices[i].firstArc;
        while (p != NULL) {
            cout << " ->" << ALG.vertices[p->adjVex].data;
            p = p->nextArc;
        }
        cout << endl;
    }
}

int main () {
    // 指定文件名称
    string filename = "graph_data.txt";

    ALGraph ALG;
    ALGraph RALG;

    // 创建邻接表
    CreateUDG(ALG, filename);

    // 输出创建的邻接表
    cout << "Create adjacency list from the read file:" << endl;
    printALG(ALG);

    // 邻接表转逆邻接表
    cout << "Convert adjacency list to reverse adjacency list,Conversion result" << endl;
    CreateRALGByALG(RALG, ALG);

    // 输出逆邻接表
    printALG(RALG);
}

12. 邻接矩阵的深度优先搜索（DFS）

  • 从文件输入
1
2
3
4
5
6
7
8
9
10
8 8
ABCDEFGH
A B
A C
B D
B E
C F
C G
D H
E H
  • 输出：
1
A B D H E C F G
  • 代码
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
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
using namespace std;
#define MVNum 10

int visited[MVNum];
typedef struct{
    char vexs[MVNum];
    int arcs[MVNum][MVNum];
    int vexnum,arcnum;
}MGraph;

// 查找顶点在数组中的索引
int locateVexIndex(MGraph G, char v) {
    for (int i = 0; i < G.vexnum; ++i) {
        if (G.vexs[i] == v) {
            return i;
        }
    }
    return -1;
}

// 创建邻接矩阵
void createUDN(MGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexnum >> G.arcnum; // 读取顶点数和边数
    // 读取顶点名称
    for (int i = 0; i < G.vexnum; i++) {
        infile >> G.vexs[i];
    }

    // 初始化邻接矩阵
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            G.arcs[i][j] = 0;
        }
    }

    // 读取邻接关系（边）
    for (int k = 0; k < G.arcnum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        // 找到顶点下标
        int i = locateVexIndex(G, v1);
        int j = locateVexIndex(G, v2);

        // 构建邻接关系
        if (i == -1 || j == -1) {
            continue;
        }
        // 无向图：边是双向的，矩阵对称
        G.arcs[i][j] = 1;
        G.arcs[j][i] = 1;
    }
}
void DFS(MGraph MG, int v) {
    visited[v] = 1;
    cout << MG.vexs[v] << " ";
    for (int i = 0; i < MG.vexnum; i++) {
        if (MG.arcs[v][i] == 1 && !visited[i]) {
            DFS(MG, i);
        }
    }
}
void DFSTraverse(MGraph MG){
    int v;
    for(v = 0; v < MG.vexnum; ++v)  visited[v] = 0;
    for(v = 0; v < MG.vexnum; ++v)
        if(!visited[v])  DFS(MG, v);
}
int main(){
    string filename = "DFS_data.txt";
    MGraph MG;
    createUDN(MG, filename);
    DFSTraverse(MG);
    return 0;
}

13. 邻接矩阵的广度优先搜索（BFS）

  • 从文件输入
1
2
3
4
5
6
7
8
9
10
8 8
ABCDEFGH
A B
A C
B D
B E
C F
C G
D H
E H
  • 输出：
1
A B C D E F G H
  • 代码
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
#include <iostream>
#include <queue>
#include <fstream>
using namespace std;
#define MVNum 10

int visited[MVNum];
typedef struct{
    char vexs[MVNum];
    int arcs[MVNum][MVNum];
    int vexnum,arcnum;
}MGraph;

// 查找顶点在数组中的索引
int locateVexIndex(MGraph G, char v) {
    for (int i = 0; i < G.vexnum; ++i) {
        if (G.vexs[i] == v) {
            return i;
        }
    }
    return -1;
}

// 创建邻接矩阵
void createUDN(MGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexnum >> G.arcnum; // 读取顶点数和边数
    // 读取顶点名称
    for (int i = 0; i < G.vexnum; i++) {
        infile >> G.vexs[i];
    }

    // 初始化邻接矩阵
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            G.arcs[i][j] = 0;
        }
    }

    // 读取邻接关系（边）
    for (int k = 0; k < G.arcnum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        // 找到顶点下标
        int i = locateVexIndex(G, v1);
        int j = locateVexIndex(G, v2);

        // 构建邻接关系
        if (i == -1 || j == -1) {
            continue;
        }
        // 无向图：边是双向的，矩阵对称
        G.arcs[i][j] = 1;
        G.arcs[j][i] = 1;
    }
}
// 广度优先搜索
void BFS(MGraph G, int v) {
    queue<int> queue;
    if (!visited[v]) {
        visited[v] = 1; // 标记已访问
        cout << G.vexs[v];
        queue.push(v); // 入队
        // 遍历所有顶点，寻找邻接且未访问的顶点
        while (!queue.empty()) {
            int num = queue.front();
            queue.pop(); // 出队
            for (int i = 0; i < G.vexnum; i++) {
                if (G.arcs[num][i] == 1 && !visited[i]) {
                    visited[i] = 1;
                    cout << " " << G.vexs[i];
                    queue.push(i);
                }
            }
        }
    }
    cout << " ";
}

void BFSTraverse(MGraph G){
    int v;
    for(v = 0; v < G.vexnum; ++v)  visited[v] = 0;
    for(v = 0; v < G.vexnum; ++v)
        if(!visited[v])  BFS(G, v);
}
int main(){
    // 指定读取文件位置
    string filename = "BFS_data.txt";
    MGraph G;
    createUDN(G, filename);

    // 广度优先搜索
    BFSTraverse(G);
    return 0;
}

14. 邻接表的深度优先搜索（DFS）

  • 从文件输入
1
2
3
4
5
6
7
8
9
10
8 8
ABCDEFGH
A B
A C
B D
B E
C F
C G
D H
E H
  • 输出：
1
A C G F B E H D
  • 代码
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
#include <iostream>
#include <fstream>
using namespace std;
#define MVNum 10
int visited[MVNum];
typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
    int info;
}ArcNode;

typedef struct VNode{
    char data;
    ArcNode *firstArc;
}VNode, AdjList[MVNum];

typedef struct{
    AdjList vertices;
    int vexNum, arcNum;
}ALGraph;

// 定位下标
int LocateVexIndex(ALGraph G, char v) {
    for (int i = 0; i < G.vexNum; ++i) {
        if (v == G.vertices[i].data) {
            return i;
        }
    }
    return -1;
}

void createUDG(ALGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexNum >> G.arcNum;
    // 读取顶点信息
    for (int i = 0; i < G.vexNum; ++i) {
        infile >> G.vertices[i].data;
        G.vertices[i].firstArc = NULL;
    }
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        int i = LocateVexIndex(G, v1);
        int j = LocateVexIndex(G, v2);

        // 将邻接边头插入链表
        ArcNode *p1 = new ArcNode();
        p1->nextarc = G.vertices[i].firstArc;
        p1->adjvex = j;
        G.vertices[i].firstArc = p1;

        // 双向
        ArcNode *p2 = new ArcNode();
        p2->nextarc = G.vertices[j].firstArc;
        p2->adjvex = i;
        G.vertices[j].firstArc = p2;
    }
}

// 深度优先搜索
void DFS(ALGraph G, int v) {
    visited[v] = 1;
    cout << G.vertices[v].data << " ";
    ArcNode *p = G.vertices[v].firstArc;
    while (p != NULL) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex);
        }
        p = p->nextarc;
    }
}
void DFSTraverse(ALGraph G){
    int v;
    for(v = 0; v < G.vexNum; ++v)
        visited[v] = 0;
    for(v = 0; v < G.vexNum; ++v)
        if(!visited[v])
            DFS(G, v);
}

int main(){
    // 指定文件读取位置
    string filename = "DFS_data.txt";
    ALGraph G;
    createUDG(G, filename);

    // 深度优先搜索
    DFSTraverse(G);
    return 0;
}

15. 邻接表的广度优先搜索（BFS）

  • 从文件输入
1
2
3
4
5
6
7
8
9
10
8 8
ABCDEFGH
A B
A C
B D
B E
C F
C G
D H
E H
  • 输出：
1
A C B G F E D H
  • 代码
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
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
#define MVNum 10
#define MAXQSIZE 100

bool visited[MVNum];
typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextarc;
    int info;
}ArcNode;

typedef struct VNode{
    char data;
    ArcNode *firstArc;
}VNode, AdjList[MVNum];

typedef struct{
    AdjList vertices;
    int vexNum, arcNum;
}ALGraph;

// 定位下标
int LocateVexIndex(ALGraph G, char v) {
    for (int i = 0; i < G.vexNum; ++i) {
        if (v == G.vertices[i].data) {
            return i;
        }
    }
    return -1;
}

void createUDG(ALGraph &G, const string &filename) {
    ifstream infile(filename);
    infile >> G.vexNum >> G.arcNum;
    // 读取顶点信息
    for (int i = 0; i < G.vexNum; ++i) {
        infile >> G.vertices[i].data;
        G.vertices[i].firstArc = NULL;
    }
    for (int k = 0; k < G.arcNum; ++k) {
        char v1, v2;
        infile >> v1 >> v2;

        int i = LocateVexIndex(G, v1);
        int j = LocateVexIndex(G, v2);

        // 将邻接边头插入链表
        ArcNode *p1 = new ArcNode();
        p1->nextarc = G.vertices[i].firstArc;
        p1->adjvex = j;
        G.vertices[i].firstArc = p1;

        // 双向
        ArcNode *p2 = new ArcNode();
        p2->nextarc = G.vertices[j].firstArc;
        p2->adjvex = i;
        G.vertices[j].firstArc = p2;
    }
}

void BFS(ALGraph G, int v) {
    queue<int> queue;
    if (!visited[v]) {
        queue.push(v);
        visited[v] = 1;
        cout << G.vertices[v].data;
        // 当队列不空

        while (!queue.empty()) {
            int num = queue.front();
            queue.pop();
            ArcNode *p = G.vertices[num].firstArc;
            // 依次遍历顶点邻接边
            while (p != NULL) {
                if (!visited[p->adjvex]){
                    queue.push(p->adjvex);
                    visited[p->adjvex] = 1;
                    cout  << " " << G.vertices[p->adjvex].data;
                }
                p = p->nextarc;
            }
        }
    }
    cout << " ";
}
void BFSTraverse(ALGraph G){
    int v;
    for(v = 0; v < G.vexNum; ++v)
        visited[v] = 0;
    for(v = 0; v < G.vexNum; ++v)
        if(!visited[v])
            BFS(G, v);
}

int main(){
    // 指定文件读取位置
    string filename = "BFS_data.txt";
    ALGraph G;
    createUDG(G, filename);
    // 广度优先搜索
    BFSTraverse(G);
    return 0;
}