有向图的邻接矩阵与邻接表详细实现_有向图的邻接表

有向图的邻接矩阵

通过邻接矩阵来表示有向图。如下如所示：

上面的有向图G2包含了“A, B, C, D, E, F, G”共7个顶点，而且包含了“<A, B>, <B, C>, <B, E>, <B, F>, <C, F>, <D, C>, <E, B>, <E, D>, <F, G>”共9条边。

上图中右边的矩阵是有向图G2的邻接矩阵示意图。A[i][j] = 1表示第i个顶点到第j个顶点是一条边，A[i][j] = 0则表示不是一条边，而A[i][j]表示的是第i行第j列的值。例如，A[1][2] = 1表示的是顶点B到顶点C是一条边。

代码实现

#include <iostream>
#include <vector>
using namespace std;

#define MAX 100

class MatrixDG
{
private:
    char mVexs[MAX];       //顶点集合
    int mVexNum;           //顶点数
    int mEdgNum;           //边数
    int mMatrix[MAX][MAX]; //邻接矩阵
public:
    //创建图(手动输入)
    MatrixDG();
    //创建图(用提供的顶点和边)
    MatrixDG(char *vexs, int vNum, char (*edges)[2], int eNum);
    ~MatrixDG();
    void print();
    char readChar();
    int getPosition(char ch);
};

MatrixDG::MatrixDG()
{
    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;
    }
}

MatrixDG::MatrixDG(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;
    }
}

MatrixDG::~MatrixDG()
{
}

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

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

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

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

输入顶点数:7
输入边数：9
vertex(0):A
vertex(1):B
vertex(2):C
vertex(3):D
vertex(4):E
vertex(5):F
vertex(6):G
edge(0):AB
edge(1):BC
edge(2):BE
edge(3):BF
edge(4):CE
edge(5):DC
edge(6):EB
edge(7):ED
edge(8):FG
0 1 0 0 0 0 0 
0 0 1 0 1 1 0 
0 0 0 0 1 0 0 
0 0 1 0 0 0 0 
0 1 0 1 0 0 0 
0 0 0 0 0 0 1 
0 0 0 0 0 0 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

有向图的邻接表

通过邻接表来表示有向图。如下如所示：

上面的有向图G2包含了“A, B, C, D, E, F, G”共7个顶点，而且包含了“<A, B>, <B, C>, <B, E>, <B, F>, <C, F>, <D, C>, <E, B>, <E, D>, <F, G>”共9条边。

上图中右边的邻接表是有向图G2的邻接表示意图。每个顶点都包含一条链表，该链表记录了“该顶点所对应的出边的另一个顶点的序号”。例如，第1个顶点B包含的链表所包含的节点的数据分别是“2, 4, 5”，而这“2, 4, 5”分别对应“C, E, F”的序号，“C, E, F”都属于B的出边的另一个顶点。

代码实现

#include <iostream>
using namespace std;

#define MAX 100

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

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

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

ListDG::ListDG()
{
    char c1, c2;
    int p1, p2;
    ENode *node1;
    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);
    }
}

ListDG::ListDG(char *vexs, int vNum, char (*edges)[2], int eNum)
{
    if (vNum > MAX || eNum > MAX)
        return;
    char c1, c2;
    int p1, p2;
    ENode *node1;
    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);
    }
}

ListDG::~ListDG() {}

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

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

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

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

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

输入顶点数:7
输入边数:9
vertex(0):A
vertex(1):B
vertex(2):C
vertex(3):D
vertex(4):E
vertex(5):F
vertex(6):G
edge(0):AB
edge(1):BC
edge(2):BE
edge(3):BF
edge(4):CE
edge(5):DC
edge(6):EB
edge(7):ED
edge(8):FG
0(A):1(B)
1(B):2(C)4(E)5(F)
2(C):4(E)
3(D):2(C)
4(E):1(B)3(D)
5(F):6(G)
6(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