图数据结构及操作

图是一种比较重要的数据结构之一，主要应用于交通、通信等网络化的信息存贮中.

之前有被提问：如果想知道两个城市之间的距离适合采用哪种数据结构？

回答：图（我发音：头：tou）

再被提问：什么头，头的，你说的是什么呀？

回答：te wu tu 图   图结构

又说道：说的什么，不知道你在说什么？

我回答道：算了，听不懂就算了交流实在困难

此处省略一万个”X”........

---

顶点：V  Vertex

边：  E  Edge

V集合表示包含哪些顶点

G集合表示顶点之间的连接关系.

 

无向图：边没有方向

有向图：边有方向<V1,V2>  从V1到V2

 

顶点的度：

连接顶点的数量

 

有向图中一个点有入度和出度  之和叫度

 

邻接点：

有向图邻接点有：起始顶点  终止顶点

无向图：两个顶点都是互为邻接点

 

无向完全图：

每两个顶点之间都存在一条边   N*(N-1)/2  边的数量

 

有向完全图

每两个顶点之间都存在两条边相反方向的边  N*(N-1)

void createGraphMatrix(GraphMatrix* GM) { int i, j, k; int weight; char EstartV, EendV; printf("请输入图中顶点的信息\n"); for (i = 0; i < GM->VertexNum; i++) { getchar(); printf("第%d个顶点：", i + 1); //scanf("%c", &(GM->Vertex[i])); cin >> GM->Vertex[i]; } ​ ​ printf("输入构成各边的顶点的权值：\n"); for (j = 0; j < GM->EdgeNUm; j++) { getchar(); printf("第%d条边：", j + 1); //scanf("%c %c %d", &EstartV, &EendV, &weight); cin >> EstartV >> EendV >> weight; for (i = 0; EstartV != GM->Vertex[i]; i++); for (k = 0; EendV != GM->Vertex[k]; k++); GM->EdgeWeight[i][k] = weight; if (GM->Gtype == 0) //无向图 需要将对角位置的权值也保存一下. { GM->EdgeWeight[k][i] = weight; } } } ​ ​ void ClearGraphMatrix(GraphMatrix* GM) { int i, j; for ( i = 0; i < GM->VertexNum; i++); { for ( j = 0; j < GM->VertexNum; j++) { GM->EdgeWeight[i][j] = MAXVALUE; } } } ​ void OutPutGraphMatrix(GraphMatrix* GM) { int i, j; for (i = 0; i < GM->VertexNum; i++) { printf("\t%c", GM->Vertex[i]); //第一行输出顶点 } printf("\n"); ​ for (i = 0; i < GM->VertexNum; i++) { printf("%c", GM->Vertex[i]); for (j = 0; j < GM->VertexNum; j++) { if (GM->EdgeWeight[i][j] == MAXVALUE) { printf("\tZ"); } else { printf("\t%d", GM->EdgeWeight[i][j]); } } printf("\n"); } ​ } ​ ​ void DeepTraveGraphMatrix(GraphMatrix* GM,int n) //从第n个顶点开始深度遍历图 { int i; GM->isTraved[n] = 1; printf("->%c", GM->Vertex[n]); ​ for (i = 0; i < GM->VertexNum; i++) { if (GM->EdgeWeight[n][i] != MAXVALUE && !GM->isTraved[n]) { DeepTraveGraphMatrix(GM, i); } } ​ } ​ int main() { GraphMatrix GM; ​ printf("输入生成图的类型：\n"); //scanf("%d", &GM.Gtype); cin >> GM.Gtype; cout << "输入顶点：" << endl; cin >> GM.VertexNum; cout << "输入边数" << endl; cin >> GM.EdgeNUm; ClearGraphMatrix(&GM); createGraphMatrix(&GM); cout << "该图的邻接矩阵如下：\n" << endl; OutPutGraphMatrix(&GM); cout << "深度优先搜索\n" << endl; DeepTraveGraphMatrix(&GM,3); ​ ​ return 0; }