圖的基本操作

• 基本操作：
• 判斷邊是否存在：
• 列出與某節點相鄰的邊：
• 在圖中插入一個頂點：
• 在圖中刪除一個頂點：
• 在圖中添加一條邊：
• 在圖中刪除一個邊：
• 查找某頂點的第一個鄰接點：
• 查找某邊的權值：
• 查找某一頂點鄰接點的下一個鄰接點：

基本操作：

判斷邊是否存在：

ps：
在鄰接表中，要搜索某節點的整個邊表才能找到是否存在邊,O(1)~O(|v|)
在鄰接矩陣中，只需要判斷該邊對應數組位置的值即可，O(1)
所以從判斷是否存在邊的角度看，鄰接矩陣法更優

列出與某節點相鄰的邊：

無向圖：
在鄰接矩陣中，只需要搜索對應行或對應列即可,O(|V|)
在鄰接表中，只需要遍歷該節點的邊表即可,O(1)~O(|V|)
所以在無向圖中， 列出與某節點相鄰的邊時鄰接表法更優
有向圖：
在鄰接矩陣中，只需要搜索對應行和對應列即可,O(|V|)
在鄰接表中，出邊很容易，但是找入邊需要遍歷整個邊表:
1、尋找出邊：O(1)~O(|V|)
2、尋找入邊：O(|E|) (遍歷所有的邊節點)
所以在有向圖中，列出與某節點相鄰的邊時鄰接矩陣法更優(但是存儲稀疏圖，E比較小)

在圖中插入一個頂點：

ps：
在鄰接表法中，將該頂點加入到頂點表中將邊的關系加入到邊表中，O(1)
在鄰接矩陣法中，擴充一行和一列，放置對應關系,O(1)

在圖中刪除一個頂點：

無向圖：

ps：
在鄰接表法中，刪除該節點和對應的邊表即可，O(|V|)
在鄰接矩陣法中，刪除該頂點對應的行與列即可，有以下兩種情況,O(1)~O(|E|)
1、將后續元素前移，用D覆蓋C，但是會讓大量元素移動，代價太大
2、將刪除節點對應行列置0，在頂點結構體中設置bool變量來標記節點的空

有向圖：

在圖中添加一條邊：

ps：
在鄰接表法中，在倆端節點的邊表添加該邊，O(1)
在鄰接矩陣法中，把對應的倆個矩陣值修改即可,O(1)（頭插法優于尾插法，O(1)是頭插法的時間復雜度，尾插法還需要遍歷邊表）

在圖中刪除一個邊：

ps：
在鄰接表法中，遍歷整個邊表找到對應的邊表節點，然后刪除
在鄰接矩陣法中，只需要修改對應位的值即可
所以在在刪除邊的操作中，鄰接矩陣法更優

查找某頂點的第一個鄰接點：

鄰接矩陣：O(1)~O(|V|)
鄰接表：O(1)

查找某邊的權值：

核心問題：找邊
鄰接矩陣：O(1)
鄰接表：O(1)~O(|V|)

查找某一頂點鄰接點的下一個鄰接點：

鄰接矩陣：O(1)~O(|V|)
鄰接表：O(1)

總結

以上是生活随笔為你收集整理的数据结构之图的基本操作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。