圖（Graph）是一種復雜的非線性結構，它可以描述數(shù)據(jù)間的關系，被廣泛使用。

圖 G 由兩個集合 V 和 E 組成，記為。V是頂點的有窮非空集合，E是邊的集合。通常，也將 G 的頂點集和邊集表示為 V(G) 和 E(G)。其中，E(G)可以是空集，如果它是空集，那么 G 只有頂點。

有向圖：邊上有箭頭，只能從箭頭的引出的結點到被指向的結點，不能逆著箭頭走。

無向圖：邊上無箭頭，可以隨便走。

結點的度：無向圖中與結點相連的邊的數(shù)量。

結點的入度：有向圖中以結點為終點的邊的數(shù)量。

結點的出度：有向圖中以結點為起點的邊的數(shù)量。

權值：可以理解為邊的長度。

連通：如果結點 U 和 V 之間通過若干個邊和結點能從 U 到達 V，則稱 U 和 V 連通。

回路：起點和終點相同的路徑。

完全圖：一個 n 階的完全無向圖含有 n*(n-1)/2 條邊，一個 n 階的完全有向圖含有 n*(n-1) 條邊。

稠密圖：一個邊數(shù)接近完全圖的圖。

稀疏圖：一個邊數(shù)遠少于完全圖的圖。

強連通分量：有向圖中任意兩點都連通的大子圖。特殊的，一個點也算一個強連通分量。

二維數(shù)組鄰接矩陣存儲

定義 int G[101][101];

G[i][j] 的值，表示點 i 到點 j 的邊的權值，定義如下，

G[i][j]{1或權值，0或無窮

從圖中某一頂點出發(fā)，系統(tǒng)的訪問圖中所有頂點，并且每個頂點只被訪問一次，這種操作叫做圖的遍歷。為了不重復訪問，我們使用一個數(shù)組 visit[] ，被訪問過就變成 true，反之 false。這兩種方法（廣度和深度優(yōu)先遍歷）時間復雜度都是 O(n*n)。

深度優(yōu)先遍歷和深度優(yōu)先搜索相似，它是先訪問一個點，再訪問與這個點相連的所有點，當這個點所有相連的點訪問完，再退回下一個點。

它基本不用，和廣度優(yōu)先搜索相似，和深度優(yōu)先遍歷相似，這里不講解。

如果一個圖存在一筆畫，則一筆畫的路徑叫做歐拉路，如果起點和終點相同，則這個路徑叫歐拉回路。

奇點是與一個點相連的邊數(shù)是奇數(shù)的點。我們有如下兩個定理：

（1）存在歐拉路的條件：圖是連通的，且有且只有兩個奇點。

（2）存在歐拉回路的條件：圖是聯(lián)通的，且有0個奇點。

#includeusing namespace std;
const int N=1000;
int p[N],q[N];
int n,m;
int sum=0,flag=0;
int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        q[a]++;//由于是無向圖需要把所有邊加上
        q[b]++;
        a=find(a),b=find(b);
        if(a!=b) p[a]=b;
    }
    for(int i=1;i<=n;i++) 
        if(p[i]==i) sum++;
       if(sum==1)
       {
           for(int i=1;i<=n;i++)
           {
               if(q[i]%2!=0)
                   flag++;
           }
       }
     else {cout<<"N"<

4 3
1 2
2 4
4 3

4 4 3 4

#include#include#includeusing namespace std;

#define MAXL 100010

int N, M, A[MAXL];
vectorG[MAXL]; //vector存圖 

void dfs(int x, int d) {
    if(A[x]) return; //訪問過 
    A[x] = d;
    for(int i=0; i