圖數據結構

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

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

Graph

另外，在上述圖中，

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

數據結構和算法教程

圖數據結構