圖數據結構

圖是一個集合，其中一些對對象都是通過鏈路連接的對象的圖形表示。互聯的對象是通過頂點來表示，以及連接所述頂點的鏈接被稱為邊緣。

形式上，曲線圖是一對集(V, E), 其中V是頂點組及E是邊集，連接頂點的對。看看下麵的圖 -

另外，在上述圖中，

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的路徑。

基本操作

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

• 添加頂點 − 添加一個頂點到圖。

• 添加邊緣 − 圖的兩個頂點之間添加邊線。

• 顯示頂點 − 顯示一個圖形的頂點。

添加頂點操作

//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);
}