关注码农话题
做一个实实在在的内行人

图数据结构

图是一个集合,其中一些对对象都是通过链路连接的对象的图形表示。互联的对象是通过顶点来表示,以及连接所述顶点的链接被称为边缘。

形式上,曲线图是一对集(V, E), 其中V是顶点组及E是边集,连接顶点的对。看看下面的图 –

Graph Example

另外,在上述图中,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

图数据结构

数学图可在数据结构中表示。我们可以使用顶点数组和边缘的二维数组来表示图。 在进一步前进学习前,让我们熟悉一下一些重要术语−

  • 顶点 − 图的每个节点被表示为顶点。在下面的例子中给出,标记圆圈代表顶点。因此,A至G的顶点。使用数组,如下面的图片我们可以代表他们。这里A可以通过索引0,B可以使用索引1等来识别。
  • 边缘 − 边表示两个顶点之间的线的两个顶点之间的路径。在下面的例子中给出,线路从A到B,B到C等代表边缘。我们可以用一个二维数组来表示数组所示图如下。这里AB可以表示为1,在第0行,第1列,BC为1,在第1行,列2等等,保持其他的组合为0。
  • 相邻 − 两个节点或顶点相邻当它们通过一个边彼此连接。在下面的例子给出,B是相邻的A,C是相邻B等。
  • 通路 − 路径代表两个顶点之间的边的序列。在下面的例子给出ABCD表示从A到D的路径。

graph

基本操作

以下是遵循图的基本操作。

  • 添加顶点 − 添加一个顶点到图。
  • 添加边缘 − 图的两个顶点之间添加边线。
  • 显示顶点 − 显示一个图形的顶点。

添加顶点操作

//add vertex to the vertex list
void addVertex(char label){
   struct vertex* vertex = (struct vertex*) malloc(sizeof(struct vertex));
   vertex->label = label;  
   vertex->visited = false;     
   lstVertices[vertexCount++] = vertex;
}

添加边缘操作

//add edge to edge array
void addEdge(int start,int end){
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
}

显示边缘操作

//display the vertex
void displayVertex(int vertexIndex){
   printf("%c ",lstVertices[vertexIndex]->label);
}

入职你的梦想 VS 变现你的技术

IT面试宝典码农市场