程式扎記: [ Data Structures with Java ] Section 26.1 : Representing Graphs

標籤

2011年5月16日 星期一

[ Data Structures with Java ] Section 26.1 : Representing Graphs

Preface : 
In order to implement a graph, we need some way to represent the set of vertices and their edges. Assume the vertices are v0, v1, v2..., vm-1. An m by m matrix, called an adjacency matrix, identifies the edges. An entry in row i and column j corresponds to the edge e(v, vj). Its value is the weight of the edge, or 0 if the edge does not exist. For instance, below figure shows a non-weighted and a weighted graph, with the corresponding adjacency matrices : 
 

The adjacency matrix representation has the disadvantage that, regardless of the number of edges, it always requites V x V = V^2 entries, where V is the number of vertices. Another representation of a graph associates with each vertex a list of its adjacent vertices (neighbors). This model is often more efficient because it stores information for precisely the edges that actually belong to the graph. For each vertex, an element in the adjacency list is a pair consisting of the destination vertex and the weight of the edge. For the graph from upper figure, we give the adjacency-list representation as below figure : 
 

The DiGraph class uses the adjacency-list representation for a graph. We will discuss more about DiGraph in the follow up sections.

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!