1. 什么是圖

圖論（graph theory） 是數(shù)學(xué)的一個分支，它以 圖 為研究的對象。

圖論本身是應(yīng)用數(shù)學(xué)的一部分，歷史上圖論曾經(jīng)被很多數(shù)學(xué)家各自獨立建立過。關(guān)于圖論的最早文字記載最早出現(xiàn)在歐拉 1736 年的論著中，也就是著名的柯尼斯堡（Konigsberg）問題（七橋問題）。

2. 圖的定義

一個圖G是一個二元組，即序偶<V,E>，或記作G=<V,E> ，其中V是有限非空集合，稱為G的頂點集,V中的元素稱為頂點或結(jié)點；E稱為 G的邊的集合，所有的邊ei都屬于E，都有v中的結(jié)點與之對應(yīng)，稱ei為 G的邊。

3. 圖的基本概念

l  無向圖：每條邊都是無向邊的圖。

l  有向圖：每條邊都是有向邊的圖。

l  混合圖：在一個圖中，有些邊是有向邊，另一些邊是無向邊，則該圖為混合圖。

l  有限圖：一個圖的點集和邊集都是有窮集的圖。

l  零圖：邊集為空集的圖。

l  平凡圖：僅有一個結(jié)點而沒有邊構(gòu)成的圖。

l  關(guān)聯(lián)：若有ei=(u,v) 且ei屬于E ，則稱u是和v相關(guān)聯(lián)的。

l  孤立點：無邊關(guān)聯(lián)的點。

l  自環(huán)：若一條邊所關(guān)聯(lián)的兩個結(jié)點重合，則稱此邊為自環(huán)。

l  鄰接：關(guān)聯(lián)于同一條邊的兩個點  和  稱為鄰接的；關(guān)聯(lián)于同一個點的兩條邊  和  是鄰接的（或相鄰的）。

4.兩個定理：

l  推論：在任意圖中，度數(shù)為奇數(shù)的點必然有偶數(shù)個。

l  推論：即所有點入度之和等于出度之和。

（這個比較好理解，就如同問世界上的上坡多還是下坡多一樣，答案是一樣多）

由上面的概念可知，樹或者是森林，就是一種特殊的圖。

5. 最簡單的存儲——鄰接矩陣

鄰接矩陣的英文名是 adjacency matrix。它的形式是 bool adj[n][n]，這里面n是節(jié)點個數(shù)，adj[i][j]表示i和j之間是否有邊。

如果邊有權(quán)值，也可以直接用 int adj[n][n] ，直接把邊權(quán)存進去。

它的優(yōu)點是可以在O(1)時間內(nèi)得到一條邊是否存在，缺點是需要占用O(n^2)的空間。對于一個稀疏的圖（邊相對于點數(shù)的平方比較少）來說，用鄰接矩陣來存儲的話，成本偏高。

其代碼可以表示為（假設(shè)各邊長度均為1）：

#include<iostream>
 
using namespace std;
 
const int maxn=105;
int adj[maxn][maxn]={0};    //定義鄰接矩陣
 
int x,y;    //輸入兩條邊
int n,m;    //供輸入n對邊 ,m個頂點 (x,y <= m) 
 
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        adj[x-1][y-1]=1;
        adj[y-1][x-1]=1;
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            cout<<adj[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}