图的定义
图 G GG 由顶点集 V VV 和边集 E EE 组成，记为 G = ( V , E ) G=(V,E)G=(V,E)，其中 V ( G ) V(G)V(G) 表示图 G GG 中顶点的有限非空集；E ( G ) E(G)E(G) 表示图 G GG 中顶点之间的关系（边）集合。
有向图
概念
若 E是有向边（也称弧）的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为 < v , w > ，其中 v , w是顶点， v 称为弧尾，w 称为弧头，< v , w > 称为从 v 到 w 的弧，也称 v 邻接到 w。
模板
/* 有向图邻接矩阵 */ #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; #define MaxVertexNum 100 typedef int weightType; // 权重数据类型 typedef char vertexType; // 顶点数据类型 struct Graph { int vertexnum; int edgenum; vertexType vertexList[MaxVertexNum]; weightType edgeList[MaxVertexNum][MaxVertexNum]; }; void BuildGraph(Graph *G) { int start, end; cout << "Please enter the number of vertices and edges" << endl; cin >> G->vertexnum >> G->edgenum; // 图的权重初始化 for (int i = 0; i < G->vertexnum; i++) { for (int j = 0; j < G->vertexnum; j++) { G->edgeList[i][j] = 0; } } // 图的顶点数据 for (int i = 0; i < G->vertexnum; i++) { cout << "Please enter the data of vertex" << i + 1 << endl; cin >> G->vertexList[i]; } // 输入权重信息 for (int i = 0; i < G->edgenum; i++) { cout << "Please enter the Start number, end number, weight" << endl; cin >> start >> end; cin >> G->edgeList[start - 1][end - 1]; } cout << endl; } void Print_Adjacency_Matrix(Graph G) { for (int i = 0; i < G.vertexnum; i++) { for (int j = 0; j < G.vertexnum; j++) { cout << G.edgeList[i][j] << '\t'; } cout << endl; } } int main() { Graph G; BuildGraph(&G); Print_Adjacency_Matrix(G); cout << endl; system("pause"); return 0; }
/* 有向图邻接表 */ #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; #define MaxVertexNum 100 typedef int weightType; // 权重数据类型 typedef char vertexType; // 顶点数据类型 struct EdgeNode { int adjvex; weightType weight; EdgeNode *next; }; struct VertexNode { vertexType data; EdgeNode *firstedge; }; struct Graph { int vertexnum; int edgenum; VertexNode vertexList[MaxVertexNum]; VertexNode inverseVertexList[MaxVertexNum]; }; void BuildGraph(Graph *G) { int start, end, weight; EdgeNode *newnode; cout << "Please enter the number of vertices and edges" << endl; cin >> G->vertexnum >> G->edgenum; // 图的顶点数据 for (int i = 0; i < G->vertexnum; i++) { cout << "Please enter the data of vertex" << i << endl; cin >> G->vertexList[i].data; G->vertexList[i].firstedge = NULL; G->inverseVertexList[i].data = G->vertexList[i].data; G->inverseVertexList[i].firstedge = NULL; } // 输入权重信息 for (int i = 0; i < G->edgenum; i++) { cout << "Please enter the Start number, end number, weight" << endl; cin >> start >> end >> weight; //start-->end newnode = new EdgeNode; newnode->adjvex = end; newnode->weight = weight; newnode->next = G->vertexList[start].firstedge; G->vertexList[start].firstedge = newnode; // 逆邻接表 newnode = new EdgeNode; newnode->adjvex = start; newnode->weight = weight; newnode->next = G->inverseVertexList[end].firstedge; G->inverseVertexList[end].firstedge = newnode; } } void Print_Adjacency_Matrix(Graph G) { for (int i = 0; i < G.vertexnum; i++) { cout << G.vertexList[i].data << '\t'; EdgeNode *p = G.vertexList[i].firstedge; while (p) { printf("adjvex:%d weight:%d ", p->adjvex, p->weight); p = p->next; } cout << endl; } cout << endl; cout << "inverse adjacency list" << endl; for (int i = 0; i < G.vertexnum; i++) { cout << G.inverseVertexList[i].data << '\t'; EdgeNode *p = G.inverseVertexList[i].firstedge; while (p) { printf("adjvex:%d weight:%d ", p->adjvex, p->weight); p = p->next; } cout << endl; } } int main() { Graph G; BuildGraph(&G); Print_Adjacency_Matrix(G); cout << endl; system("pause"); return 0; }
无向图
概念
若 E是无向边的有限集合时，则图 G 为有向图。边是顶点的无序对，记为 ( v , w )或 ( w , v )。可以说 w 和 v 互 为邻接点。边 ( V , W )依附于 w 和 v ，或称边 ( v , w ) 和 v , w相关联。
模板
邻接矩阵
/* 无向图邻接矩阵 */ #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; #define MaxVertexNum 100 typedef int weightType; // 权重数据类型 typedef char vertexType; // 顶点数据类型 struct Graph { int vertexnum; int edgenum; vertexType vertexList[MaxVertexNum]; weightType edgeList[MaxVertexNum][MaxVertexNum]; }; void BuildGraph(Graph *G) { int start, end; cout << "Please enter the number of vertices and edges" << endl; cin >> G->vertexnum >> G->edgenum; // 图的权重初始化 for (int i = 0; i < G->vertexnum; i++) { for (int j = 0; j < G->vertexnum; j++) { G->edgeList[i][j] = 0; } } // 图的顶点数据 for (int i = 0; i < G->vertexnum; i++) { cout << "Please enter the data of vertex" << i + 1 << endl; cin >> G->vertexList[i]; } // 输入权重信息 for (int i = 0; i < G->edgenum; i++) { cout << "Please enter the Start number, end number, weight" << endl; cin >> start >> end; cin >> G->edgeList[start - 1][end - 1]; G->edgeList[end - 1][start - 1] = G->edgeList[start - 1][end - 1]; } cout << endl; } void Print_Adjacency_Matrix(Graph G) { cout << '\t'; for (int i = 0; i < G.vertexnum; i++) { cout << G.vertexList[i] << '\t'; } cout << endl; for (int i = 0; i < G.vertexnum; i++) { cout << G.vertexList[i] << '\t'; for (int j = 0; j < G.vertexnum; j++) { cout << G.edgeList[i][j] << '\t'; } cout << endl; } } int main() { Graph G; BuildGraph(&G); Print_Adjacency_Matrix(G); cout << endl; system("pause"); return 0; }
邻接表
/* 无向图邻接表 */ #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; #define MaxVertexNum 100 typedef int weightType; // 权重数据类型 typedef char vertexType; // 顶点数据类型 struct EdgeNode { int adjvex; weightType weight; EdgeNode *next; }; struct VertexNode { vertexType data; EdgeNode *firstedge; }; struct Graph { int vertexnum; int edgenum; VertexNode vertexList[MaxVertexNum]; }; void BuildGraph(Graph *G) { int start, end, weight; EdgeNode *newnode; cout << "Please enter the number of vertices and edges" << endl; cin >> G->vertexnum >> G->edgenum; // 图的顶点数据 for (int i = 0; i < G->vertexnum; i++) { cout << "Please enter the data of vertex" << i << endl; cin >> G->vertexList[i].data; G->vertexList[i].firstedge = NULL; } // 输入权重信息 for (int i = 0; i < G->edgenum; i++) { cout << "Please enter the Start number, end number, weight" << endl; cin >> start >> end >> weight; //start-->end newnode = new EdgeNode; newnode->adjvex = end; newnode->weight = weight; newnode->next = G->vertexList[start].firstedge; G->vertexList[start].firstedge = newnode; // end-->start newnode = new EdgeNode; newnode->adjvex = start; newnode->weight = weight; newnode->next = G->vertexList[end].firstedge; G->vertexList[end].firstedge = newnode; } } void Print_Adjacency_Matrix(Graph G) { for (int i = 0; i < G.vertexnum; i++) { cout << G.vertexList[i].data << '\t'; EdgeNode *p = G.vertexList[i].firstedge; while (p) { printf("adjvex:%d weight:%d\n", p->adjvex, p->weight); p = p->next; } cout << endl; } } int main() { Graph G; BuildGraph(&G); Print_Adjacency_Matrix(G); cout << endl; system("pause"); return 0; }
简单图
1.不存在重复边
2.不存在顶点到自身的边
完全图
对于无向图
∣E∣ 的取值范围 0到 n ( n − 1 ) / 2，有 n ( n − 1 ) / 2条边的无向图称为完全图
对于有向图
∣E∣ 的取值范围 0 到 n ( n − 1 ) ，有 n ( n − 1 )条弧的有向图称为有向完全图
