数据结构中图的初步了解
随着计算机科学和技术的发展，数据结构已经成为了大学中相当重要的一门学科。其中“图”是数据结构中的一个重要概念，本文将会介绍图的各种关键名词和算法。
一、图的基本概念
图（Graph）是一种非线性数据结构，由节点（Vertex）和边（Edge）组成。在图中，节点之间可以通过边连接起来，形成任意复杂的结构。
图G(V,E)是由顶点集V和边集E组成的。如果边是有方向的，则称该图为有向图（DiGraph）；反之，则称该图为无向图（UnDiGraph）。两个相邻的结点称为邻结点（Adjacent Vertex），起始节点称为始点（Start Vertex），结束节点称为终点（End Vertex），从一个节点出发到达另外一个节点的边称为出边（Outgoing Edge），指向该节点的边称为入边（Incoming Edge）。一个节点的度数（Degree），包括出度（Out Degree）和入度（In Degree）。对于一个图中所有节点的度数之和，等于所有边数的两倍。
完全图（Complete Graph）是指节点之间都有连边的图，因此完全图的边数最多，为n(n-1)/2，n为节点数。稠密图（Dense Graph）则是指节点之间有相对较多的连边的图。稀疏图（Sparse Graph）则相反，节点之间的连边数量比较少。子图（Sub Graph）是指原图中一部分节点和它们之间的连边所组成的图。路径（Path）是指从一个节点到另一个节点所经过的所有边和节点的序列。回路（Cycle）是指起点和终点相同的路径。
连通图（Connected Graph）是指任意两个节点之间都存在路径的图。如果不满足这个条件，则称之为非连通图（Disconnected Graph）。强连通图（Strongly Connected Graph）是指任意两个节点之间都存在有向路径的图。非强连通图则相反。
二、算法
1. 图的邻接矩阵存储的初始化算法：
```
void InitMatrix(adjmatrix GA, int K){
for(int i0; i for(int j0; j GA[i][j] 0; // 初始化为0 } } } ``` 2. 根据一个图的边集生成图的邻接矩阵的算法： ``` void CreateMatrix(adrmatrix GA,int n,char*s,int k1,int k2){ for(int i0; i for(int j0; j if(ij){ GA[i][j] 0; } else{ GA[i][j] -1;// 用-1表示不连通 } } } for(int i0; i char a s[i*2]; char b s[i*2 1]; GA[a-'A'][b-'A'] 1; GA[b-'A'][a-'A'] 1;// 如果是无向图，需要把两个方向都赋值 } } ``` 3. 遍历算法： (1) 深度优先遍历： ``` void dfsMatrix(adjmatrix GA, int i, int n, bool *visited){ visited[i] true; printf("%c ",i 'A'); for(int j0;j if(GA[i][j]!0 !visited[j]){ dfsMatrix(GA,j,n,visited); } } } ``` (2) 广度优先遍历： ``` void bfsMatrix(adjmatrix GA, int i, int n, bool *visited){ int queue[MAXSIZE],front-1,rear-1; visited[i] true; printf("%c ",i 'A'); queue[ rear] i; while(front!rear){ front ; int j queue[front]; for(int k0;k if(GA[j][k]!0 !visited[k]){ visited[k] true; printf("%c ",k 'A'); queue[ rear] k; } } } } ``` 图作为非常重要的数据结构，在计算机科学中扮演着非常重要的角色。学习和理解图的相关概念和算法，是每个计算机科学专业学生不可或缺的一部分。 版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
