圖的存儲結(jié)構(gòu)除了要存儲圖中各個頂點(diǎn)的本身信息外，同時還要存儲頂點(diǎn)與頂點(diǎn)之間的所有關(guān)系(邊的信息)，因此，圖的結(jié)構(gòu)比較復(fù)雜，很難以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關(guān)系，但也正是由于其任意的特性，故物理表示方法很多。常用的圖的存儲結(jié)構(gòu)有鄰接矩陣、鄰接表等。

鄰接矩陣表示法

對于一個具有n個結(jié)點(diǎn)的圖，可以使用n*n的矩陣(二維數(shù)組)來表示它們間的鄰接關(guān)系。矩陣 A(i,j) = 1 表示圖中存在一條邊 (Vi,Vj),而A(i,j)=0表示圖中不存在邊 (Vi,Vj)。實(shí)際編程時，當(dāng)圖為不帶權(quán)圖時，可以在二維數(shù)組中存放 bool 值。

A(i,j) = true 表示存在邊 (Vi,Vj),
A(i,j) = false 表示不存在邊 (Vi,Vj);

當(dāng)圖帶權(quán)值時，則可以直接在二維數(shù)值中存放權(quán)值，A(i,j) = null 表示不存在邊 (Vi,Vj)。

下面看看我們使用鄰接矩陣實(shí)現(xiàn)的圖結(jié)構(gòu)：

#[derive(Debug)]
struct Node {
    nodeid: usize,
    nodename: String,
}

#[derive(Debug,Clone)]
struct Edge {
    edge: bool,
}

#[derive(Debug)]
struct Graphadj {
    nodenums: usize,
    graphadj: Vec<Vec<Edge>>,
}

impl Node {
    fn new(nodeid: usize, nodename: String) -> Node {
        Node{
            nodeid: nodeid,
            nodename: nodename,
        }
    }
}
impl Edge {
    fn new() -> Edge {
        Edge{
            edge: false,
        }
    }
    fn have_edge() -> Edge {
        Edge{
            edge: true,
        }
    }
}

impl Graphadj {
    fn new(nums:usize) -> Graphadj {
        Graphadj {
            nodenums: nums,
            graphadj: vec![vec![Edge::new();nums]; nums],
        }
    }

    fn insert_edge(&mut self, v1: Node, v2:Node) {
        match v1.nodeid < self.nodenums && v2.nodeid<self.nodenums {
            true => {
                self.graphadj[v1.nodeid][v2.nodeid] = Edge::have_edge();
                //下面這句注釋去掉相當(dāng)于把圖當(dāng)成無向圖
                //self.graphadj[v2.nodeid][v1.nodeid] = Edge::have_edge();
            }
            false => {
                panic!("your nodeid is bigger than nodenums!");
            }
        }
    }
}

fn main() {
    let mut g = Graphadj::new(2);
    let v1 = Node::new(0, "v1".to_string());
    let v2 = Node::new(1, "v2".to_string());
    g.insert_edge(v1,v2);
    println!("{:?}", g);
}

鄰接表表示法

鄰接表是圖的一種最主要存儲結(jié)構(gòu)，用來描述圖上的每一個點(diǎn)。

實(shí)現(xiàn)方式：對圖的每個頂點(diǎn)建立一個容器（n個頂點(diǎn)建立n個容器），第i個容器中的結(jié)點(diǎn)包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。實(shí)際上我們常用的鄰接矩陣就是一種未離散化每個點(diǎn)的邊集的鄰接表。

在有向圖中，描述每個點(diǎn)向別的節(jié)點(diǎn)連的邊（點(diǎn) a->點(diǎn) b 這種情況）。
在無向圖中，描述每個點(diǎn)所有的邊(點(diǎn) a->點(diǎn) b這種情況)

與鄰接表相對應(yīng)的存圖方式叫做邊集表，這種方法用一個容器存儲所有的邊。

練習(xí)：

實(shí)現(xiàn)鏈接表表示法的圖結(jié)構(gòu)。

上一篇：結(jié)構(gòu)體與枚舉下一篇：生命周期（ Lifetime ）