【資料結構】圖鄰接表存儲實作

一個圖 G = （V，E）由頂點（vertex）集 V 和邊（edge）集 E 組成。每一條邊就是一個點對（v，w），其中 v，w ∈V。

圖的表示

圖的存儲一般有鄰接表和鄰接矩陣兩種。若圖是稠密的，則宜采用鄰接矩陣；圖是稀疏的，則應改用鄰接表。這裡我們先讨論圖的鄰接表存儲方式。

先看下面的無向圖（圖檔來源于網絡）

鄰接表形式

上面的邊沒有賦予權重，考慮邊的權重，可以在鄰接表後面的連結清單節點中添加 weight 變量表示。

鄰接表前面的數組表示各個頂點，後面的連結清單節點分别表示與該頂點相連接配接的頂點。邊則由兩個頂點組成（最前面的頂點分别與後面對應的連結清單節點的頂點組合而成）。

圖的資料結構

/*鄰接點*/
typedef struct _AdjListNode
{
	int end;     //頂點編号，也是邊的結束頂點編号
	int weight;  //權重
	struct _AdjListNode *next;//指向下一個鄰接點
}AdjListNode;

typedef struct _AdjList
{
	AdjListNode *head;  //指向連結清單的頭節點
}AdjList;

typedef struct _Graph
{
	int vertices;      //頂點數
	int edges;         //邊數
	AdjList *array;
}Graph;
           

圖的建立

/*建立V個頂點的圖*/
Graph* CreateGraph(int V)
{
	Graph *graph = new Graph;
	assert(graph);
	graph->vertices = V;
	graph->edges = 0;

	graph->array = new AdjList[V];

	for (int i = 0; i < V; ++i)
	{
		graph->array[i].head = NULL;
	}

	return graph;
}
           

添加邊

/*
添加邊
如果是有向圖或是因邊的起始頂點不同的不同權重的可基于此簡單修改
*/
void AddEdge(Graph *graph, int begin, int end, int weight)
{
	//邊後頂點  begin --> end
	AdjListNode *newNode = new AdjListNode;
	assert(newNode);
	newNode->end = end;
	newNode->weight = weight;               //begin頂點到end頂點的邊的權重
	newNode->next = graph->array[begin].head;  //新邊插入到連結清單前面（同Hash）
	graph->array[begin].head = newNode;

	//邊前頂點，因為是無向圖，是以類似雙向連結清單形式 end --> begin
	newNode = new AdjListNode;
	newNode->end = begin;
	newNode->weight = weight;               //end頂點到begin頂點的邊的權重
	newNode->next = graph->array[end].head;
	graph->array[end].head = newNode;

	graph->edges++;
}
           

銷毀圖

/*銷毀圖*/
void GraphDestory(Graph *graph)
{
	AdjListNode *delNode = NULL;
	for (int i = 0; i < graph->vertices; ++i)
	{
		delNode = graph->array[i].head;
		while (delNode)      //删除對應連結清單節點
		{
			AdjListNode *temp = delNode;
			delNode = delNode->next;
			delete temp;
		}
		graph->array[i].head = NULL;
	}
	delete[] graph->array;  
	delete graph;
}
           

傳回圖的頂點數和邊數

/*傳回圖的頂點數*/
int GraphVerticesNum(Graph *graph)
{
	return graph->vertices;
}

/*傳回圖的邊數*/
int GraphEdgesNum(Graph *graph)
{
	return graph->edges;
}
           

檢查兩個頂點之間是否有邊

/*檢查兩個頂點間是否有邊*/
bool GraphHasEdge(Graph *graph, int begin, int end)
{
	assert(begin != end);//其餘各參數檢查（圖，頂點編号）未寫出

	/*因為是無向圖，是以隻需檢查其中的一個頂點即可*/
	AdjListNode *node = graph->array[begin].head;
	while (node)
	{
		if (end == node->end)
			return true;
		node = node->next;
	}
	return false;

	/*如果是有向圖，則還需要檢查數組中編号end的頂點*/
}
           

圖就是多個連結清單的聚合。

了解了圖的鄰接表存儲，後面的代碼就好實作了。

基于前面的分析上，下面給出借助STL中的list 來建構鄰接表的圖，前面需要自己建構連結清單，最終實作的圖結構是一樣的，但是代碼的簡潔度不是差了一點半點：

class graph
{
public:
	graph(int v) :vertex(v){
		adj = new list<int>[v];
	}

	void addEdge(int v, int w);
	
private:
	int vertex;
	list<int> *adj;
};

//v:邊的首頂點；w：邊的尾頂點
void graph::addEdge(int v, int w)
{
	adj[v].push_back(w);
}
           

建構時，隻需要對照鄰接表來添加邊。

下面上面建立一個圖過于繁瑣，這裡更新一下，一舉根據輸入建立一個圖，2015.7更新

typedef int VertexType;
typedef int EdgeType;

/*下面構成一個鍊式哈希表結構*/
/*邊表結點*/
typedef struct AdjNode
{
	int adjvex;  //邊的終點
	int weight;  //邊的權重
	struct AdjNode *next;  //指向下一個鄰接點
}AdjNode;

/*頂點表結點*/
typedef struct VertexNode
{
	VertexType data;   //頂點資訊
	AdjNode *pFfirstedge;  //邊表頭指針
}VertexNode;

/*圖結點*/
typedef struct Graph
{
	VertexNode *AdjArray;   //指向頂點表
	int numVertexes;
	int numEdges;
}Graph;

Graph* CreateGraph()
{
	Graph *pGraph = new Graph;
	AdjNode *pNode = NULL;
	if (NULL == pGraph)
		return NULL;

	cout << "輸入頂點數和邊數：" << endl;
	cin >> pGraph->numVertexes >> pGraph->numEdges;

	pGraph->AdjArray = new VertexNode[pGraph->numVertexes]();//建立并初始化為0
	if (NULL == pGraph->AdjArray)
	{
		delete pGraph;
		return NULL;
	}

	/*建立頂點資訊表*/
	for (int i = 0; i < pGraph->numVertexes; ++i)
	{
		/*這裡預設頂點從0到pGraph->numVertexes，可根據需要修改
		如：
		cout << "輸入頂點資訊" << endl;
		cin >> (pGraph->AdjArray)[i].data;
		*/
		(pGraph->AdjArray)[i].data = i;
	}

	/*建立邊表*/
	for (int k = 0; k < pGraph->numEdges; ++k)
	{
		int i, j, w;
		cout << "輸入邊<vi,vj>上的下标i，下标j和權重w：" << endl;
		cin >> i >> j >> w;

		pNode = new AdjNode;
		if (NULL == pNode)
		{
			delete[] pGraph->AdjArray;
			delete pGraph;
			return NULL;
		}
		pNode->adjvex = j;
		pNode->weight = w;
		pNode->next = (pGraph->AdjArray)[i].pFfirstedge;//類鍊式哈希表插入操作，新節點插入到連結清單頭結點
		(pGraph->AdjArray)[i].pFfirstedge = pNode;

		/*如果是無向圖，還需要插入反過來的邊，補充代碼如下*/
		AdjNode *pNode = new AdjNode;
		if (NULL == pNode)
		{
			delete[] pGraph->AdjArray;
			delete pGraph;
			return NULL;
		}
		pNode->adjvex = i;
		pNode->weight = w;
		pNode->next = (pGraph->AdjArray)[j].pFfirstedge;
		(pGraph->AdjArray)[j].pFfirstedge = pNode;
	}
	return pGraph;
}
           

圖結構關鍵在于了解圖的存儲方式，了解了其存儲方式，對于建立圖以及周遊就很好了解實作了。

 圖的鄰接矩陣實作見： http://blog.csdn.net/wenqian1991/article/details/47123807