16、【图】邻接矩阵有向图和邻接表有向图

一、邻接矩阵有向图的介绍

邻接矩阵有向图是指通过邻接矩阵表示的有向图。

上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了"<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<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，表示第1个顶点(即顶点B)到第2个顶点(C)是一条边。

二、邻接矩阵有向图的代码说明

1. 基本定义

 1 #define MAX 100
 2 
 3 class MatrixDG {
 4     private:
 5         char mVexs[MAX];    // 顶点集合
 6         int mVexNum;             // 顶点数
 7         int mEdgNum;             // 边数
 8         int mMatrix[MAX][MAX];   // 邻接矩阵
 9 
10     public:
11         // 创建图(自己输入数据)
12         MatrixDG();
13         // 创建图(用已提供的矩阵)
14         MatrixDG(char vexs[], int vlen, char edges[][2], int elen);
15         ~MatrixDG();
16 
17         // 打印矩阵队列图
18         void print();
19 
20     private:
21         // 读取一个输入字符
22         char readChar();
23         // 返回ch在mMatrix矩阵中的位置
24         int getPosition(char ch);
25 };

(1) ListDG是邻接表对应的结构体。 mVexNum是顶点数，mEdgNum是边数；mVexs则是保存顶点信息的一维数组。
(2) VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据，而firstEdge是该顶点所包含链表的表头指针。
(3) ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引，而nextEdge是指向下一个节点的。

2. 创建矩阵

这里介绍提供了两个创建矩阵的方法。一个是用已知数据，另一个则需要用户手动输入数据。

2.1 创建图(用已提供的矩阵)

/*
 * 创建图(用已提供的矩阵)
 *
 * 参数说明：
 *     vexs  -- 顶点数组
 *     vlen  -- 顶点数组的长度
 *     edges -- 边数组
 *     elen  -- 边数组的长度
 */
MatrixDG::MatrixDG(char vexs[], int vlen, char edges[][2], int elen)
{
    int i, p1, p2;

    // 初始化"顶点数"和"边数"
    mVexNum = vlen;
    mEdgNum = elen;
    // 初始化"顶点"
    for (i = 0; i < mVexNum; i++)
        mVexs[i] = vexs[i];

    // 初始化"边"
    for (i = 0; i < mEdgNum; i++)
    {
        // 读取边的起始顶点和结束顶点
        p1 = getPosition(edges[i][0]);
        p2 = getPosition(edges[i][1]);

        mMatrix[p1][p2] = 1;
    }
}

该函数的作用是创建一个邻接表有向图。实际上，该方法创建的有向图，就是上面的图G2。该函数的调用方法如下：

 1 char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
 2 char edges[][2] = {
 3     {'A', 'B'}, 
 4     {'B', 'C'}, 
 5     {'B', 'E'}, 
 6     {'B', 'F'}, 
 7     {'C', 'E'}, 
 8     {'D', 'C'}, 
 9     {'E', 'B'}, 
10     {'E', 'D'}, 
11     {'F', 'G'}}; 
12 int vlen = sizeof(vexs)/sizeof(vexs[0]);
13 int elen = sizeof(edges)/sizeof(edges[0]);
14 MatrixDG* pG;
15 
16 pG = new MatrixDG(vexs, vlen, edges, elen);

2.2 创建图(自己输入)

 1 /* 
 2  * 创建图(自己输入数据)
 3  */
 4 MatrixDG::MatrixDG()
 5 {
 6     char c1, c2;
 7     int i, p1, p2;
 8 
 9     // 输入"顶点数"和"边数"
10     cout << "input vertex number: ";
11     cin >> mVexNum;
12     cout << "input edge number: ";
13     cin >> mEdgNum;
14     if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1))))
15     {
16         cout << "input error: invalid parameters!" << endl;
17         return ;
18     }
19 
20     // 初始化"顶点"
21     for (i = 0; i < mVexNum; i++)
22     {
23         cout << "vertex(" << i << "): ";
24         mVexs[i] = readChar();
25     }
26 
27     // 初始化"边"
28     for (i = 0; i < mEdgNum; i++)
29     {
30         // 读取边的起始顶点和结束顶点
31         cout << "edge(" << i << "): ";
32         c1 = readChar();
33         c2 = readChar();
34 
35         p1 = getPosition(c1);
36         p2 = getPosition(c2);
37         if (p1==-1 || p2==-1)
38         {
39             cout << "input error: invalid edge!" << endl;
40             return ;
41         }
42 
43         mMatrix[p1][p2] = 1;
44     }
45 }

三、邻接矩阵有向图的C++实现

  1 /**
  2  * C++: 邻接矩阵图
  3  */
  4 
  5 #include <iomanip>
  6 #include <iostream>
  7 #include <vector>
  8 using namespace std;
  9 
 10 #define MAX 100
 11 class MatrixDG {
 12     private:
 13         char mVexs[MAX];    // 顶点集合
 14         int mVexNum;             // 顶点数
 15         int mEdgNum;             // 边数
 16         int mMatrix[MAX][MAX];   // 邻接矩阵
 17 
 18     public:
 19         // 创建图(自己输入数据)
 20         MatrixDG();
 21         // 创建图(用已提供的矩阵)
 22         MatrixDG(char vexs[], int vlen, char edges[][2], int elen);
 23         ~MatrixDG();
 24 
 25         // 打印矩阵队列图
 26         void print();
 27 
 28     private:
 29         // 读取一个输入字符
 30         char readChar();
 31         // 返回ch在mMatrix矩阵中的位置
 32         int getPosition(char ch);
 33 };
 34 
 35 /* 
 36  * 创建图(自己输入数据)
 37  */
 38 MatrixDG::MatrixDG()
 39 {
 40     char c1, c2;
 41     int i, p1, p2;
 42     
 43     // 输入"顶点数"和"边数"
 44     cout << "input vertex number: ";
 45     cin >> mVexNum;
 46     cout << "input edge number: ";
 47     cin >> mEdgNum;
 48     if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1))))
 49     {
 50         cout << "input error: invalid parameters!" << endl;
 51         return ;
 52     }
 53     
 54     // 初始化"顶点"
 55     for (i = 0; i < mVexNum; i++)
 56     {
 57         cout << "vertex(" << i << "): ";
 58         mVexs[i] = readChar();
 59     }
 60 
 61     // 初始化"边"
 62     for (i = 0; i < mEdgNum; i++)
 63     {
 64         // 读取边的起始顶点和结束顶点
 65         cout << "edge(" << i << "): ";
 66         c1 = readChar();
 67         c2 = readChar();
 68 
 69         p1 = getPosition(c1);
 70         p2 = getPosition(c2);
 71         if (p1==-1 || p2==-1)
 72         {
 73             cout << "input error: invalid edge!" << endl;
 74             return ;
 75         }
 76 
 77         mMatrix[p1][p2] = 1;
 78     }
 79 }
 80 
 81 /*
 82  * 创建图(用已提供的矩阵)
 83  *
 84  * 参数说明：
 85  *     vexs  -- 顶点数组
 86  *     vlen  -- 顶点数组的长度
 87  *     edges -- 边数组
 88  *     elen  -- 边数组的长度
 89  */
 90 MatrixDG::MatrixDG(char vexs[], int vlen, char edges[][2], int elen)
 91 {
 92     int i, p1, p2;
 93     
 94     // 初始化"顶点数"和"边数"
 95     mVexNum = vlen;
 96     mEdgNum = elen;
 97     // 初始化"顶点"
 98     for (i = 0; i < mVexNum; i++)
 99         mVexs[i] = vexs[i];
100 
101     // 初始化"边"
102     for (i = 0; i < mEdgNum; i++)
103     {
104         // 读取边的起始顶点和结束顶点
105         p1 = getPosition(edges[i][0]);
106         p2 = getPosition(edges[i][1]);
107 
108         mMatrix[p1][p2] = 1;
109     }
110 }
111 
112 /* 
113  * 析构函数
114  */
115 MatrixDG::~MatrixDG() 
116 {
117 }
118 
119 /*
120  * 返回ch在mMatrix矩阵中的位置
121  */
122 int MatrixDG::getPosition(char ch)
123 {
124     int i;
125     for(i=0; i<mVexNum; i++)
126         if(mVexs[i]==ch)
127             return i;
128     return -1;
129 }
130 
131 /*
132  * 读取一个输入字符
133  */
134 char MatrixDG::readChar()
135 {
136     char ch;
137 
138     do {
139         cin >> ch;
140     } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
141 
142     return ch;
143 }
144 
145 /*
146  * 打印矩阵队列图
147  */
148 void MatrixDG::print()
149 {
150     int i,j;
151 
152     cout << "Martix Graph:" << endl;
153     for (i = 0; i < mVexNum; i++)
154     {
155         for (j = 0; j < mVexNum; j++)
156             cout << mMatrix[i][j] << " ";
157         cout << endl;
158     }
159 }
160 
161 int main()
162 {
163     char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
164     char edges[][2] = {
165         {'A', 'B'}, 
166         {'B', 'C'}, 
167         {'B', 'E'}, 
168         {'B', 'F'}, 
169         {'C', 'E'}, 
170         {'D', 'C'}, 
171         {'E', 'B'}, 
172         {'E', 'D'}, 
173         {'F', 'G'}}; 
174     int vlen = sizeof(vexs)/sizeof(vexs[0]);
175     int elen = sizeof(edges)/sizeof(edges[0]);
176     MatrixDG* pG;
177 
178     // 自定义"图"(输入矩阵队列)
179     //pG = new MatrixDG();
180     // 采用已有的"图"
181     pG = new MatrixDG(vexs, vlen, edges, elen);
182 
183     pG->print();   // 打印图
184 
185     return 0;
186 }

四、邻接表有向图的介绍

邻接表有向图是指通过邻接表表示的有向图。