图结构作为一种比线性表和树更为复杂的数据结构，任意两个数据元素之间都有可能相关。在离散数学中有图论一章，就是专门研究图的性质的。
目录
邻接矩阵表示法
邻接表表示法
图的遍历(邻接表的实现)
不足之处
数据的逻辑结构是非线性的图结构，一个节点可能有多个前驱、多个后继；
从存储结构上来说，只有链式存储结构，没有顺序存储结构。但是，可以通过一个邻接矩阵表示两结点之间的连接关系。
图的具体分为：无向图、有向图、无向网、有向网
邻接矩阵表示法
#pragma once #includeusing namespace std; const int MaxInt = 32767; const int MVNum = 10; typedef char Elemtype; typedef enum { DG, DN, UDG, UDN } GraphKind;//创建一个枚举类型GraphKind //DG:有向图 DN:有向网 UDG：无向图 UDN：无向网 class AMGraph { public: AMGraph(GraphKind k); void Create();//创建网or图 int LocateVex(const Elemtype s);//定位邻接矩阵中的1或者权值的位置 void Printarcs();//打印邻接矩阵 private: GraphKind kind; Elemtype vexs[MVNum];//创建一个顶点表 int arcs[MVNum][MVNum];//邻接矩阵 int vex_num;//当前的顶点数 int arc_num;//当前的边数 }; AMGraph::AMGraph(GraphKind k) { this->kind = k; this->vex_num = 0; this->arc_num = 0; } void AMGraph::Create() { cout << "输入总顶点数："; cin >> this->vex_num; cout << "输入总边数："; cin >> this->arc_num; cout << "初始化顶点表！" << endl; //也就是说输入点的信息 //初始化一下这个矩阵 for (int i = 0; i < this->vex_num; i++) { cout << "请输入第" << i + 1 << "个点的信息:"; cin >> vexs[i]; } for (int i = 0; i < this->vex_num; i++) { for (int j = 0; j < this->vex_num; j++) { if (this->kind == 0 || this->kind == 2) this->arcs[i][j] = 0; else this->arcs[i][j] = MaxInt; } } //正式构建邻接矩阵 for (int i = 0; i < this->arc_num; i++) { Elemtype s1, s2; int val=1; int locate1=-1, locate2=-1; cout << "输入第一个点：" << endl; cin >> s1; cout << "输入第二个点：" << endl; cin >> s2; if (this->kind == 1 || this->kind == 3) { cout << "输入权值："; cin >> val; } locate1 = this->LocateVex(s1); locate2 = this->LocateVex(s2); if (locate1 == -1 || locate2 == -1) return; switch (this->kind) { case DG: this->arcs[locate1][locate2] = 1; break; case DN: this->arcs[locate1][locate2] = val; break; case UDG: this->arcs[locate1][locate2] = 1; this->arcs[locate2][locate1] = 1; break; case UDN: this->arcs[locate1][locate2] = val; this->arcs[locate2][locate1] = val; break; default: break; } } } int AMGraph::LocateVex(const Elemtype s) { for (int i = 0; i < this->vex_num; i++) { if (s == this->vexs[i]) return i;//如果找到喽 就返回在顶点表中的下标 } return -1;//如果没找到，就返回-1 } void AMGraph::Printarcs() { for (int i = 0; i < this->vex_num; i++) { for (int j = 0; j < this->vex_num; j++) { cout << this->arcs[i][j] << "t"; } cout << endl; } }
邻接表表示法
图中的每一个顶点建立一个单链表，把与结点相邻接的顶点放在链表中，顶点（表头节点）组成一个线性表，表头结点的指针域指向边表，时间复杂度O(n+e)(e:边数)
关于邻接表表示法的相关理论可参考诸多数据结构与算法书籍，下面给出邻接表的表示方法：
#pragma once #includeusing namespace std; typedef char Elemtype; const int MaxInt = 32767; typedef enum { DG, DN, UDG, UDN } GraphKind;//创建一个枚举类型GraphKind //DG:有向图 DN:有向网 UDG：无向图 UDN：无向网 //可以通过邻接表实现四种kind的计算机存储结构 //邻接表的三部分定义：边结点、存放顶点的头结点线性表、图的类型 class ArcNode//定义了边结点 { public: int adjvex;//邻接顶点所在表中下标 int weight;//边权重 ArcNode* nextarc;//指向下一条边的指针 }; class VNode { public: Elemtype data; ArcNode* firstarc; }; class ALGraph { public: ALGraph(GraphKind k); void CreateALG();//创建邻接表 int LocateVex(const Elemtype s); private: VNode* vertices; GraphKind kind; int vex_num; int arc_num; }; ALGraph::ALGraph(GraphKind k) { this->vex_num = 0; this->arc_num = 0; this->kind = k; this->vertices = nullptr; } void ALGraph::CreateALG() { cout << "输入总顶点数："; cin >> this->vex_num; cout << "输入总边数："; cin >> this->arc_num; //初始化顶点表 this->vertices = new VNode[vex_num]; for (int i = 0; i < this->vex_num; i++) { cout << "输入顶点表中的数据域："; cin >> vertices[i].data; vertices[i].firstarc = nullptr; } //边结点的链接 for (int i = 0; i < this->arc_num; i++) { Elemtype s1, s2; int locate1 = -1, locate2 = -1; cout << "输入第1点：" << endl; cin >> s1; cout << "输入第2点：" << endl; cin >> s2; locate1 = this->LocateVex(s1); locate2 = this->LocateVex(s2); int val=1; if (this->kind == 1 || this->kind == 3)//如果创建的是有向网无向网就输入对应的权值 { cout << "输入权值："; cin >> val; } ArcNode* p; p = new ArcNode; p->weight = val; p->adjvex = locate2; p->nextarc = this->vertices[locate1].firstarc; this->vertices[locate1].firstarc = p; if (this->kind == 2 || this->kind == 3)//如果无向图/无向网 { ArcNode* p1; p1 = new ArcNode; p1->weight = val; p1->adjvex = locate1; p1->nextarc = this->vertices[locate2].firstarc; this->vertices[locate2].firstarc = p1; } } } int ALGraph::LocateVex(const Elemtype s) { for (int i = 0; i < this->vex_num; i++) { if (s == this->vertices[i].data) return i;//如果找到喽 就返回在顶点表中的下标 } return -1;//如果没找到，就返回-1 }
邻接表缺点：对于图来说，需要开辟两个空间来记录两个结点之间的关系，这对于后续的删除以及图的遍历都是不利的，为了克服这一缺点，引入邻接多重表；
对于有向图/网来说，一个结点只能记录他的出度，却不能记录入度，因此引入了十字链表，求得顶点的入度和出度.
图的遍历(邻接表的实现)
下面的两段程序是针对邻接表进行的深度优先搜索（DFS）和广度优先搜索（BFS），下面的程序是邻接表程序上又加了几个成员函数
以邻接表为表示方法，深度优先算法，更像是看到一个结点，一看他没被访问过，就立马就再从表结点出发，以该结点为出度边，递归访问，这样来回得穿梭于表头结点和边结点之间，从图形上是说是“一条道走到黑”；
而广度优先算法，更像是从邻接表上起始点出发，一条道走到黑，路上把所有遍历的且之前未访问过的结点，放到容器中，走到黑之后，再掉头从queue中输出队列元素，继续再邻接表上一条道走到黑，不用递归噢，走到黑之后，让容器再给你吐出来一个起始点。
类.hpp
#pragma once #pragma once #include#include using namespace std; typedef char Elemtype; const int MaxInt = 32767; typedef enum { DG, DN, UDG, UDN } GraphKind;//创建一个枚举类型GraphKind //DG:有向图 DN:有向网 UDG：无向图 UDN：无向网 //可以通过邻接表实现四种kind的计算机存储结构 //邻接表的三部分定义：边结点、存放顶点的头结点线性表、图的类型 class ArcNode//定义了边结点 { public: int adjvex;//邻接顶点所在表中下标 int weight;//边权重 ArcNode* nextarc;//指向下一条边的指针 }; class VNode { public: Elemtype data; ArcNode* firstarc; }; class ALGraph { public: ALGraph(GraphKind k); void CreateALG();//创建邻接表 void InitArry();//标志数组置空 void DFS_AL(const Elemtype s);//输入时图中的某一个结点，深度优先遍历，采用邻接表表示,本质上操作对象还是表头结点表，而非依靠边结点输出 void BFS_AL(const Elemtype s);//广度优先访问连通图，还有构建一个标志数组 private: int LocateVex(const Elemtype s);//根据输入的s值，确定要连接的两个点在表头结点中的位置 VNode* vertices; GraphKind kind; int vex_num; int arc_num; int* visitedDFS; queue Q; }; ALGraph::ALGraph(GraphKind k) { this->vex_num = 0; this->arc_num = 0; this->kind = k; this->vertices = nullptr; } void ALGraph::CreateALG() { //初始化顶点表 cout << "输入总顶点数："; cin >> this->vex_num; cout << "输入总边数："; cin >> this->arc_num; //初始化标志数组 this->visitedDFS = new int[vex_num]; for (int j = 0; j < this->vex_num; j++) { visitedDFS[j] = 0;//默认都没有访问过 } //初始化表头 this->vertices = new VNode[vex_num]; for (int i = 0; i < this->vex_num; i++) { cout << "输入顶点表中的数据域："; cin >> vertices[i].data; vertices[i].firstarc = nullptr; } //边结点的链接 for (int i = 0; i < this->arc_num; i++) { Elemtype s1, s2; int locate1 = -1, locate2 = -1; cout << "输入第1点：" ; cin >> s1; cout << "输入第2点：" ; cin >> s2; locate1 = this->LocateVex(s1); locate2 = this->LocateVex(s2); int val = 1; if (this->kind == 1 || this->kind == 3)//如果创建的是有向网无向网就输入对应的权值 { cout << "输入权值："; cin >> val; } ArcNode* p; p = new ArcNode; p->weight = val;//头插法 p->adjvex = locate2; p->nextarc = this->vertices[locate1].firstarc; this->vertices[locate1].firstarc = p; if (this->kind == 2 || this->kind == 3)//如果无向图/无向网 { ArcNode* p1; p1 = new ArcNode; p1->weight = val; p1->adjvex = locate1; p1->nextarc = this->vertices[locate2].firstarc; this->vertices[locate2].firstarc = p1; } } } int ALGraph::LocateVex(const Elemtype s) { for (int i = 0; i < this->vex_num; i++) { if (s == this->vertices[i].data) return i;//如果找到喽 就返回在顶点表中的下标 } return -1;//如果没找到，就返回-1 } void ALGraph::InitArry()//为了防止一次程序中反复遍历图，所以提供给标志数组置0，这样的话，进行多次遍历的时候主程序都将其置空一次； { for (int i = 0; i < this->vex_num; i++) { this->visitedDFS[i] = 0; } } void ALGraph::DFS_AL(const Elemtype s) {//邻接表的展现方式 cout << s << "t";//麻溜把结点输出来; int locate = this->LocateVex(s); this->visitedDFS[locate] = 1; ArcNode* p; p = this->vertices[locate].firstarc; while (p) { int index = p->adjvex;//获得点的索引下标 if (!this->visitedDFS[index]) this->DFS_AL(this->vertices[p->adjvex].data); p = p->nextarc; } } void ALGraph::BFS_AL(const Elemtype s)//不需要遍历，但需要一个队列容器 { cout << s << "t"; int index = this->LocateVex(s); this->visitedDFS[index] = 1; this->Q.push(index); while (!Q.empty()) { int num = Q.front(); Q.pop(); ArcNode* p; p = this->vertices[num].firstarc; while (p) { if (this->visitedDFS[p->adjvex] == 0) { cout << this->vertices[p->adjvex].data << "t"; this->visitedDFS[p->adjvex] = 1; Q.push(p->adjvex); } p = p->nextarc;//如果被访问过了，还要继续去顺着边结点寻找噢，所以这个程序不能放在if语句中 } } cout << endl; }
主程序.cpp
#include#include"图邻接表实现.hpp" using namespace std; int main() { ALGraph K(UDG); K.CreateALG(); K.DFS_AL('A'); cout << endl; K.InitArry(); K.BFS_AL('A'); system("pause"); return 0; }
结果：答案不唯一，由于子图在遍历的时候没有顺序，所以先访问A之后访问B或C都行
原型：
不足之处
这里动态开辟的空间都没释放噢！
