演算法筆記學習（4）---鄰接矩陣、鄰接表、拓撲排序-有解無憂

鄰接矩陣

??設圖G(V,E)的頂點標號為0, 1,…,N-1,那么可以令二維陣列G[N] [N]的兩維分別表示圖的頂點標號，即如果G[ i ] [ j ]為1,則說明頂點i和頂點j之間有邊;如果G[i] [j]]為0,則說明頂點i和頂點j之間不存在邊，而這個二維陣列G[ ] [ ]則被稱為鄰接矩陣，另外，如果存在邊權，則可以令G[ i ] [ j ]存放邊權，對不存在的邊可以設邊權為0、-1或是一個很大的數，
??圖10-4是一個作為舉例的無向圖以及對應的鄰接矩陣(邊權為0表示不存在邊)，顯然對無向圖來說，鄰接矩陣是一個對稱矩陣，
在這里插入圖片描述
??雖然鄰接矩陣比較好寫，但是由于需要開一個二維陣列，如果頂點數目太大，便可能會超過題目限制的記憶體，因此鄰接矩陣只適用于頂點數目不太大(一般不超過1000)的題目，

鄰接表

??設圖G(V,E)的頂點編號為0,1,…,N-1,每個頂點都可能有若干條出邊，如果把同一個頂點的所有出邊放在一個串列中，那么N個項點就會有N個串列(沒有出邊，則對應空表)，這N個串列被稱為圖G的鄰接表，記為Adj[N], 其中Adj[i]存放頂點i的所有出邊組成的串列，這樣Adj[0], Adj[1],…, Adj[N-1]就分別都是一個串列，由于串列可以用鏈表實作，如果畫出圖10-4對應的鄰接表，就會得到圖10-5，其中Adj[0]用鏈表連接了兩個結點，每個結點存放一條邊的資訊(括號外的數字是邊的終點編號，括號內的數字是邊權)，于是0號頂點有兩條出邊：一條的終點為1號頂點(邊權為2)；另一條邊的終點為4號頂點(邊權為1)，而對Adj[4]來說，它表示4號頂點的三條出邊的資訊，這三條出邊的終點分別是0號頂點、1號頂點、3號頂點，邊權分別為1、2、1，
在這里插入圖片描述

??對初學者來說，可能會不太容易很快就熟練使用鏈表來實作鄰接表，因此此處介紹另一種更為簡單的工具來實作鄰接表: vector ，它能讓初學者更快上手并易于使用，且不易出錯，

??由于vector有變長陣列之稱，因此可以開個vector 陣列Adj[N]，其中N為頂點個數，這樣每個Adj[i]就都是一個變長陣列vector，使得存盤空間只與圖的邊數有關，

??如果鄰接表只存放每條邊的終點編號，而不存放邊權，則vector中的元素型別可以直接定義為int型，如下所示：

vector<int> Adj[N];

??圖10-6為把圖10-5中的鄰接表采用vector 陣列進行存盤的情況(只存放邊的終點編號)，

在這里插入圖片描述

??如果想添加一條從1號頂點到達3號頂點的有向邊，只需要在Adj[1]中添加終點編號3即可，代碼如下所示(如果是無向邊，就再添加一條從3號頂點到達1號頂點的有向邊)：

Adj[1].push_back(3);

??如果需要同時存放邊的終點編號和邊權，那么可以建立結構體Node，用來存放每條邊的終點編號和邊權，代碼如下所示：

struct Node{
	int v;//邊的終點編號
	int w;//邊權
};

??這樣vector鄰接表中的元素型別就是Node型的，如下所示：

vector<Node> Adj[N];

??此時如果想要添加從1號到達3號頂點的有向邊，邊權為4，就可以定義一個Node型的臨時變數temp，令temp.v=3、temp.w=4，然后把temp加入到Adj[1]中即可，代碼如下所示：

Node temp;
temp.v = 3;
temp.w = 4;
Adj[1].push_back(temp);

??當然，更快的做法是定義結構體Node的建構式，代碼如下所示：

struct Node{
	int v,w;
	Node(int _v ,int _w) : (v)_v , w(_w) {}//建構式，注意沒有分號
};

??這樣就能不定義臨時變數來實作加邊操作，代碼如下所示：

Adj[1].push_back(Node(3,4));

??于是就可以使用vector來很方便地實作鄰接表，在一些**頂點數目較大**（一般頂點個數在1000以上）的情況下，一般都需要使用鄰接表而非鄰接矩陣來存盤圖，

拓撲排序

??如果一個有向圖的任意項點都無法通過一些有向邊回到自身，那么稱這個有向圖為有向無環圖(Directed Acyclic Graph, DAG)，圖10-56給出了幾個DAG的例子，

在這里插入圖片描述

??拓撲排序是將有向無環圖G的所有項點排成一個線性序列，使得對圖G中的任意兩個項點u、V，如果存在邊u->V，那么在序列中u一定在V 前面，這個序列又被稱為拓撲序列，

??以圖10-57 數學專業的某幾門課程的學習先后順序為例(為了方便閱讀，圖中省略了一部分關系)，可以獲知，“數學分析”是“復變函式"、“常微分方程”、“計算方法"的先導課程，“復變函式”是“實變函式”和“泛函分析”的先導課程，“實變函式”又是“泛函分析”的先導課程，等等，顯然，對一門課來說，必須要先學習它的先導課程才能很好地學習這門課，而且先導課程之間不能夠形成環(例如如果“泛函分析”同時又是“空間決議幾何”的先導課程，就亂套了)，

在這里插入圖片描述

??同時還會發現，如果兩門課程之間沒有直接或間接的先導關系，那么這兩門學習的先后順序是任意的(例如“復變函式”與“計算方法"的學習順序就是任意的)，于是可以把上面的課程排成一個學習的先后序列，使得這個序列中的課程順序滿足圖10-57的先導課程順序，如圖10-58所示，

在這里插入圖片描述

??這樣讀者應當能理解什么是拓撲排序了，下面講解求解拓撲序列的方法，通過上面的例子會發現，如果某一門課沒有先導課程或是所有先導課程都已經學習完畢，那么這門課就可以學習了，如果有多門這樣的課，它們的學習順序任意，對應到圖中，這個做法可以抽象為以下步驟:

①定義一個佇列Q，并把所有入度為0的結點加入佇列，

②取隊首結點，輸出，然后刪去所有從它出發的邊，并令這些邊到達的項點的入度減1，如果某個頂點的入度減為0,則將其加入佇列，

③反復進行②操作，直到佇列為空，如果佇列為空時入過隊的結點數目恰好為N，說明拓撲排序成功，圖G為有向無環圖；否則，拓撲排序失敗，圖G中有環，

??可使用鄰接表實作拓撲排序，顯然，由于需要記錄結點的入度，因此需要額外建立一個陣列inDegree[MAXV]，并在程式一開始讀入圖時就記錄好每個結點的入度，接下來就只需要按上面所說的步驟進行實作即可，拓撲排序的代碼如下：

vector<int> G[MAXV];//鄰接表
int n, m, inDegree[MAXV];//頂點數、入度
//拓撲排序
bool topologicalSort()
{
	int num = 0;//記錄加入拓撲序列的頂點數
	queue<int> q;
	for(int i=0;i<n;i++)
	{
		if(inDegree[i]==0)
		{
			q.push(i);//將所有入度為0的頂點入隊
		}
	}
	while(!q.empty())
	{
		int u = q.front();//取隊首頂點
		//printf("%d",u);//此處可輸出頂點u，作為拓撲序列中的頂點
		q.pop();
		for(int i=0;i<G[u].size();i++)
		{
			int v = G[u][i];//u的后繼節點v
			inDegree[v]--;//頂點v的入度減1
			if(inDegree[v]==0) //頂點v的入度減為0則入隊
			{
				q.push(v);
			}
		}
		G[u].clear();//清空頂點u的所有出邊（如無必要可不寫）
		num++;
	}
	if(num == n) return true; //加入拓撲序列的頂點數為n，說明拓撲排序成功
	else return false; //加入拓撲序列的頂點數小于n，說明拓撲排序失敗
}

??拓撲排序的很重要的應用就是判斷一個給定的圖是否是有向無環圖，正如上面的代碼，如果topologicalSort()函式回傳true,則說明拓撲排序成功，給定的圖是有向無環圖；否則，說明拓撲排序失敗，給定的圖中有環，
最后指出，如果要求有多個入度為0的項點，選擇編號最小的頂點，那么把queue改成priority_ queue, 并保持隊首元素(堆項元素)是優先佇列中最小的元素即可(當然用set也是可以的)，

實體：CCFCSP認證 202009-3 點亮數字人生

題目詳情->點亮數字人生

用拓撲排序實作，代碼如下：

#include<iostream>
#include<vector>
#include<string>
#include<string.h>
#include<queue>
#include<algorithm>
#include<cstdio>
using namespace std;

const int MAXV = 505;

struct Node{
    int v;//邊的終點編號
    Node(int _v):v(_v) {} //建構式
};

vector<Node> G[MAXV];//鄰接表
int w[MAXV];//邊權重
string type[MAXV];//器件型別
int inDegree[MAXV]={0};//入度
bool initV[MAXV]={false};//判斷是否初始化
vector<int> test_in[10005];
vector<int> test_out[10005];

bool topologicalSort(int m,int n)
{
    int num = 0;//記錄加入拓撲序列的頂點數
    queue<int> q;
    int temp_inDegree[MAXV];//存盤臨時入度
    memcpy(temp_inDegree,inDegree,(m+n)*sizeof(int));

    for(int i=0;i<m+n;i++)
    {
        if(temp_inDegree[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i=0;i<G[u].size();i++)
        {
            int v = G[u][i].v;
            temp_inDegree[v]--;
            if(temp_inDegree[v]==0) q.push(v);
        }
        num++;
    }
    if(num == m+n) return true;
    else return false;
}

void calculate(int m,int n)
{
    queue<int> q;
    int temp_inDegree[MAXV];
    memcpy(temp_inDegree,inDegree,(m+n)*sizeof(int));

    for(int i=0;i<m+n;i++)
    {
        if(temp_inDegree[i]==0) q.push(i);
    }
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i=0;i<G[u].size();i++)
        {
            int v = G[u][i].v;
            temp_inDegree[v]--;

            if(!initV[v])
            {
                w[v] = w[u];
                if(type[v] == "NOT") w[v] = !w[v];
                initV[v] = true;
            }
            else
            {
                if(type[v] == "AND" || type[v] == "NAND") w[v] &= w[u];
                else if(type[v] == "OR" || type[v] == "NOR") w[v] |= w[u];
                else if(type[v] == "XOR") w[v] ^= w[u];
            }

            if(temp_inDegree[v] == 0)
            {
                if(type[v] == "NAND" || type[v] == "NOR") w[v] = !w[v];
                q.push(v);
            }
        }
    }
}

int main()
{
    int q, m, n;
    cin>>q;
    while(q--)
    {
        //初始化
        for(int i = 0;i < MAXV;i++)
        {
            for(vector<Node>::iterator j = G[i].begin();j != G[i].end();)
            {
                j = G[i].erase(j);
            }
        }
        memset(inDegree, 0, sizeof(inDegree));
        fill(initV, initV + MAXV, false);
        for(int i = 0;i < MAXV;i++)
        {
            type[i].clear();
        }
        for(int i = 0;i < 10005;i++)
        {
            for(vector<int>::iterator j = test_in[i].begin();j != test_in[i].end();)
            {
                j = test_in[i].erase(j);
            }
        }
        for(int i = 0;i < 10005;i++)
        {
            for(vector<int>::iterator j = test_out[i].begin();j != test_out[i].end();)
            {
                j = test_out[i].erase(j);
            }
        }
        cin>>m>>n;//輸入個數，器件個數
        for(int num = m;num < n + m;num++)
        {
            string FUNC;//器件描述
            int k;
            cin>>FUNC;
            type[num] = FUNC;
            cin>>k;
            for(int i = 0;i < k;i++)
            {
                string L;
                cin>>L;
                int startPoint = atoi(L.substr(1, L.length() - 1).c_str()) - 1;//計算起始點編號
                if(L[0] != 'I')
                {//如果是輸出點，則加上輸入點的偏移
                    startPoint += m;
                }
                G[startPoint].push_back(Node(num));//構造圖
                inDegree[num]++;//計算入度
            }
        }
        int s;//運算次數
        cin>>s;
        for(int i = 0;i < s;i++)
        {//輸入資料
            for(int j = 0;j < m;j++)
            {
                int input;
                cin>>input;
                test_in[i].push_back(input);
            }
        }
        for(int i = 0;i < s;i++)
        {//輸出資料
            int out_num;
            cin>>out_num;
            while(out_num--)
            {
                int output;
                cin>>output;
                output = output + m - 1;
                test_out[i].push_back(output);
            }
        }
        if(topologicalSort(m, n) == false)
        {//有環
            printf("LOOP\n");
        }
        else
        {//無環
            for(int i = 0;i < s;i++)
            {
                memset(w, 0, sizeof(w));
                fill(initV, initV + MAXV, false);
                for(int j = 0;j < test_in[i].size();j++)
                {//給初始輸入點賦值
                    w[j] = test_in[i][j];
                }
                //計算點權
                calculate(m, n);

                for(int j = 0; j < test_out[i].size();j++)
                {
                    if(j != 0) cout<<" ";
                    cout<<w[test_out[i][j]];
                }
                cout<<endl;

            }
        }
    }
    return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/254931.html

標籤：其他

上一篇：教你如何自己動手用Docker搭建一個etcd集群（附etcdctl命令說明）

下一篇：計算機網路100問