无向图的邻接矩阵与邻接表详细实现_无向图的邻接矩阵和邻接表怎么画

作者：从前慢现在也慢 | 2024-03-16 01:07:22

踩

无向图的邻接矩阵和邻接表怎么画

无向图的邻接矩阵

通过用邻接矩阵来表示无向图。如下无向图G1的邻接矩阵：

无向图G1的邻接矩阵

无向图G1包含了“A, B, C, D, E, F, G”共七个顶点，而且包含了“(A, C), (A, D), (A, F), (B, C), (C, D), (E, G), (F, G)”共七条边。由于这是无向图，所以(A, C)和(C, A)是同一条边，这里列举边时，按照字母先后顺序列举的。

无向图G1右边的邻接矩阵在内存中的邻接矩阵示意图。A[i][j] = 1表示第i个顶点与第j个顶点是邻接点，A[i][j] = 0表示它们不是邻接点。而i, j表示第i行和第j列的值。如：A[1, 2] = 1 表示第1个顶点B和第二个顶点C是邻接点。

代码实现

#include <iostream>
using namespace std;

#define MAX 100

class MatrixUDG
{
private:
    char mVexs[MAX];       //顶点集合
    int mVexNum;           //顶点数
    int mEdgNum;           //边数
    int mMatrix[MAX][MAX]; //邻接矩阵
public:
    //创建图(手动输入)
    MatrixUDG();
    //创建图(用提供的顶点和边)
    MatrixUDG(char *vexs, int vNum, char (*edges)[2], int eNum);
    ~MatrixUDG();
    //打印邻接表
    void print();
    //输入一个合法字母
    char readChar();
    //获得一个字母在顶点数组的下标
    int getPosition(char ch);
};

MatrixUDG::MatrixUDG()
{
    char c1, c2;
    int p1, p2;
    cout << "输入顶点数:";
    cin >> mVexNum;
    cout << "输入边数：";
    cin >> mEdgNum;
    if (mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum - 1))))
    {
        cout << "输入有误！" << endl;
        return;
    }
    for (int i = 0; i < mVexNum; ++i)
    {
        cout << "vertex(" << i << "):";
        mVexs[i] = readChar();
    }
    for (int j = 0; j < mEdgNum; ++j)
    {
        cout << "edge(" << j << "):";
        c1 = readChar();
        c2 = readChar();
        p1 = getPosition(c1);
        p2 = getPosition(c2);
        if (p1 == -1 || p2 == -1)
        {
            cout << "输入的边错误！" << endl;
            return;
        }
        mMatrix[p1][p2] = 1;
        mMatrix[p2][p1] = 1;
    }
}

MatrixUDG::MatrixUDG(char *vexs, int vNum, char (*edges)[2], int eNum)
{
    if (vNum > MAX)
        return;
    mVexNum = vNum;
    mEdgNum = eNum;
    //初始化顶点
    for (int i = 0; i < mVexNum; ++i)
        mVexs[i] = vexs[i];
    int p1, p2;
    for (int j = 0; j < mEdgNum; ++j)
    {
        //获得边的起始点和结束点
        p1 = getPosition(edges[j][0]);
        p2 = getPosition(edges[j][1]);
        //将连线的两个点都置为1
        if (p1 == -1 || p2 == -1)
        {
            cout << "输入的边错误！" << endl;
            return;
        }
        mMatrix[p1][p2] = 1;
        mMatrix[p2][p1] = 1;
    }
}

MatrixUDG::~MatrixUDG()
{
}

int MatrixUDG::getPosition(char ch)
{
    for (int i = 0; i < mVexNum; ++i)
    {
        if (mVexs[i] == ch)
            return i;
    }
    return -1;
}

char MatrixUDG::readChar()
{
    char ch;
    do
    {
        cin >> ch;
    } while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));
    return ch;
}

void MatrixUDG::print()
{
    for (int i = 0; i < mVexNum; ++i)
    {
        for (int j = 0; j < mVexNum; ++j)
        {
            cout << mMatrix[i][j] << " ";
        }
        cout << endl;
    }
}

int main()
{
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char edges[][2] = {
        {'A', 'C'},
        {'A', 'D'},
        {'A', 'F'},
        {'B', 'C'},
        {'C', 'D'},
        {'E', 'G'},
        {'F', 'G'}
    };
    int vNum = sizeof(vexs) / sizeof(vexs[0]);
    int eNum = sizeof(edges) / sizeof(edges[0]);
    //1. 根据提供的数据生成
//  MatrixUDG mudg(vexs, vNum, edges, eNum);
//  mudg.print();
    //2. 手动生成
    MatrixUDG mudg1;
    mudg1.print();
}
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

手动输入时运行结果如下：

输入顶点数:7
输入边数：7
vertex(0):A
vertex(1):B
vertex(2):C
vertex(3):D
vertex(4):E
vertex(5):F
vertex(6):G
edge(0):AC
edge(1):AD
edge(2):AF
edge(3):BC
edge(4):CD
edge(5):EG
edge(6):FG
0 0 1 1 0 1 0 
0 0 1 0 0 0 0 
1 1 0 1 0 0 0 
1 0 1 0 0 0 0 
0 0 0 0 0 0 1 
1 0 0 0 0 0 1 
0 0 0 0 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

无向图的邻接表

通过用邻接表来表示无向图。如下无向图G1的邻接表：

无向图G1的邻接表

无向图G1包含了“A, B, C, D, E, F, G”共七个顶点，而且包含了“(A, C), (A, D), (A, F), (B, C), (C, D), (E, G), (F, G)”共七条边。

无向图G1右边的邻接表示意图如上图。每个顶点都包含一个链表，该链表记录了“该顶点的邻接点的序号”。顶点C包含的链表所包含的数据分别是“0、1、3”，而“0、1、3”分别对应“A、B、D”的序号，“A、B、D”都是C的邻接点。就是通过这种方式记录图的信息的。

代码实现

#include <iostream>
using namespace std;

#define MAX 100

class ListUDG
{
private:
    //每一条边
    struct ENode
    {
        int iVex;               //指向的顶点的位置
        ENode *nextEdge = NULL; //指向顶点的下一条边的指针
    };
    //数组中存储的顶点
    struct VNode
    {
        char data;
        ENode *firstEdge = NULL; //指向第一条该顶点的边
    };

private:
    int mVexNum;      //图的顶点数目
    int mEdgeNum;     //图的边的数目
    VNode mVexs[MAX]; //存储顶点
public:
    ListUDG();
    ListUDG(char vexs[], int vNum, char edges[][2], int eNum);
    ~ListUDG();
    //打印邻接表
    void print();

private:
    //读取一个合法的输入字符
    char readChar();
    //返回字符ch在的位置
    int getPosition(char ch);
    //将node结点链接到list的最后
    void linkLast(ENode *list, ENode *node);
};

ListUDG::ListUDG()
{
    char c1, c2;
    int p1, p2;
    ENode *node1, *node2;
    cout << "输入顶点数:";
    cin >> mVexNum;
    cout << "输入边数:";
    cin >> mEdgeNum;
    if (mVexNum > MAX || mEdgeNum > MAX || mVexNum < 1 || mEdgeNum < 1 || (mEdgeNum > (mVexNum * (mVexNum - 1))))
    {
        cout << "输入有误！" << endl;
        return;
    }
    for (int i = 0; i < mVexNum; ++i)
    {
        cout << "vertex(" << i << "):";
        mVexs[i].data = readChar();
    }
    //初始化邻接表的边
    for (int j = 0; j < mEdgeNum; ++j)
    {
        cout << "edge(" << j << "):";
        c1 = readChar();
        c2 = readChar();
        p1 = getPosition(c1);
        p2 = getPosition(c2);
        if (p1 == -1 || p2 == -1)
        {
            cout << "输入的边有错误！" << endl;
            return;
        }

        node1 = new ENode();
        node1->iVex = p2;
        if (mVexs[p1].firstEdge == NULL)
            mVexs[p1].firstEdge = node1;
        else
            linkLast(mVexs[p1].firstEdge, node1);
        node2 = new ENode();
        node2->iVex = p1;
        if (mVexs[p2].firstEdge == NULL)
            mVexs[p2].firstEdge = node2;
        else
            linkLast(mVexs[p2].firstEdge, node2);
    }
}

ListUDG::ListUDG(char *vexs, int vNum, char (*edges)[2], int eNum)
{
    if (vNum > MAX || eNum > MAX)
        return;
    char c1, c2;
    int p1, p2;
    ENode *node1, *node2;
    mVexNum = vNum;
    mEdgeNum = eNum;
    for (int i = 0; i < mVexNum; ++i)
    {
        mVexs[i].data = vexs[i];
    }
    for (int j = 0; j < mEdgeNum; ++j)
    {
        c1 = edges[j][0];
        c2 = edges[j][1];
        p1 = getPosition(c1);
        p2 = getPosition(c2);
        if (p1 == -1 || p2 == -1)
        {
            cout << "输入的边有错误！" << endl;
            return;
        }
        node1 = new ENode();
        node1->iVex = p2;
        if (mVexs[p1].firstEdge == NULL)
            mVexs[p1].firstEdge = node1;
        else
            linkLast(mVexs[p1].firstEdge, node1);
        node2 = new ENode();
        node2->iVex = p1;
        if (mVexs[p2].firstEdge == NULL)
            mVexs[p2].firstEdge = node2;
        else
            linkLast(mVexs[p2].firstEdge, node2);
    }
}

ListUDG::~ListUDG() {}

void ListUDG::linkLast(ENode *list, ENode *node)
{
    ENode *p = list;
    while (p->nextEdge)
        p = p->nextEdge;
    p->nextEdge = node;
}

int ListUDG::getPosition(char ch)
{
    for (int i = 0; i < mVexNum; ++i)
    {
        if (mVexs[i].data == ch)
            return i;
    }
    return -1;
}

char ListUDG::readChar()
{
    char ch;
    do
    {
        cin >> ch;
    } while (!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));
    return ch;
}

void ListUDG::print()
{
    ENode *node;
    for (int i = 0; i < mVexNum; ++i)
    {
        cout << i << "(" << mVexs[i].data << "):";
        node = mVexs[i].firstEdge;
        while (node != NULL)
        {
            cout << node->iVex << "(" << mVexs[node->iVex].data << ")";
            node = node->nextEdge;
        }
        cout << endl;
    }
}

int main(int argc, char **argv)
{
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char edges[][2] = {
        {'A', 'C'},
        {'A', 'D'},
        {'A', 'F'},
        {'B', 'C'},
        {'C', 'D'},
        {'E', 'G'},
        {'F', 'G'}
    };
    int vNum = sizeof(vexs) / sizeof(vexs[0]);
    int eNum = sizeof(edges) / sizeof(edges[0]);
    //1. 根据提供的数据生成
//  ListUDG ludg(vexs, vNum, edges, eNum);
//  ludg.print();
    //2. 手动输入
    ListUDG ludg;
    ludg.print();
    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

手动输入时运行结果如下：

输入顶点数:7
输入边数:7
vertex(0):A
vertex(1):B
vertex(2):C 
vertex(3):D
vertex(4):E
vertex(5):F
vertex(6):G
edge(0):AC
edge(1):AD
edge(2):AF
edge(3):BC
edge(4):CD
edge(5):EG
edge(6):FG
0(A):2(C)3(D)5(F)
1(B):2(C)
2(C):0(A)1(B)3(D)
3(D):0(A)2(C)
4(E):6(G)
5(F):0(A)6(G)
6(G):4(E)5(F)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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