图的存储结构

图的存储结构

   数据结构 40 分钟读完 (大约6059个字) 0次访问

一、图的邻接矩阵表示——（Adjacency Matrix)

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
#include<cstdlib>
#include<iostream>
#include<string>
#include<limits.h>
using namespace std;
//----------------自定义邻接矩阵模板类-----------------//

//-------------图的数组（邻接矩阵存储）表示-----------//
#define Max_Vertex_Num 20 
#define inp(i,x,y) for(i=x;i<=y;i++)
#define dep(i,x,y) for(i=x;i>=y;i--)
#define INFINITY INT_MAX

typedef enum { DG, DN, UDG, UDN }GraphKind;    //{有向图，有向网，无向图，无向网}
typedef int VRType;
typedef string InfoType;
typedef string VertexType;
typedef bool Status;


typedef struct ArcCell {
    VRType adj;   // 顶点关系类型，无权图，用1或0表相邻否；有权图为权值
    InfoType info;   //弧相关信息指针
}ArcCell, AdjMatrix[Max_Vertex_Num][Max_Vertex_Num];

typedef struct {
    VertexType vexs[Max_Vertex_Num];  // 顶点向量
    AdjMatrix arcs;   // 邻接矩阵
    int vexnum, arcnum;  // 图的当前顶点数和弧数
    GraphKind kind;     // 图种类标志 
}MGraph;

int LocateVex(MGraph G, VertexType v);
Status CreateDG(MGraph& G);
Status CreateDN(MGraph& G);
Status CreateUDG(MGraph& G);
Status CreateUDN(MGraph& G);
Status CreateGraph(MGraph& G);
Status GraphPrint(MGraph G);
int main()
{
    MGraph G;
    CreateGraph(G);
    GraphPrint(G);
    return 0;
}
Status CreateGraph(MGraph& G)
{
    // 采用邻接矩阵表示法，构造图G
    int sign = 0;
    cout << "Input the type of graph(0:DG,1:DN,2:UDG,3:UDN):\n";
    cin >> sign;
    switch (sign) {
    case DG:
        G.kind = DG;
        return CreateDG(G);  // diagraph
    case DN:
        G.kind = DN;
        return CreateDN(G);  // dianetwork
    case UDG:
        G.kind = UDG;
        return CreateUDG(G);  //undiagraph
    case UDN:
        G.kind = UDN;
        return CreateUDN(G);  //undianetwork
    default:return false;
    }
}

Status CreateUDN(MGraph& G)
{
    // 采用数组（邻接矩阵）表示法构造无向网G
    int IncInfo = 0, i = 0, j = 0;
    cout << "Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):\n";
    cin >> G.vexnum >> G.arcnum >> IncInfo;   // IncInfo为0则各弧不含其他信息

    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) cin >> G.vexs[i];   // 节点数据
    inp(i, 0, G.vexnum - 1)  // 初始化邻接矩阵
        inp(j, 0, G.vexnum - 1) G.arcs[i][j] = { INFINITY, "" }; //{adj,info}

    cout << "Input two vertices and weight of the edges:\n";
    inp(i, 0, G.arcnum - 1) {
        VertexType v1, v2;
        int w = 0;
        cin >> v1 >> v2 >> w;     // 输入一条边的顶点和权值
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;

        G.arcs[p1][p2].adj = w;    // 弧<v1,v2>的权值w
        if (IncInfo) cin >> G.arcs[p1][p2].info;     // 如果弧有信息则输入
        G.arcs[p2][p1] = G.arcs[p1][p2];     // 无向图
    }
    return true;
}
Status CreateUDG(MGraph& G)
{
    // 采用数组（邻接矩阵）表示法构造无向图G
    int IncInfo = 0, i = 0, j = 0;
    cout << "Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):\n";
    cin >> G.vexnum >> G.arcnum >> IncInfo;   // IncInfo为0则各弧不含其他信息

    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) cin >> G.vexs[i];   // 节点数据
    inp(i, 0, G.vexnum - 1)  // 初始化邻接矩阵
        inp(j, 0, G.vexnum - 1) G.arcs[i][j] = { 0, "" }; //{adj,info}

    cout << "Input two vertices of the edges:\n";
    inp(i, 0, G.arcnum - 1) {
        VertexType v1, v2;
        cin >> v1 >> v2;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;

        G.arcs[p1][p2].adj = 1;    // 弧<v1,v2>的权值w
        if (IncInfo) cin >> G.arcs[p1][p2].info;     // 如果弧有信息则输入
        G.arcs[p2][p1] = G.arcs[p1][p2];     // 无向图
    }
    return true;
}
Status CreateDG(MGraph& G)
{
    // 采用数组（邻接矩阵）表示法构造无向图G
    int IncInfo = 0, i = 0, j = 0;
    cout << "Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):\n";
    cin >> G.vexnum >> G.arcnum >> IncInfo;   // IncInfo为0则各弧不含其他信息

    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) cin >> G.vexs[i];   // 节点数据
    inp(i, 0, G.vexnum - 1)  // 初始化邻接矩阵
        inp(j, 0, G.vexnum - 1) G.arcs[i][j] = { 0, "" }; //{adj,info}

    cout << "Input two vertices of the edges:\n";
    inp(i, 0, G.arcnum - 1) {
        VertexType v1, v2;
        cin >> v1 >> v2;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;

        G.arcs[p1][p2].adj = 1;    // 弧<v1,v2>的权值w
        if (IncInfo) cin >> G.arcs[p1][p2].info;     // 如果弧有信息则输入
    }
    return true;
}
Status CreateDN(MGraph& G)
{
    // 采用数组（邻接矩阵）表示法构造无向图G
    int IncInfo = 0, i = 0, j = 0;
    cout << "Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):\n";
    cin >> G.vexnum >> G.arcnum >> IncInfo;   // IncInfo为0则各弧不含其他信息

    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) cin >> G.vexs[i];   // 节点数据
    inp(i, 0, G.vexnum - 1)  // 初始化邻接矩阵
        inp(j, 0, G.vexnum - 1) G.arcs[i][j] = { INFINITY, "" }; //{adj,info}

    cout << "Input two vertices and weight of the edges:\n";
    inp(i, 0, G.arcnum - 1) {
        VertexType v1, v2;
        int w = 0;
        cin >> v1 >> v2 >> w;     // 输入一条边的顶点和权值
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;

        G.arcs[p1][p2].adj = w;    // 弧<v1,v2>的权值w
        if (IncInfo) cin >> G.arcs[p1][p2].info;     // 如果弧有信息则输入
    }
    return true;
}
int LocateVex(MGraph G, VertexType v)
{
    int i = 0;
    inp(i, 0, G.vexnum - 1) {
        if (G.vexs[i] == v)
            return i;
    }
    return -1;
}
Status GraphPrint(MGraph G)
{
    cout << "Output Graph Information:\n";
    cout << "Graph Kind: ";
    switch (G.kind) {
    case DG:cout << "directed graph\n";  // diagraph
        break;
    case DN:cout << "directed nets\n";  // dianetwork
        break;
    case UDG:cout << "undirected graph\n";  //undiagraph
        break;
    case UDN:cout << "undirected nets\n";  //undianetwork
        break;
    default:return false;
    }
    cout << "Vextices number: " << G.vexnum << "   " << "Arcs number: " << G.arcnum << endl;
    int i = 0, j = 0;
    cout << "Vextices Vector Information:\n";
    int sign = (G.kind == DG || G.kind == UDG) ? 1 : 0;   // 图标记
    inp(i, 0, G.vexnum - 1) {
        int Outdegree = 0, Indegree = 0;
        inp(j, 0, G.vexnum - 1) {
            if (G.arcs[i][j].adj != INFINITY && (!sign || (sign && G.arcs[i][j].adj != 0))) {
                Outdegree++;
                cout << G.vexs[i] << "-<" << G.arcs[i][j].adj << ">-" << G.vexs[j] << " ";
            }
            if (G.arcs[j][i].adj != INFINITY && (!sign || (sign && G.arcs[j][i].adj != 0))) Indegree++;
        }
        cout << endl << G.vexs[i];
        if (G.kind == DG || G.kind == DN)
            cout << "  Vextice Degree: " << Outdegree + Indegree << "  Outdegree: " << Outdegree
            << "  Indegree: " << Indegree << endl;
        else cout << "  Vextice Degree: " << Outdegree << endl;
    }
    return true;
}

给出一个算例演示：

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
/*-------------Here is a demo------------
Input the type of graph(0:DG,1:DN,2:UDG,3:UDN):
1
Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):
6 10 0
Input Graph Node Sign:
v1 v2 v3 v4 v5 v6
Input two vertices and weight of the edges:
v1 v2 5
v1 v4 7
v2 v3 4
v3 v1 8
v3 v6 9
v4 v3 5
v4 v6 6
v5 v4 5
v6 v1 3
v6 v5 1
Output Graph Information:
Graph Kind: directed nets
Vextices number: 6   Arcs number: 10
Vextices Vector Information:
v1-<5>-v2 v1-<7>-v4
v1  Vextice Degree: 4  Outdegree: 2  Indegree: 2
v2-<4>-v3
v2  Vextice Degree: 2  Outdegree: 1  Indegree: 1
v3-<8>-v1 v3-<9>-v6
v3  Vextice Degree: 4  Outdegree: 2  Indegree: 2
v4-<5>-v3 v4-<6>-v6
v4  Vextice Degree: 4  Outdegree: 2  Indegree: 2
v5-<5>-v4
v5  Vextice Degree: 2  Outdegree: 1  Indegree: 1
v6-<3>-v1 v6-<1>-v5
v6  Vextice Degree: 4  Outdegree: 2  Indegree: 2
*/

二、图的邻接表表示——（Adjacency List)

本节基于邻接表和逆邻接表表示图，以及求解图的度数；

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
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
//---------------------图的邻接表存储表示-----------------//
#define inp(i,x,y) for(i=x;i<=y;i++)
#define dep(i,x,y) for(i=x;i>=y;i--)
#define Max_Vertex_Num 20

typedef enum { DG, DN, UDG, UDN }GraphKind;    //{有向图，有向网，无向图，无向网}
typedef string InfoType;
typedef string VertexType;
typedef bool Status;
//----------弧节点结构-------------//
typedef struct ArcNode {
    int adjvex;   // 该弧所指向的顶点位置
    int weight;   // 弧的权值
    struct ArcNode* nextarc;    // 指向下一条弧指针
    InfoType info;       // 该弧相关信息
    ArcNode()
    {
        adjvex = weight = 0;
        nextarc = NULL;
        info = "";
    }
}ArcNode;
//----------头节点结构---------------//
typedef struct VNode {
    VertexType data;   // 顶点信息
    int Outdegree;     // 节点对应的出度
    ArcNode* firstarc;   // 指向第一条依附该顶点的弧的指针
    VNode()
    {
        data = "";
        Outdegree = 0;
        firstarc = NULL;
    }
}VNode, AdjList[Max_Vertex_Num];
//----------图结构定义---------------//
typedef struct {
    AdjList Vextices;
    int vexnum, arcnum;    // 图的顶点数和弧数
    int kind;       // 图的种类标志
}ALGraph;

//--------------头节点定位函数---------------------//
int LocateVex(ALGraph G, VertexType v);
//-------------------构建节点函数------------------//
Status GraphAddNode(ALGraph& G, int p1, int p2, int w, int IncInfo);
//-------------------图创建函数--------------------//
Status CreateDG(ALGraph& G, ALGraph& GR);
Status CreateDN(ALGraph& G, ALGraph& GR);
Status CreateUDG(ALGraph& G, ALGraph& GR);
Status CreateUDN(ALGraph& G, ALGraph& GR);
Status CreateGraph(ALGraph& G, ALGraph& GR);

//------------------图输出函数---------------------//
Status GraphPrint(ALGraph G, ALGraph GR);

int main()
{
    ALGraph G, GR;   // G:邻接表，GR:逆邻接表
    CreateGraph(G, GR);
    GraphPrint(G, GR);
    return 0;
}

Status CreateGraph(ALGraph& G, ALGraph& GR)
{
    cout << "Input the type of graph(0:DG,1:DN,2:UDG,3:UDN):\n";
    cin >> G.kind;      // 种类标识
    GR.kind = G.kind;
    switch (G.kind) {
    case 0:return CreateDG(G, GR);
    case 1:return CreateDN(G, GR);
    case 2:return CreateUDG(G, GR);
    case 3:return CreateUDN(G, GR);
    default:return false;
    }
}

Status CreateDG(ALGraph& G, ALGraph& GR)
{
    // 采用邻接表表示法构造有向图G
    int IncInfo = 0, i = 0, j = 0;
    cout << "Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):\n";
    cin >> G.vexnum >> G.arcnum >> IncInfo;   // IncInfo为0则各弧不含其他信息
    GR.vexnum = G.vexnum; GR.arcnum = G.arcnum;

    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) {
        cin >> G.Vextices[i].data;   // 节点数据
        GR.Vextices[i].data = G.Vextices[i].data;
    }

    cout << "Input two vertices of the edges:\n";
    inp(i, 0, G.arcnum - 1) {
        VertexType v1, v2;
        cin >> v1 >> v2;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;

        GraphAddNode(G, p1, p2, 1, IncInfo);   // 邻接表中p1->p2 ==> p1的出度
        GraphAddNode(GR, p2, p1, 1, IncInfo);   // 逆邻接表中p1->p2 ==> p2的入度
    }
    return true;
}

Status CreateDN(ALGraph& G, ALGraph& GR)
{
    // 采用邻接表表示法构造有向网G
    int IncInfo = 0, i = 0, j = 0;
    cout << "Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):\n";
    cin >> G.vexnum >> G.arcnum >> IncInfo;   // IncInfo为0则各弧不含其他信息
    GR.vexnum = G.vexnum; GR.arcnum = G.arcnum;

    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) {
        cin >> G.Vextices[i].data;   // 节点数据
        GR.Vextices[i].data = G.Vextices[i].data;
    }

    cout << "Input two vertices and weight of the edges:\n";
    inp(i, 0, G.arcnum - 1) {
        VertexType v1, v2;
        int w = 0;
        cin >> v1 >> v2 >> w;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;

        GraphAddNode(G, p1, p2, w, IncInfo);   // 邻接表中p1->p2 ==> p1的出度
        GraphAddNode(GR, p2, p1, w, IncInfo);  // 逆邻接表中p1->p2 ==> p2的入度
    }
    return true;
}

Status CreateUDG(ALGraph& G, ALGraph& GR)
{
    // 采用邻接表表示法构造无向图G
    int IncInfo = 0, i = 0, j = 0;
    cout << "Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):\n";
    cin >> G.vexnum >> G.arcnum >> IncInfo;   // IncInfo为0则各弧不含其他信息
    GR.vexnum = G.vexnum; GR.arcnum = G.arcnum;

    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) {
        cin >> G.Vextices[i].data;   // 节点数据
        GR.Vextices[i].data = G.Vextices[i].data;
    }

    cout << "Input two vertices of the edges:\n";
    inp(i, 0, G.arcnum - 1) {
        VertexType v1, v2;
        cin >> v1 >> v2;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;

        // 对无向图而言，逆邻接表作用不是很显著，实际使用中可删除
        GraphAddNode(G, p1, p2, 1, IncInfo);   // p2挂在p1链表上
        GraphAddNode(G, p2, p1, 1, IncInfo);   // p1挂在p2链表上
        GraphAddNode(GR, p1, p2, 1, IncInfo);
        GraphAddNode(GR, p2, p1, 1, IncInfo);
    }
    return true;
}

Status CreateUDN(ALGraph& G, ALGraph& GR)
{
    // 采用邻接表表示法构造无向网G
    int IncInfo = 0, i = 0, j = 0;
    cout << "Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):\n";
    cin >> G.vexnum >> G.arcnum >> IncInfo;   // IncInfo为0则各弧不含其他信息
    GR.vexnum = G.vexnum; GR.arcnum = G.arcnum;

    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) {
        cin >> G.Vextices[i].data;   // 节点数据
        GR.Vextices[i].data = G.Vextices[i].data;
    }

    cout << "Input two vertices and weight of the edges:\n";
    inp(i, 0, G.arcnum - 1) {
        VertexType v1, v2;
        int w = 0;
        cin >> v1 >> v2 >> w;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;

        GraphAddNode(G, p1, p2, w, IncInfo);    // 附权值w
        GraphAddNode(G, p2, p1, w, IncInfo);
        GraphAddNode(GR, p1, p2, w, IncInfo);
        GraphAddNode(GR, p2, p1, w, IncInfo);
    }
    return true;
}

Status GraphAddNode(ALGraph& G, int p1, int p2, int w, int IncInfo)
{
    // 将弧的头节点p2挂在尾节点p1的链表上
    ArcNode* p = G.Vextices[p1].firstarc;
    int sign = 0;
    while (p) { 
        if (p->adjvex == p2) {     //如果已经存在
            sign = 1;
            if (IncInfo) cin >> p->info;     // 如果弧有信息则输入
            break;
        }
        if (!p->nextarc) break;
        p = p->nextarc;
    }
    if (!sign) {
        if (!p) {
            p = (ArcNode*)malloc(sizeof(ArcNode));
            G.Vextices[p1].firstarc = p;
        }
        else {
            p->nextarc = (ArcNode*)malloc(sizeof(ArcNode));
            p = p->nextarc;
        }

        p->adjvex = p2;
        p->weight = w;    // 弧<v1,v2>的权值w   
        p->nextarc = NULL;
        if (IncInfo) cin >> p->info;     // 如果弧有信息则输入
        G.Vextices[p1].Outdegree++;
    }
    return true;
}

int LocateVex(ALGraph G, VertexType v)
{
    int i = 0;
    inp(i, 0, G.vexnum - 1) {
        if (G.Vextices[i].data == v)
            return i;
    }
    return -1;
}

Status GraphPrint(ALGraph G, ALGraph GR)
{
    cout << "----------------Output Graph Information-----------------\n";
    cout << "Graph Kind: ";
    switch (G.kind) {
    case DG:cout << "directed graph\n";  // diagraph
        break;
    case DN:cout << "directed nets\n";  // dianetwork
        break;
    case UDG:cout << "undirected graph\n";  //undiagraph
        break;
    case UDN:cout << "undirected nets\n";  //undianetwork
        break;
    default:return false;
    }
    cout << "Vextices number: " << G.vexnum << "   " << "Arcs number: " << G.arcnum << endl;
    int i = 0, j = 0;
    cout << endl << "----------------Vextices Vector Information----------------\n";
    int sign = (G.kind == DG || G.kind == DN) ? 1 : 0;   // 图标记
    cout << "The Nodes Path:\n";
    inp(i, 0, G.vexnum - 1) {
        ArcNode* p = G.Vextices[i].firstarc;
        ArcNode* q = GR.Vextices[i].firstarc;
        if (sign) {
            cout << "Out path: ";
            while (p) {
                cout << G.Vextices[i].data << "-[" << p->weight << "]->" << G.Vextices[p->adjvex].data << "  ";
                p = p->nextarc;
            }
            cout << endl << "In path: ";
            while (q) {
                cout << GR.Vextices[q->adjvex].data << "-[" << q->weight << "]->-" << GR.Vextices[i].data << "  ";
                q = q->nextarc;
            }
            cout << endl << G.Vextices[i].data;
            cout << "  Vextice Degree: " << G.Vextices[i].Outdegree + GR.Vextices[i].Outdegree << "  Outdegree: " << G.Vextices[i].Outdegree
                << "  Indegree: " << GR.Vextices[i].Outdegree << endl;
        }
        else {
            cout << "Out path: ";
            while (p) {
                cout << G.Vextices[i].data << "-<-[" << p->weight << "]->-" << G.Vextices[p->adjvex].data << "  ";
                p = p->nextarc;
            }
            cout << endl << G.Vextices[i].data;
            cout << "  Vextice Degree: " << G.Vextices[i].Outdegree << endl;
        }
        cout << endl;
    }
    return true;
}

给出一个算例演示：

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
//---------- Here is a drected graph demo -------//
/*
Input the type of graph(0:DG,1:DN,2:UDG,3:UDN):
0
Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):
4 7 0
Input Graph Node Sign:
V1 V2 V3 V4
Input two vertices of the edges:
V1 V2
V3 V1
V1 V3
V4 V1
V3 V4
V4 V3
V4 V2
----------------Output Graph Information-----------------
Graph Kind: directed graph
Vextices number: 4   Arcs number: 7

----------------Vextices Vector Information----------------
The Nodes Path:
Out path: V1-[1]->V2  V1-[1]->V3
In path: V3-[1]->-V1  V4-[1]->-V1
V1  Vextice Degree: 4  Outdegree: 2  Indegree: 2

Out path:
In path: V1-[1]->-V2  V4-[1]->-V2
V2  Vextice Degree: 2  Outdegree: 0  Indegree: 2

Out path: V3-[1]->V1  V3-[1]->V4
In path: V1-[1]->-V3  V4-[1]->-V3
V3  Vextice Degree: 4  Outdegree: 2  Indegree: 2

Out path: V4-[1]->V1  V4-[1]->V3  V4-[1]->V2
In path: V3-[1]->-V4
V4  Vextice Degree: 4  Outdegree: 3  Indegree: 1
*/
//---------- Here is a undrected graph demo -------//
/*Input the type of graph(0:DG,1:DN,2:UDG,3:UDN):
2
Input Vextices number, Arcs number and Incinformation(1:Yes,0:NO):
4 7 0
Input Graph Node Sign:
V1 V2 V3 V4
Input two vertices of the edges:
V1 V2
V3 V1
V1 V3
V4 V1
V3 V4
V4 V3
V4 V2
----------------Output Graph Information-----------------
Graph Kind: undirected graph
Vextices number: 4   Arcs number: 7

----------------Vextices Vector Information----------------
The Nodes Path:
Out path: V1-<-[1]->-V2  V1-<-[1]->-V3  V1-<-[1]->-V4
V1  Vextice Degree: 3

Out path: V2-<-[1]->-V1  V2-<-[1]->-V4
V2  Vextice Degree: 2

Out path: V3-<-[1]->-V1  V3-<-[1]->-V4
V3  Vextice Degree: 2

Out path: V4-<-[1]->-V1  V4-<-[1]->-V3  V4-<-[1]->-V2
V4  Vextice Degree: 3
*/

三、图的十字链表表示——（Orthogonal List）

本节实现对图的十字链表表示（主要用于有向图的存储），其中对无向图/网没有实现判重的功能，即不允许无向图/网先后输入同一条弧；

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
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
//----------------有向图的十字链表存储表示------------------//
#define Max_Vertex_Num 20
#define MAX_Length_Info 10
#define inp(i,x,y) for(i=x;i<=y;i++)
#define dep(i,x,y) for(i=x;i>=y;i--)
#define InfoType char*
#define VertexType string
#define Status bool
typedef enum { DG, DN, UDG, UDN }GraphKind;    //{有向图，有向网，无向图，无向网}

//---------------图的弧结构表示------------------//
typedef struct ArcBox {
    int tailvex, headvex, weight;  // 该弧的尾和头顶点的位置==>指向顺序存储结构中的编号
    struct ArcBox* hlink, * tlink; // 分别为弧头相同和弧尾相同的弧的链域
    // 对每一个节点而言，弧头相同的节点和弧尾相同的节点指向两个链表构成十字链表分别表示入度和出度
    InfoType info;        // 弧信息
}ArcBox;
//---------------图的顶点结构表示-----------------//
typedef struct VexNode {
    VertexType data;
    ArcBox* firstin, * firstout;  // 分别指向该顶点第一条入弧和出弧
    VexNode()
    {
        data = "";
        firstin = firstout = NULL;
    }
}VexNode, Xlist[Max_Vertex_Num];
typedef struct {
    Xlist Vextices;    // 表头向量
    int kind, vexnum, arcnum, IncInfo;          //图种类表识，节点数和弧数，弧有无信息
}OLGraph;

int LocateVex(OLGraph G, VertexType v);
Status GraphAddNode(OLGraph& G, int p1, int p2, int w);
Status CreateDG(OLGraph& G);
Status CreateDN(OLGraph& G);
Status CreateUDG(OLGraph& G);
Status CreateUDN(OLGraph& G);
Status CreateGraph(OLGraph& G);
Status GraphPrint(OLGraph G);

int main()
{
    OLGraph G;
    CreateGraph(G);
    GraphPrint(G);
    return 0;
}
Status CreateGraph(OLGraph& G)
{
    cout << "Input the type of graph(0:DG,1:DN,2:UDG,3:UDN):\n";
    cin >> G.kind;      // 种类标识
    switch (G.kind) {
    case DG:return CreateDG(G);
    case DN:return CreateDN(G);
    case UDG:return CreateUDG(G);
    case UDN:return CreateUDN(G);
    default:return false;
    }
}
Status CreateDG(OLGraph& G)
{
    // 采用十字链表存储表示，构造有向图G(G.kind=DG)
    cout << "Input Vextices number, Arcs number and Incinformation(Yes:1,NO:0):\n";
    cin >> G.vexnum >> G.arcnum >> G.IncInfo;
    int i = 0;
    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) cin >> G.Vextices[i].data;      // 节点顶点值 
    cout << "Input two vertices of the edges:\n";
    inp(i, 0, G.arcnum - 1) {    // 输入各弧并构造十字链表
        VertexType v1, v2;
        cin >> v1 >> v2;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;

        GraphAddNode(G, p1, p2, 1);   // p1->p2
    }
    return true;
}
Status CreateDN(OLGraph& G)
{
    // 采用十字链表存储表示，构造有向网G(G.kind=DN)
    cout << "Input Vextices number, Arcs number and Incinformation(Yes:1,NO:0):\n";
    cin >> G.vexnum >> G.arcnum >> G.IncInfo;
    int i = 0;
    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) cin >> G.Vextices[i].data;      // 节点顶点值 
    cout << "Input two vertices and weight of the edges:\n";
    inp(i, 0, G.arcnum - 1) {    // 输入各弧并构造十字链表
        VertexType v1, v2;
        int w = 0;
        cin >> v1 >> v2 >> w;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;

        GraphAddNode(G, p1, p2, w);   // p1->p2
    }
    return true;
}
Status CreateUDG(OLGraph& G)
{
    // 采用十字链表存储表示，构造无向图G(G.kind=UDG)
    cout << "Input Vextices number, Arcs number and Incinformation(Yes:1,NO:0):\n";
    cin >> G.vexnum >> G.arcnum >> G.IncInfo;
    int i = 0;
    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) cin >> G.Vextices[i].data;      // 节点顶点值 
    cout << "Input two vertices of the edges:\n";
    inp(i, 0, G.arcnum - 1) {    // 输入各弧并构造十字链表
        VertexType v1, v2;
        cin >> v1 >> v2;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;
        GraphAddNode(G, p1, p2, 1);   // p1->p2
        GraphAddNode(G, p2, p1, 1);   // p2->p1
    }
    return true;
}
Status CreateUDN(OLGraph& G)
{
    // 采用十字链表存储表示，构造无向网G(G.kind=UDN)
    cout << "Input Vextices number, Arcs number and Incinformation(Yes:1,NO:0):\n";
    cin >> G.vexnum >> G.arcnum >> G.IncInfo;
    int i = 0;
    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) cin >> G.Vextices[i].data;      // 节点顶点值 
    cout << "Input two vertices and weight of the edges:\n";
    inp(i, 0, G.arcnum - 1) {    // 输入各弧并构造十字链表
        VertexType v1, v2;
        int w = 0;
        cin >> v1 >> v2 >> w;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;
        GraphAddNode(G, p1, p2, w);   // p1->p2
        GraphAddNode(G, p2, p1, w);   // p2->p1
    }
    return true;
}
Status GraphAddNode(OLGraph& G, int p1, int p2, int w)
{
    ArcBox* p = (ArcBox*)malloc(sizeof(ArcBox));  // 创建弧单元
    if (!p) return false;

    //十字链表——涉及两个链表的交接==>最终first指针会指向最后输入的一组数据
    *p = { p1, p2, w, G.Vextices[p2].firstin, G.Vextices[p1].firstout, NULL };  // 对弧节点赋值
    G.Vextices[p2].firstin = G.Vextices[p1].firstout = p;  // 完成在入弧和出弧链头的插入
    if (G.IncInfo) {
        p->info = (char*)malloc(MAX_Length_Info*sizeof(char));
        cout << "Input the arc information: ";
        cin >> p->info;
    }
    return true;
}
int LocateVex(OLGraph G, VertexType v)
{
    int i = 0;
    inp(i, 0, G.vexnum - 1) {
        if (G.Vextices[i].data == v)
            return i;
    }
    return -1;
}
Status GraphPrint(OLGraph G)
{
    cout << "----------------Output Graph Information-----------------\n";
    cout << "Graph Kind: ";
    switch (G.kind) {
    case DG:cout << "directed graph\n";  // diagraph
        break;
    case DN:cout << "directed nets\n";  // dianetwork
        break;
    case UDG:cout << "undirected graph\n";  //undiagraph
        break;
    case UDN:cout << "undirected nets\n";  //undianetwork
        break;
    default:return false;
    }
    cout << "Vextices number: " << G.vexnum << "   " << "Arcs number: " << G.arcnum << endl;
    int i = 0, j = 0;
    cout << endl << "----------------Vextices Vector Information----------------\n";
    cout << "The Nodes Path:\n";
    inp(i, 0, G.vexnum - 1) {
        ArcBox* p = G.Vextices[i].firstout;
        ArcBox* q = G.Vextices[i].firstin;
        int Outdegree = 0, Indegree = 0;
        cout << "Out path: ";
        while (p) {
            cout << G.Vextices[p->tailvex].data << "-[" << p->weight << "]->" << G.Vextices[p->headvex].data << "  ";
            p = p->tlink;
            Outdegree++;
        }
        cout << endl << "In path: ";
        while (q) {
            cout << G.Vextices[q->tailvex].data << "-[" << q->weight << "]->" << G.Vextices[q->headvex].data << "  ";
            q = q->hlink;
            Indegree++;
        }

        cout << endl << G.Vextices[i].data;
        cout << "  Vextice Degree: " << Outdegree + Indegree << "  Outdegree: " << Outdegree
            << "  Indegree: " << Indegree << endl;
        cout << endl;
    }
    return true;
}

给出一个算例演示：

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
//---------------Here is a directed graph demo-----------//
/*
Input the type of graph(0:DG,1:DN,2:UDG,3:UDN):
0
Input Vextices number, Arcs number and Incinformation(Yes:1,NO:0):
4 7 0
Input Graph Node Sign:
V1 V2 V3 V4
Input two vertices of the edges:
V1 V2
V3 V1
V1 V3
V4 V1
V3 V4
V4 V3
V4 V2
----------------Output Graph Information-----------------
Graph Kind: directed graph
Vextices number: 4   Arcs number: 7

----------------Vextices Vector Information----------------
The Nodes Path:
Out path: V1-[1]->V3  V1-[1]->V2
In path: V4-[1]->V1  V3-[1]->V1
V1  Vextice Degree: 4  Outdegree: 2  Indegree: 2

Out path:
In path: V4-[1]->V2  V1-[1]->V2
V2  Vextice Degree: 2  Outdegree: 0  Indegree: 2

Out path: V3-[1]->V4  V3-[1]->V1
In path: V4-[1]->V3  V1-[1]->V3
V3  Vextice Degree: 4  Outdegree: 2  Indegree: 2

Out path: V4-[1]->V2  V4-[1]->V3  V4-[1]->V1
In path: V3-[1]->V4
V4  Vextice Degree: 4  Outdegree: 3  Indegree: 1
*/
//-------------------Here is a directed net demo--------------//
/*
Input the type of graph(0:DG,1:DN,2:UDG,3:UDN):
1
Input Vextices number, Arcs number and Incinformation(Yes:1,NO:0):
6 10 0
Input Graph Node Sign:
v1 v2 v3 v4 v5 v6
Input two vertices and weight of the edges:
v1 v2 5
v1 v4 7
v2 v3 4
v3 v1 8
v3 v6 9
v4 v3 5
v4 v6 6
v5 v4 5
v6 v1 3
v6 v5 1
----------------Output Graph Information-----------------
Graph Kind: directed nets
Vextices number: 6   Arcs number: 10

----------------Vextices Vector Information----------------
The Nodes Path:
Out path: v1-[7]->v4  v1-[5]->v2
In path: v6-[3]->v1  v3-[8]->v1
v1  Vextice Degree: 4  Outdegree: 2  Indegree: 2

Out path: v2-[4]->v3
In path: v1-[5]->v2
v2  Vextice Degree: 2  Outdegree: 1  Indegree: 1

Out path: v3-[9]->v6  v3-[8]->v1
In path: v4-[5]->v3  v2-[4]->v3
v3  Vextice Degree: 4  Outdegree: 2  Indegree: 2

Out path: v4-[6]->v6  v4-[5]->v3
In path: v5-[5]->v4  v1-[7]->v4
v4  Vextice Degree: 4  Outdegree: 2  Indegree: 2

Out path: v5-[5]->v4
In path: v6-[1]->v5
v5  Vextice Degree: 2  Outdegree: 1  Indegree: 1

Out path: v6-[1]->v5  v6-[3]->v1
In path: v4-[6]->v6  v3-[9]->v6
v6  Vextice Degree: 4  Outdegree: 2  Indegree: 2
*/
//---------------Here is a undirected graph demo-----------//
/*
Input the type of graph(0:DG,1:DN,2:UDG,3:UDN):
2
Input Vextices number, Arcs number and Incinformation(Yes:1,NO:0):
7 6 0
Input Graph Node Sign:
A B C D E F G
Input two vertices of the edges:
A C
A F
A D
B E
G E
E D
----------------Output Graph Information-----------------
Graph Kind: undirected graph
Vextices number: 7   Arcs number: 6

----------------Vextices Vector Information----------------
The Nodes Path:
Out path: A-[1]->D  A-[1]->F  A-[1]->C
In path: D-[1]->A  F-[1]->A  C-[1]->A
A  Vextice Degree: 6  Outdegree: 3  Indegree: 3

Out path: B-[1]->E
In path: E-[1]->B
B  Vextice Degree: 2  Outdegree: 1  Indegree: 1

Out path: C-[1]->A
In path: A-[1]->C
C  Vextice Degree: 2  Outdegree: 1  Indegree: 1

Out path: D-[1]->E  D-[1]->A
In path: E-[1]->D  A-[1]->D
D  Vextice Degree: 4  Outdegree: 2  Indegree: 2

Out path: E-[1]->D  E-[1]->G  E-[1]->B
In path: D-[1]->E  G-[1]->E  B-[1]->E
E  Vextice Degree: 6  Outdegree: 3  Indegree: 3

Out path: F-[1]->A
In path: A-[1]->F
F  Vextice Degree: 2  Outdegree: 1  Indegree: 1

Out path: G-[1]->E
In path: E-[1]->G
G  Vextice Degree: 2  Outdegree: 1  Indegree: 1
*/

四、无向图的邻接多重表表示——（Adjacency Multilist)

本节介绍无向图的另一种链式存储结构——邻接多重表，这类存储结构对已被搜索过的边做记号或删除一条表尤为方便；
由于采用将边存储为一个节点，以边的两个端点是否依附于该条边作为存储关系，故对有向图而言忽略了边的方向，不过结构与十字链表类似，因此此结构主要用于无向图；

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
#include<iostream>
#include<string>
using namespace std;
//--------------------无向图的邻接多重表存储表示-----------------//
#define Max_Vertex_Num 20
#define MAX_Length_Info 10
#define InfoType char
#define VertexType string
#define inp(i,x,y) for(i=x;i<=y;i++)
#define Status bool

typedef enum{unvisited, visited}VisitIf;
typedef enum {UDG, UDN }GraphKind;    //{无向图，无向网}
//------------------边结构定义--------------//
typedef struct EBox{
    VisitIf mark;     // 访问标记
    int ivex, jvex, weight;     // 该边依附的两个顶点位置
    struct EBox *ilink, *jlink;   // 分别指向依附这两个顶点的下一条边
    InfoType *info;    // 该边信息指针  
}EBox;
//------------------顶点结构定义--------------//
typedef struct VexBox{
    VertexType data;     // 节点数据域
    EBox *firstedge;  //指向第一条依附该顶点的边
    VexBox()
    {
        data = "";
        firstedge = NULL;
    }
}VexBox, AMList[Max_Vertex_Num];
//-------------------图结构定义---------------//
typedef struct{
    AMList adjmulist;
    int vexnum, arcnum, kind, IncInfo;     // 无向图的顶点数和边数
}AMLGraph;

int LocateVex(AMLGraph G, VertexType v);
Status GraphAddNode(AMLGraph& G, int p1, int p2, int w);
Status CreateGraph(AMLGraph &G);
Status CreateUDG(AMLGraph &G);
Status CreateUDN(AMLGraph &G);
Status GraphPrint(AMLGraph G);

int main()
{
    AMLGraph G;
    CreateGraph(G);
    GraphPrint(G);
    return 0;
}
Status CreateGraph(AMLGraph &G)
{
    cout << "Input the type of graph(0:UDG,1:UDN):\n";
    cin >> G.kind;      // 种类标识
    switch(G.kind){
        case UDG:return CreateUDG(G);
        case UDN:return CreateUDN(G);
        default:return false;
    }
}
Status CreateUDG(AMLGraph &G)
{
    // 采用邻接多重表存储表示，构造无向图G(G.kind=UDG)
    cout << "Input Vextices number, Arcs number and Incinformation(Yes:1,NO:0):\n";
    cin >> G.vexnum >> G.arcnum >> G.IncInfo;
    int i = 0;
    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) cin >> G.adjmulist[i].data;      // 节点顶点值 
    cout << "Input two vertices of the edges:\n";
    inp(i, 0, G.arcnum - 1) {    // 输入各弧并构造十字链表
        VertexType v1, v2;
        cin >> v1 >> v2;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;
    
        // 由于以边为单元，对两个节点的firstedge都做修改因此只需一次添加即可
        GraphAddNode(G, p1, p2, 1);   // p1<->p2
    }
    return true;
}
Status CreateUDN(AMLGraph &G)
{
    // 采用邻接多重表存储表示，构造无向网G(G.kind=UDN)
    cout << "Input Vextices number, Arcs number and Incinformation(Yes:1,NO:0):\n";
    cin >> G.vexnum >> G.arcnum >> G.IncInfo;
    int i = 0;
    cout << "Input Graph Node Sign:\n";
    inp(i, 0, G.vexnum - 1) cin >> G.adjmulist[i].data;      // 节点顶点值 
    cout << "Input two vertices of the edges:\n";
    inp(i, 0, G.arcnum - 1) {    // 输入各弧并构造十字链表
        VertexType v1, v2;
        int w = 0;
        cin >> v1 >> v2 >> w;     // 输入一条边的顶点
        int p1 = LocateVex(G, v1), p2 = LocateVex(G, v2);
        if (p1 == -1 || p2 == -1) return false;
    
        // 由于以边为单元，对两个节点的firstedge都做修改因此只需一次添加即可
        GraphAddNode(G, p1, p2, w);   // p1<->p2
    }
    return true;
}
int LocateVex(AMLGraph G, VertexType v)
{
    int i = 0;
    inp(i, 0, G.vexnum - 1) {
        if (G.adjmulist[i].data == v)
            return i;
    }
    return -1;
}
Status GraphAddNode(AMLGraph& G, int p1, int p2, int w)
{
    EBox* p = (EBox*)malloc(sizeof(EBox));  // 创建边单元
    if (!p) return false;

    //邻接多重表——涉及两个链表的交接==>最终firstedge指针会指向最后输入的一组数据
    *p = {unvisited, p1, p2, w, G.adjmulist[p1].firstedge, G.adjmulist[p2].firstedge, NULL };  // 对弧节点赋值
         //{mark, ivex, jvex, weight, *ilink, *jlink, *info}
    G.adjmulist[p1].firstedge = G.adjmulist[p2].firstedge = p; // 完成在入弧和出弧链头的插入
    if (G.IncInfo) {
        p->info = (char*)malloc(MAX_Length_Info*sizeof(char));
        cout << "Input the arc information: ";
        cin >> p->info;
    }
    return true;
}
Status GraphPrint(AMLGraph G)
{
    cout << "----------------Output Graph Information-----------------\n";
    cout << "Graph Kind: ";
    switch (G.kind) {
    case UDG:cout << "undirected graph\n";  //undiagraph
        break;
    case UDN:cout << "undirected nets\n";  //undianetwork
        break;
    default:return false;
    }
    cout << "Vextices number: " << G.vexnum << "   " << "Arcs number: " << G.arcnum << endl;
    int i = 0, j = 0;
    cout << endl << "----------------Vextices Vector Information----------------\n";
    cout << "The Nodes Path:\n";
    inp(i, 0, G.vexnum - 1) {
        EBox* p = G.adjmulist[i].firstedge;
        int Degree = 0, pos = 0;
        cout << "Paths: ";
        while (p) {
            pos = (p->ivex == i)?p->jvex:p->ivex;
            if(G.IncInfo)
                cout << G.adjmulist[i].data << p->info << "-<" << p->weight << ">-" << G.adjmulist[pos].data << "  ";
            else
                cout << G.adjmulist[i].data << "-<" << p->weight << ">-" << G.adjmulist[pos].data << "  ";
            p = (p->ivex == i)?p->ilink:p->jlink;
            Degree++;
        }
        cout << endl << G.adjmulist[i].data;
        cout << "  Vextice Degree: " << Degree << "  Outdegree: " << Degree<< "  Indegree: " << Degree << "\n\n";
    }
    return true;
}

这里给出一个算例演示：

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
//----------------Here is a undirected graph demo--------------//
/*
Input the type of graph(0:UDG,1:UDN):
0
Input Vextices number, Arcs number and Incinformation(Yes:1,NO:0):
7 6 0
Input Graph Node Sign:
A B C D E F G         
Input two vertices of the edges:
A C
A F
A D
B E
G E
E D
----------------Output Graph Information-----------------
Graph Kind: undirected graph
Vextices number: 7   Arcs number: 6

----------------Vextices Vector Information----------------
The Nodes Path:
Paths: A-<1>-D  A-<1>-F  A-<1>-C
A  Vextice Degree: 3  Outdegree: 3  Indegree: 3

Paths: B-<1>-E
B  Vextice Degree: 1  Outdegree: 1  Indegree: 1

Paths: C-<1>-A
C  Vextice Degree: 1  Outdegree: 1  Indegree: 1

Paths: D-<1>-E  D-<1>-A
D  Vextice Degree: 2  Outdegree: 2  Indegree: 2

Paths: E-<1>-D  E-<1>-G  E-<1>-B
E  Vextice Degree: 3  Outdegree: 3  Indegree: 3

Paths: F-<1>-A
F  Vextice Degree: 1  Outdegree: 1  Indegree: 1

Paths: G-<1>-E
G  Vextice Degree: 1  Outdegree: 1  Indegree: 1
*/
//----------------Here is a undrected net demo-----------------//
/*
Input the type of graph(0:UDG,1:UDN):
1
Input Vextices number, Arcs number and Incinformation(Yes:1,NO:0):
7 8 0   
Input Graph Node Sign:
A B C D E F G
Input two vertices and weight of the edges:
A C 4
A F -2
A D 4
B E -9
G E 7
E D 3
D B 1
G F 2
----------------Output Graph Information-----------------
Graph Kind: undirected nets
Vextices number: 7   Arcs number: 8

----------------Vextices Vector Information----------------
The Nodes Path:
Paths: A-<4>-D  A-<-2>-F  A-<4>-C
A  Vextice Degree: 3  Outdegree: 3  Indegree: 3

Paths: B-<1>-D  B-<-9>-E
B  Vextice Degree: 2  Outdegree: 2  Indegree: 2

Paths: C-<4>-A
C  Vextice Degree: 1  Outdegree: 1  Indegree: 1

Paths: D-<1>-B  D-<3>-E  D-<4>-A
D  Vextice Degree: 3  Outdegree: 3  Indegree: 3

Paths: E-<3>-D  E-<7>-G  E-<-9>-B
E  Vextice Degree: 3  Outdegree: 3  Indegree: 3

Paths: F-<2>-G  F-<-2>-A
F  Vextice Degree: 2  Outdegree: 2  Indegree: 2

Paths: G-<2>-F  G-<7>-E
G  Vextice Degree: 2  Outdegree: 2  Indegree: 2
*/

图的存储结构

https://markstiff.github.io/数据结构/图的存储表示/

作者

Mark Stiff

发布于

2022-10-28

更新于

2024-01-21

许可协议

 

喜欢这篇文章？打赏一下作者吧

评论

  关注我

分类

标签

Generative Model1
Latex3
Markdown1
二叉树1
人工智能1
体系结构1
图论2
字符串1
嵌入式2
嵌入式系统1
排序4
数字信号处理1
数学6
数据库系统1
数据结构16
数据结构与算法 - LeetCode1
概率论与数理统计 - 数学1
稀疏矩阵3
算法3
算法竞赛3
计算机原理4
软件工程1
×