有向图的邻接矩阵通过邻接矩阵表示有向图。 如下所示。
在上面的有向图G2中包含“a，b，c，d，e，f，g”的合计7个顶点，而且还包含“a，b，b，c，b，e，b，b，c，d，c，f”
上图右边的矩阵是有向图G2的邻接矩阵图像。 A[i][j]=1表示从第I个顶点到第j个顶点是一条边，A[i][j]=0表示不是一条边，A[i][j]表示第I行j列的值。 例如，A[1][2]=1表示从顶点b到顶点c是边。
代码实现# include iostream # includevectorusingnamespacestd； # definemax 100 classmatrixdg { private : charmvexs [ max ]； //顶点集合int mVexNum； //顶点数int mEdgNum； //边数int mMatrix[MAX][MAX]； //邻接矩阵public: //创建图(手工输入)矩阵DG )； //使用提供的顶点和边绘制图(matrixDG(char*vexs，int vNum，char ) edges ) [2]，int eNum )； ~MatrixDG (； void print (； char readChar (； intgetposition(charch )； (； MatrixDG:MatrixDG () { char c1，c2； int p1，p2； cout '输入顶点数： '； cin mVexNum； 输入cout '边数： '； cin mEdgNum； if (mve xnum1| (med gnum ) mvexnum*(mvexnum-1 ) ) )的输入有误！ ' endl； 返回； }for(intI=0； i mVexNum； I ) cout'vertex(I ' ) : )； mVexs[i]=readChar (； }for(intj=0； j mEdgNum； j ) {cout'edge(j ) ) : )； c1=readChar (； c2=readChar (； P1=getposition(C1； P2=getposition(C2； if(p1==-1||p2==-1 ) { cout '输入边缘错误！' endl； 返回； } mMatrix[p1][p2]=1； } matrix DG :3360矩阵DG (char * vexs，int vNum，char ) Edges ) [2]，int eNum ) if ) vnummax ) return； mVexNum=vNum； mEdgNum=eNum； //初始化顶点for (inti=0； i mVexNum； I ) mVexs[i]=vexs[i]； int p1，p2； for(intj=0； j mEdgNum； j ) (/得到边缘的起点和终点=getposition(edges[j][0] )； P2=getposition(Edges[j][1]； //将连接的2个点设为1if (P1==-1p2==-1 ) ) { cout '输入的边缘错误！' endl； 返回； } mMatrix[p1][p2]=1； } } matrix DG :至matrix DG () intmatrixdg : get position (charch ) ) for ) intI=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();}手动输入时运行结果如下：
输入顶点数:7输入边数：9vertex(0):Avertex(1):Bvertex(2):Cvertex(3):Dvertex(4):Evertex(5):Fvertex(6):Gedge(0):ABedge(1):BCedge(2):BEedge(3):BFedge(4):CEedge(5):DCedge(6):EBedge(7):EDedge(8):FG0 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 有向图的邻接表通过邻接表来表示有向图。如下如所示：
上面的有向图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 100class 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;}手动输入时运行结果如下：
输入顶点数:7输入边数:9vertex(0):Avertex(1):Bvertex(2):Cvertex(3):Dvertex(4):Evertex(5):Fvertex(6):Gedge(0):ABedge(1):BCedge(2):BEedge(3):BFedge(4):CEedge(5):DCedge(6):EBedge(7):EDedge(8):FG0(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):