對於無向圖,e的範圍是:
數據結構中所討論的圖都是簡單圖,任意兩結點間不會有雙重的邊。
對於有向圖,e的範圍是:
圖的各種存儲結構
鄰接矩陣很方便訪問任意兩點的邊,但是不方便計算其鄰接點。在深度和廣度遍歷中廣泛的需要求某點的鄰接點。所以鄰接矩陣只在Floyed和Prim和Dijstra中采用。
鄰接表能很方便的求某頂點的鄰接點,索引對於與遍歷有關的算法大多都采用鄰接表。如深度、廣度、拓撲排序、關鍵路徑。但他也有不足的地方,就是不方便求入度或是那些點可以到他的操作。所以有人引進逆鄰接表。最後人們把這兩種表結合到壹起就是十字鏈表和鄰接多重表。壹個是存儲有向圖,另壹個是存儲無向圖。
在十字鏈表和鄰接多重表很方便求鄰接點的操作和對應的逆操作。所以實際應用中,凡是能用鄰接表實現的壹定能用十字鏈表和鄰接多重表實現。並且它們的存儲效率更高。
1.鄰接矩陣(有向圖和無向圖和網)又稱為數組表示法
typedef struct
{ vextype vexs[maxn]; ∥頂點存儲空間∥
adjtype A[maxn][maxn]; ∥鄰接矩陣∥
int vexnum,arcnum; //圖的頂點數和邊數
GraphKind Kind; //圖的類型
} mgraph;
2.鄰接表(有向圖和無向圖和網)
typedef struct node ∥邊
{ int adj; int w; ∥鄰接點、權∥
struct node *next; ∥指向下壹弧或邊∥
}linknode;
typedef struct ∥頂點類型∥
{ vtype data; ∥頂點值域∥
linknode *farc; ∥指向與本頂點關聯的第壹條弧或邊∥
}Vnode;
typedef struct
{
Vnode G[maxn]; ∥頂點表∥
int vexnum,arcnum;
GraphKind kind;
}ALGraph;
adjvexnextarcinfo
邊結點
datafirstarc
頂點結點
3.十字鏈表(有向圖和有向網)
headvextaivexhlinktlinkinfo
邊結點
datafirstinfirstout
頂點結點
4.鄰接多重表(無向圖)
markivexjvexilinkjlinkinfo
邊結點
datafirstedge
頂點結點
有向無環圖(DAG):是描述含有公***子式的表達式的有效工具。二叉樹也能表示表達式,但是利用有向無環圖可以實現對相同子式的***享,從而節省存儲空間。
頂點的度:
無向圖:某頂點V的度記為D(V),代表與V相關聯的邊的條數
有向圖:頂點V的度D(V)=ID(V)+OD(V)
強連通分量:在有向圖中,若圖中任意兩頂點間都存在路徑,則稱其是強連通圖。圖中極大 強連通子圖稱之為強連通分量
“極大”在這裏指的是:往壹個連通分量中再加入頂點和邊,就構不成原圖中的壹個 連通子圖,即連通分量是壹個最大集的連通子圖。有向圖的連通就是指該有向圖是強連通的。
考研有疑問、不知道如何總結考研考點內容、不清楚考研報名當地政策,點擊底部咨詢官網,免費領取復習資料:/xl/