對于圖來說,鄰接矩陣是不錯的一種圖存儲結構,但是我們也發現,對于邊數相對頂點較少的圖,這種結構是存在對存儲空間的極大浪費的。因此我們考慮另外一種存儲結構方式:鄰接表(Adjacency List),即數組與鏈表相結合的存儲方法。
鄰接表的處理方法是這樣的。
1、圖中頂點用一個一維數組存儲,另外,對于頂點數組中,每個數據元素還需要存儲指向第一個鄰接點的指針,以便于查找該頂點的邊信息。
2、圖中每個頂點vi的所有鄰接點構成一個線性表,由于鄰接點的個數不定,所以用單鏈表存儲,無向圖稱為頂點vi的邊表,有向圖稱為頂點vi作為弧尾的出邊表。
例如圖7-4-6就是一個無向圖的鄰接表結構。
?
若是有向圖,鄰接表的結構是類似的,如圖7-4-7,以頂點作為弧尾來存儲邊表容易得到每個頂點的出度,而以頂點為弧頭的表容易得到頂點的入度,即逆鄰接表。
?
對于帶權值的網圖,可以在邊表結點定義中再增加一個weight的數據域,存儲權值信息即可,如圖7-4-8所示。
?
下面示例無向圖的鄰接表創建:(改編自《大話數據結構》)
C++ Code
#include
using namespace std;
#define MAXVEX 100 /* 最大頂點數,應由用戶定義 */
typedef char VertexType; /* 頂點類型應由用戶定義 */
typedef int EdgeType; /* 邊上的權值類型應由用戶定義 */
typedef struct EdgeNode /* 邊表結點 */
{
int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */
EdgeType weight; /* 用于存儲權值,對于非網圖可以不需要 */
struct EdgeNode *next; /* 鏈域,指向下一個鄰接點 */
} EdgeNode;
typedef struct VextexNode /* 頂點表結點 */
{
VertexType data; /* 頂點域,存儲頂點信息 */
EdgeNode *firstedge; /* 邊表頭指針 */
} VextexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numNodes, numEdges; /* 圖中當前頂點數和邊數 */
} GraphAdjList;
void CreateALGraph(GraphAdjList *Gp)
{
int i, j, k;
EdgeNode *pe;
cout << "輸入頂點數和邊數(空格分隔):" << endl;
cin >> Gp->numNodes >> Gp->numEdges;
for (i = 0 ; i < Gp->numNodes; i++)
{
cout << "輸入頂點信息:" << endl;
cin >> Gp->adjList[i].data;
Gp->adjList[i].firstedge = NULL; /* 將邊表置為空表 */
}
for (k = 0; k < Gp->numEdges; k++) /* 建立邊表 */
{
cout << "輸入邊(vi,vj)的頂點序號i,j(空格分隔):" << endl;
cin >> i >> j;
pe = (EdgeNode *)malloc( sizeof(EdgeNode));
pe->adjvex = j; /* 鄰接序號為j */
/* 將pe的指針指向當前頂點上指向的結點 */
pe->next = Gp->adjList[i].firstedge;
Gp->adjList[i].firstedge = pe; /* 將當前頂點的指針指向pe */
pe = (EdgeNode *)malloc( sizeof(EdgeNode));
pe->adjvex = i;
pe->next = Gp->adjList[j].firstedge;
Gp->adjList[j].firstedge = pe;
}
}
int main( void)
{
GraphAdjList GL;
CreateALGraph(&GL);
return 0;
}
這里的鄰接點插入使用了單鏈表創建中的頭插法,對于無向圖來說,一條邊對應都是兩個頂點,所以在循環中,一次就針對i和j分別進行了插入。
-
矩陣
+關注
關注
0文章
423瀏覽量
34528 -
存儲結構
+關注
關注
0文章
21瀏覽量
9712
發布評論請先 登錄
相關推薦
評論