15、【图】邻接矩阵无向图和邻接表无向图

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

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

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

上图右边的矩阵是G1在内存中的邻接矩阵示意图。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 class MatrixUDG {
 2     private:
 3         char mVexs[MAX];    // 顶点集合
 4         int mVexNum;             // 顶点数
 5         int mEdgNum;             // 边数
 6         int mMatrix[MAX][MAX];   // 邻接矩阵
 7 
 8     public:
 9         // 创建图(自己输入数据)
10         MatrixUDG();
11         // 创建图(用已提供的矩阵)
12         MatrixUDG(char vexs[], int vlen, char edges[][2], int elen);
13         ~MatrixUDG();
14 
15         // 打印矩阵队列图
16         void print();
17 
18     private:
19         // 读取一个输入字符
20         char readChar();
21         // 返回ch在mMatrix矩阵中的位置
22         int getPosition(char ch);
23 };

MatrixUDG是邻接矩阵对应的结构体。
mVexs用于保存顶点，mVexNum是顶点数，mEdgNum是边数；mMatrix则是用于保存矩阵信息的二维数组。例如，mMatrix[i][j]=1，则表示"顶点i(即mVexs[i])"和"顶点j(即mVexs[j])"是邻接点；mMatrix[i][j]=0，则表示它们不是邻接点。

2. 创建矩阵

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

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

 1 /*
 2  * 创建图(用已提供的矩阵)
 3  *
 4  * 参数说明：
 5  *     vexs  -- 顶点数组
 6  *     vlen  -- 顶点数组的长度
 7  *     edges -- 边数组
 8  *     elen  -- 边数组的长度
 9  */
10 MatrixUDG::MatrixUDG(char vexs[], int vlen, char edges[][2], int elen)
11 {
12     int i, p1, p2;
13 
14     // 初始化"顶点数"和"边数"
15     mVexNum = vlen;
16     mEdgNum = elen;
17     // 初始化"顶点"
18     for (i = 0; i < mVexNum; i++)
19         mVexs[i] = vexs[i];
20 
21     // 初始化"边"
22     for (i = 0; i < mEdgNum; i++)
23     {
24         // 读取边的起始顶点和结束顶点
25         p1 = getPosition(edges[i][0]);
26         p2 = getPosition(edges[i][1]);
27 
28         mMatrix[p1][p2] = 1;
29         mMatrix[p2][p1] = 1;
30     }
31 }

该函数的作用是利用已知数据来创建一个邻接矩阵无向图。实际上，在本文的测试程序源码中，该方法创建的无向图就是上面图G1。具体的调用代码如下：

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

2.2 创建图(自己输入)

 1 /* 
 2  * 创建图(自己输入数据)
 3  */
 4 MatrixUDG::MatrixUDG()
 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         mMatrix[p2][p1] = 1;
45     }
46 }

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

  1 /**
  2  * C++: 邻接矩阵表示的"无向图(List Undirected Graph)"
  3  */
  4 
  5 #include <iomanip>
  6 #include <iostream>
  7 #include <vector>
  8 using namespace std;
  9 
 10 #define MAX 100
 11 class MatrixUDG {
 12     private:
 13         char mVexs[MAX];    // 顶点集合
 14         int mVexNum;             // 顶点数
 15         int mEdgNum;             // 边数
 16         int mMatrix[MAX][MAX];   // 邻接矩阵
 17 
 18     public:
 19         // 创建图(自己输入数据)
 20         MatrixUDG();
 21         // 创建图(用已提供的矩阵)
 22         MatrixUDG(char vexs[], int vlen, char edges[][2], int elen);
 23         ~MatrixUDG();
 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 MatrixUDG::MatrixUDG()
 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         mMatrix[p2][p1] = 1;
 79     }
 80 }
 81 
 82 /*
 83  * 创建图(用已提供的矩阵)
 84  *
 85  * 参数说明：
 86  *     vexs  -- 顶点数组
 87  *     vlen  -- 顶点数组的长度
 88  *     edges -- 边数组
 89  *     elen  -- 边数组的长度
 90  */
 91 MatrixUDG::MatrixUDG(char vexs[], int vlen, char edges[][2], int elen)
 92 {
 93     int i, p1, p2;
 94     
 95     // 初始化"顶点数"和"边数"
 96     mVexNum = vlen;
 97     mEdgNum = elen;
 98     // 初始化"顶点"
 99     for (i = 0; i < mVexNum; i++)
100         mVexs[i] = vexs[i];
101 
102     // 初始化"边"
103     for (i = 0; i < mEdgNum; i++)
104     {
105         // 读取边的起始顶点和结束顶点
106         p1 = getPosition(edges[i][0]);
107         p2 = getPosition(edges[i][1]);
108 
109         mMatrix[p1][p2] = 1;
110         mMatrix[p2][p1] = 1;
111     }
112 }
113 
114 /* 
115  * 析构函数
116  */
117 MatrixUDG::~MatrixUDG() 
118 {
119 }
120 
121 /*
122  * 返回ch在mMatrix矩阵中的位置
123  */
124 int MatrixUDG::getPosition(char ch)
125 {
126     int i;
127     for(i=0; i<mVexNum; i++)
128         if(mVexs[i]==ch)
129             return i;
130     return -1;
131 }
132 
133 /*
134  * 读取一个输入字符
135  */
136 char MatrixUDG::readChar()
137 {
138     char ch;
139 
140     do {
141         cin >> ch;
142     } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
143 
144     return ch;
145 }
146 
147 /*
148  * 打印矩阵队列图
149  */
150 void MatrixUDG::print()
151 {
152     int i,j;
153 
154     cout << "Martix Graph:" << endl;
155     for (i = 0; i < mVexNum; i++)
156     {
157         for (j = 0; j < mVexNum; j++)
158             cout << mMatrix[i][j] << " ";
159         cout << endl;
160     }
161 }
162 
163 int main()
164 {
165     char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
166     char edges[][2] = {
167         {'A', 'C'}, 
168         {'A', 'D'}, 
169         {'A', 'F'}, 
170         {'B', 'C'}, 
171         {'C', 'D'}, 
172         {'E', 'G'}, 
173         {'F', 'G'}};
174     int vlen = sizeof(vexs)/sizeof(vexs[0]);
175     int elen = sizeof(edges)/sizeof(edges[0]);
176     MatrixUDG* pG;
177 
178     // 自定义"图"(输入矩阵队列)
179     //pG = new MatrixUDG();
180     // 采用已有的"图"
181     pG = new MatrixUDG(vexs, vlen, edges, elen);
182 
183     pG->print();   // 打印图
184 
185     return 0;
186 }

四、邻接表无向图介绍

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

上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。

上图右边的矩阵是G1在内存中的邻接表示意图。每一个顶点都包含一条链表，该链表记录了"该顶点的邻接点的序号"。例如，第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3"；而这"0,1,3"分别对应"A,B,D"的序号，"A,B,D"都是C的邻接点。就是通过这种方式记录图的信息的。

五、邻接表无向图的代码说明

1. 基本定义

 1 #define MAX 100
 2 // 邻接表
 3 class ListUDG
 4 {
 5     private: // 内部类
 6         // 邻接表中表对应的链表的顶点
 7         class ENode
 8         {
 9             public:
10                 int ivex;           // 该边所指向的顶点的位置
11                 ENode *nextEdge;    // 指向下一条弧的指针
12         };
13 
14         // 邻接表中表的顶点
15         class VNode
16         {
17             public:
18                 char data;          // 顶点信息
19                 ENode *firstEdge;   // 指向第一条依附该顶点的弧
20         };
21 
22     private: // 私有成员
23         int mVexNum;             // 图的顶点的数目
24         int mEdgNum;             // 图的边的数目
25         VNode mVexs[MAX];
26 
27     public:
28         // 创建邻接表对应的图(自己输入)
29         ListUDG();
30         // 创建邻接表对应的图(用已提供的数据)
31         ListUDG(char vexs[], int vlen, char edges[][2], int elen);
32         ~ListUDG();
33 
34         // 打印邻接表图
35         void print();
36 
37     private:
38         // 读取一个输入字符
39         char readChar();
40         // 返回ch的位置
41         int getPosition(char ch);
42         // 将node节点链接到list的最后
43         void linkLast(ENode *list, ENode *node);
44 };

(1) ListUDG是邻接表对应的结构体。
mVexNum是顶点数，mEdgNum是边数；mVexs则是保存顶点信息的一维数组。

(2) VNode是邻接表顶点对应的结构体。
data是顶点所包含的数据，而firstEdge是该顶点所包含链表的表头指针。

(3) ENode是邻接表顶点所包含的链表的节点对应的结构体。
ivex是该节点所对应的顶点在vexs中的索引，而nextEdge是指向下一个节点的。

2. 创建矩阵

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

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

/*
 * 创建邻接表对应的图(用已提供的数据)
 */
ListUDG::ListUDG(char vexs[], int vlen, char edges[][2], int elen)
{
    char c1, c2;
    int i, p1, p2;
    ENode *node1, *node2;

    // 初始化"顶点数"和"边数"
    mVexNum = vlen;
    mEdgNum = elen;
    // 初始化"邻接表"的顶点
    for(i=0; i<mVexNum; i++)
    {
        mVexs[i].data = vexs[i];
        mVexs[i].firstEdge = NULL;
    }

    // 初始化"邻接表"的边
    for(i=0; i<mEdgNum; i++)
    {
        // 读取边的起始顶点和结束顶点
        c1 = edges[i][0];
        c2 = edges[i][1];

        p1 = getPosition(c1);
        p2 = getPosition(c2);
        // 初始化node1
        node1 = new ENode();
        node1->ivex = p2;
        // 将node1链接到"p1所在链表的末尾"
        if(mVexs[p1].firstEdge == NULL)
          mVexs[p1].firstEdge = node1;
        else
            linkLast(mVexs[p1].firstEdge, node1);
        // 初始化node2
        node2 = new ENode();
        node2->ivex = p1;
        // 将node2链接到"p2所在链表的末尾"
        if(mVexs[p2].firstEdge == NULL)
          mVexs[p2].firstEdge = node2;
        else
            linkLast(mVexs[p2].firstEdge, node2);
    }
}

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

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

2.2 创建图(自己输入)

 1 /*
 2  * 创建邻接表对应的图(自己输入)
 3  */
 4 ListUDG::ListUDG()
 5 {
 6     char c1, c2;
 7     int v, e;
 8     int i, p1, p2;
 9     ENode *node1, *node2;
10 
11     // 输入"顶点数"和"边数"
12     cout << "input vertex number: ";
13     cin >> mVexNum;
14     cout << "input edge number: ";
15     cin >> mEdgNum;
16     if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1))))
17     {
18         cout << "input error: invalid parameters!" << endl;
19         return ;
20     }
21 
22     // 初始化"邻接表"的顶点
23     for(i=0; i<mVexNum; i++)
24     {
25         cout << "vertex(" << i << "): ";
26         mVexs[i].data = readChar();
27         mVexs[i].firstEdge = NULL;
28     }
29 
30     // 初始化"邻接表"的边
31     for(i=0; i<mEdgNum; i++)
32     {
33         // 读取边的起始顶点和结束顶点
34         cout << "edge(" << i << "): ";
35         c1 = readChar();
36         c2 = readChar();
37 
38         p1 = getPosition(c1);
39         p2 = getPosition(c2);
40         // 初始化node1
41         node1 = new ENode();
42         node1->ivex = p2;
43         // 将node1链接到"p1所在链表的末尾"
44         if(mVexs[p1].firstEdge == NULL)
45           mVexs[p1].firstEdge = node1;
46         else
47             linkLast(mVexs[p1].firstEdge, node1);
48         // 初始化node2
49         node2 = new ENode();
50         node2->ivex = p1;
51         // 将node2链接到"p2所在链表的末尾"
52         if(mVexs[p2].firstEdge == NULL)
53           mVexs[p2].firstEdge = node2;
54         else
55             linkLast(mVexs[p2].firstEdge, node2);
56     }
57 }

该函数是读取用户的输入，将输入的数据转换成对应的无向图。

六、邻接表无向图的C++实现

  1 /**
  2  * C++: 邻接表表示的"无向图(List Undirected Graph)"  6  */
  7 
  8 #include <iomanip>
  9 #include <iostream>
 10 #include <vector>
 11 using namespace std;
 12 
 13 #define MAX 100
 14 // 邻接表
 15 class ListUDG
 16 {
 17     private: // 内部类
 18         // 邻接表中表对应的链表的顶点
 19         class ENode
 20         {
 21             public:
 22                 int ivex;           // 该边所指向的顶点的位置
 23                 ENode *nextEdge;    // 指向下一条弧的指针
 24         };
 25 
 26         // 邻接表中表的顶点
 27         class VNode
 28         {
 29             public:
 30                 char data;          // 顶点信息
 31                 ENode *firstEdge;   // 指向第一条依附该顶点的弧
 32         };
 33 
 34     private: // 私有成员
 35         int mVexNum;             // 图的顶点的数目
 36         int mEdgNum;             // 图的边的数目
 37         VNode mVexs[MAX];
 38 
 39     public:
 40         // 创建邻接表对应的图(自己输入)
 41         ListUDG();
 42         // 创建邻接表对应的图(用已提供的数据)
 43         ListUDG(char vexs[], int vlen, char edges[][2], int elen);
 44         ~ListUDG();
 45 
 46         // 打印邻接表图
 47         void print();
 48 
 49     private:
 50         // 读取一个输入字符
 51         char readChar();
 52         // 返回ch的位置
 53         int getPosition(char ch);
 54         // 将node节点链接到list的最后
 55         void linkLast(ENode *list, ENode *node);
 56 };
 57 
 58 /*
 59  * 创建邻接表对应的图(自己输入)
 60  */
 61 ListUDG::ListUDG()
 62 {
 63     char c1, c2;
 64     int v, e;
 65     int i, p1, p2;
 66     ENode *node1, *node2;
 67 
 68     // 输入"顶点数"和"边数"
 69     cout << "input vertex number: ";
 70     cin >> mVexNum;
 71     cout << "input edge number: ";
 72     cin >> mEdgNum;
 73     if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1))))
 74     {
 75         cout << "input error: invalid parameters!" << endl;
 76         return ;
 77     }
 78  
 79     // 初始化"邻接表"的顶点
 80     for(i=0; i<mVexNum; i++)
 81     {
 82         cout << "vertex(" << i << "): ";
 83         mVexs[i].data = readChar();
 84         mVexs[i].firstEdge = NULL;
 85     }
 86 
 87     // 初始化"邻接表"的边
 88     for(i=0; i<mEdgNum; i++)
 89     {
 90         // 读取边的起始顶点和结束顶点
 91         cout << "edge(" << i << "): ";
 92         c1 = readChar();
 93         c2 = readChar();
 94 
 95         p1 = getPosition(c1);
 96         p2 = getPosition(c2);
 97         // 初始化node1
 98         node1 = new ENode();
 99         node1->ivex = p2;
100         // 将node1链接到"p1所在链表的末尾"
101         if(mVexs[p1].firstEdge == NULL)
102           mVexs[p1].firstEdge = node1;
103         else
104             linkLast(mVexs[p1].firstEdge, node1);
105         // 初始化node2
106         node2 = new ENode();
107         node2->ivex = p1;
108         // 将node2链接到"p2所在链表的末尾"
109         if(mVexs[p2].firstEdge == NULL)
110           mVexs[p2].firstEdge = node2;
111         else
112             linkLast(mVexs[p2].firstEdge, node2);
113     }
114 }
115 
116 /*
117  * 创建邻接表对应的图(用已提供的数据)
118  */
119 ListUDG::ListUDG(char vexs[], int vlen, char edges[][2], int elen)
120 {
121     char c1, c2;
122     int i, p1, p2;
123     ENode *node1, *node2;
124 
125     // 初始化"顶点数"和"边数"
126     mVexNum = vlen;
127     mEdgNum = elen;
128     // 初始化"邻接表"的顶点
129     for(i=0; i<mVexNum; i++)
130     {
131         mVexs[i].data = vexs[i];
132         mVexs[i].firstEdge = NULL;
133     }
134 
135     // 初始化"邻接表"的边
136     for(i=0; i<mEdgNum; i++)
137     {
138         // 读取边的起始顶点和结束顶点
139         c1 = edges[i][0];
140         c2 = edges[i][1];
141 
142         p1 = getPosition(c1);
143         p2 = getPosition(c2);
144         // 初始化node1
145         node1 = new ENode();
146         node1->ivex = p2;
147         // 将node1链接到"p1所在链表的末尾"
148         if(mVexs[p1].firstEdge == NULL)
149           mVexs[p1].firstEdge = node1;
150         else
151             linkLast(mVexs[p1].firstEdge, node1);
152         // 初始化node2
153         node2 = new ENode();
154         node2->ivex = p1;
155         // 将node2链接到"p2所在链表的末尾"
156         if(mVexs[p2].firstEdge == NULL)
157           mVexs[p2].firstEdge = node2;
158         else
159             linkLast(mVexs[p2].firstEdge, node2);
160     }
161 }
162 
163 /* 
164  * 析构函数
165  */
166 ListUDG::~ListUDG() 
167 {
168 }
169 
170 /*
171  * 将node节点链接到list的最后
172  */
173 void ListUDG::linkLast(ENode *list, ENode *node)
174 {
175     ENode *p = list;
176 
177     while(p->nextEdge)
178         p = p->nextEdge;
179     p->nextEdge = node;
180 }
181 
182 /*
183  * 返回ch的位置
184  */
185 int ListUDG::getPosition(char ch)
186 {
187     int i;
188     for(i=0; i<mVexNum; i++)
189         if(mVexs[i].data==ch)
190             return i;
191     return -1;
192 }
193 
194 /*
195  * 读取一个输入字符
196  */
197 char ListUDG::readChar()
198 {
199     char ch;
200 
201     do {
202         cin >> ch;
203     } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
204 
205     return ch;
206 }
207 
208 /*
209  * 打印邻接表图
210  */
211 void ListUDG::print()
212 {
213     int i,j;
214     ENode *node;
215 
216     cout << "List Graph:" << endl;
217     for (i = 0; i < mVexNum; i++)
218     {
219         cout << i << "(" << mVexs[i].data << "): ";
220         node = mVexs[i].firstEdge;
221         while (node != NULL)
222         {
223             cout << node->ivex << "(" << mVexs[node->ivex].data << ") ";
224             node = node->nextEdge;
225         }
226         cout << endl;
227     }
228 }
229 
230 int main()
231 {
232     char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
233     char edges[][2] = {
234         {'A', 'C'}, 
235         {'A', 'D'}, 
236         {'A', 'F'}, 
237         {'B', 'C'}, 
238         {'C', 'D'}, 
239         {'E', 'G'}, 
240         {'F', 'G'}};
241     int vlen = sizeof(vexs)/sizeof(vexs[0]);
242     int elen = sizeof(edges)/sizeof(edges[0]);
243     ListUDG* pG;
244 
245     // 自定义"图"(输入矩阵队列)
246     //pG = new ListUDG();
247     // 采用已有的"图"
248     pG = new ListUDG(vexs, vlen, edges, elen);
249 
250     pG->print();   // 打印图
251 
252     return 0;
253 }