圖論

圖論（Graph theory）是數(shù)學(xué)的一個分支，它以圖為研究對象，研究頂點(diǎn)和邊組成的圖形的數(shù)學(xué)理論和方法。

圖論起源于著名的柯尼斯堡七橋問題。

圖

圖是由頂點(diǎn)(Vertex)和邊(Edge)組成，每條邊的兩端都必須是圖的兩個頂點(diǎn)(可以是相同的頂點(diǎn))。而記號G(V,E)表示圖G的頂點(diǎn)集合是V，邊集合是E。

如下(就像公交車路線一樣，四通八達(dá)的)

v4────────────v5 / v1────v6 \ / v3

一般來說，圖分為有向圖和無向圖，有向圖的所有邊都有方向，而無向圖每一條邊都是雙向的。

術(shù)語

頂點(diǎn)的度:指的是和該頂點(diǎn)相連邊的條數(shù)

出度:對于有向圖來說，頂點(diǎn)的出邊條數(shù)稱為出度

入度:對于有向圖來說，頂點(diǎn)的入邊條數(shù)稱為入度

權(quán)值:每一條邊和頂點(diǎn)都可以有一定的屬性，量化的屬性稱為權(quán)值，頂點(diǎn)和邊的權(quán)值分別稱為點(diǎn)權(quán)和邊權(quán)

一:鄰接矩陣，一般在頂點(diǎn)不大于1000時，我們可以選用鄰接矩陣實(shí)現(xiàn)圖(實(shí)際上是二維數(shù)組)。

二:鄰接表，C++可以采用vector(一種順序容器，支持隨機(jī)訪問)實(shí)現(xiàn)鄰接表。Java可以采用List去實(shí)現(xiàn)

本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊舉報(bào)。