圖的遍歷及連通性

【問(wèn)題描述】
根據(jù)輸入的圖的鄰接矩陣A，判斷此圖的連通分量的個(gè)數(shù)。請(qǐng)使用鄰接矩陣的存儲(chǔ)結(jié)構(gòu)創(chuàng)建圖的存儲(chǔ)，并采用BFS優(yōu)先遍歷算法實(shí)現(xiàn)，否則不得分。
【輸入形式】
第一行為圖的結(jié)點(diǎn)個(gè)數(shù)n，之后的n行為鄰接矩陣的內(nèi)容，每行n個(gè)數(shù)表示。其中A[i][j]=1表示兩個(gè)結(jié)點(diǎn)鄰接，而A[i][j]=0表示兩個(gè)結(jié)點(diǎn)無(wú)鄰接關(guān)系。
【輸出形式】
輸出此圖連通分量的個(gè)數(shù)。
【樣例輸入】
5
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0
【樣例輸出】
2
【樣例說(shuō)明】
鄰接矩陣中對(duì)角線上的元素都用0表示。(單個(gè)獨(dú)立結(jié)點(diǎn)，即與其它結(jié)點(diǎn)都沒(méi)有邊連接，也算一個(gè)連通分量)

#include<iostream>
#define N 100
#include<queue>
using namespace std;
int matrix[N][N];

void bfs(int node, int matrix[N][N], int visited[N], int limit)
{
    queue<int> s;
    s.push(node);
    visited[node] = 1;
    while(!s.empty())
    {
        node = s.front();
        s.pop();
        int j = 0;
        for(j = 1; j < limit; j ++)
        {
            if(matrix[node][j] == 1 && visited[j] == 0)
            {
                s.push(j);
                visited[j] = 1;
            }
        }
    }
}

int main()
{
    int node;
    cin>>node;
    int i = 0;
    int j = 0;
    for(i = 1; i < node + 1; i ++) //創(chuàng)建鄰接矩陣，從一號(hào)位開(kāi)始存放
    {
        for(j = 1; j < node + 1; j++)
            cin>>matrix[i][j];
    }
    int res = 0;
    int visited[node + 1];
    for(i = 0; i < node + 1; i ++) visited[i] = 0;//初始化訪問(wèn)數(shù)組
    for(i = 1; i < node + 1; i ++)
    {
        if(visited[i] == 0)
        {
            bfs(i, &matrix[0], visited, node + 1); //二維數(shù)組傳第一行的地址
            res ++;
        }
    }
    cout<<res;
    return 0;
}

犯罪團(tuán)伙

【題目描述】

此題必須采用鄰接表的存儲(chǔ)結(jié)構(gòu)，建立圖的存儲(chǔ)，然后采用DFS遍歷實(shí)現(xiàn)求解。否則不給分。

警察抓到了 n 個(gè)罪犯，警察根據(jù)經(jīng)驗(yàn)知道他們屬于不同的犯罪團(tuán)伙，卻不能判斷有多少個(gè)團(tuán)伙，但通過(guò)警察的審訊，知道其中的一些罪犯之間相互認(rèn)識(shí)，已知同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識(shí)。有可能一個(gè)犯罪團(tuán)伙只有一個(gè)人。請(qǐng)你根據(jù)已知罪犯之間的關(guān)系，確定犯罪團(tuán)伙的數(shù)量。已知罪犯的編號(hào)從 1 至 n。

【輸入】

第一行：n（<=1000,罪犯數(shù)量），第二行：m（<5000，關(guān)系數(shù)量）以下若干行：每行兩個(gè)數(shù)：I 和 j，中間一個(gè)空格隔開(kāi)，表示罪犯 i 和罪犯 j 相互認(rèn)識(shí)。

【輸出】

一個(gè)整數(shù)，犯罪團(tuán)伙的數(shù)量。

【樣例輸入】

11

8

1 2

4 3

5 4

1 3

5 6

7 10

5 10

8 9

【輸出】

3

#include<iostream>
#define N 50
using namespace std;

int matrix[N][N];

void dfs(int human, int visited[N], int limit)
{
    visited[human] = 1;
    int j = 1;
    for(; j < limit; j ++)
    {
        if(matrix[human][j] == 1 && visited[j] == 0)
            dfs(j, visited, limit);
    }
}

int main()
{
    int human; //罪犯數(shù)量
    int relation; // 關(guān)系數(shù)量
    cin>>human>>relation;
    int i = 0;
    int j = 0;
    for(i = 0; i < N; i ++)
    {
        for(j = 0; j < N; j ++)
            matrix[i][j] = 0;
    }
    while(relation --)
    {
        int i, j;
        cin>>i>>j;
        matrix[i][j] = 1;
        matrix[j][i] = 1;
    }
    int visited[human + 1];
    for(i = 0; i < human + 1; i ++) visited[i] = 0;
    int res = 0;
    for(i = 1; i < human + 1; i++)
    {
        if(visited[i] == 0)
        {
            dfs(i, visited, human + 1);
            res ++;
        }
    }
    cout<<res;
    return 0;
}

圖形窗口問(wèn)題

【問(wèn)題描述】

在某圖形操作系統(tǒng)中，有N個(gè)窗口，每個(gè)窗口都是一個(gè)兩邊與坐標(biāo)軸分別平行的矩形區(qū)域。窗口的邊界上的點(diǎn)也屬于該窗口。窗口之間有層次的區(qū)別，在多于一個(gè)窗口重疊的區(qū)域里，只會(huì)顯示位于頂層的窗口里的內(nèi)容。

當(dāng)你點(diǎn)擊屏幕上一個(gè)點(diǎn)的時(shí)候，你就選擇了處于被點(diǎn)擊位置的最頂層窗口，并且這個(gè)窗口就會(huì)被移到所有窗口的最頂層，而剩余的窗口的層次順序不變。如果你點(diǎn)擊的位置不屬于任何窗口，則系統(tǒng)會(huì)忽略你這次點(diǎn)擊。

現(xiàn)在我們希望你寫(xiě)一個(gè)程序模擬點(diǎn)擊窗口的過(guò)程。

【輸入形式】

輸入的第一行有兩個(gè)正整數(shù)，即N和M。（1<=N<=10，1<=M<=10）接下來(lái)N行按照從最下層到最頂層的順序給出N個(gè)窗口的位置。每行包含四個(gè)非負(fù)整數(shù)x1,y1,x2,y2，表示該窗口的一對(duì)頂點(diǎn)坐標(biāo)分別為(x1,y1)和(x2,y2)。保證x1<x2，y1<y2。

接下來(lái)M行每行包含兩個(gè)非負(fù)整數(shù)x,y，表示一次鼠標(biāo)點(diǎn)擊的坐標(biāo)。題目中涉及到的所有點(diǎn)和矩形的頂點(diǎn)的x,y坐標(biāo)分別不超過(guò)2559和1439。

【輸出形式】

輸出包括M行，每一行表示一次鼠標(biāo)點(diǎn)擊的結(jié)果。如果該次鼠標(biāo)點(diǎn)擊選擇了一個(gè)窗口，則輸出這個(gè)窗口的編號(hào)（窗口按照輸入中的順序從1編號(hào)到N）；如果沒(méi)有，則輸出"IGNORED"（不含雙引號(hào)）。

【樣例輸入】

3 4

0 0 4 4

1 1 5 5

2 2 6 6

1 1

0 0

4 4

0 5

【樣例輸出】

2

1

1

IGNORED

【樣例說(shuō)明】

第一次點(diǎn)擊的位置同時(shí)屬于第1和第2個(gè)窗口，但是由于第2個(gè)窗口在上面，它被選擇并且被置于頂層。

第二次點(diǎn)擊的位置只屬于第1個(gè)窗口，因此該次點(diǎn)擊選擇了此窗口并將其置于頂層?，F(xiàn)在的三個(gè)窗口的層次關(guān)系與初始狀態(tài)恰好相反了。第三次點(diǎn)擊的位置同時(shí)屬于三個(gè)窗口的范圍，但是由于現(xiàn)在第1個(gè)窗口處于頂層，它被選擇。

最后點(diǎn)擊的(0,5)不屬于任何窗口。

【備注】2014年3月CCF-CSP考試真題第2題

#include<iostream>
#define N 20
using namespace std;

typedef struct
{
    int x;
    int y;
}point;

typedef struct
{
    point p1;
    point p2;
    int num;
}windows;

int main()
{
    windows w[N];
    int WindowsNum = 0;
    cin>>WindowsNum;
    int ClickNum = 0;
    cin>>ClickNum;
    int i = 1;
    while(1)
    {
        int x1, y1, x2, y2;
        cin>>x1>>y1>>x2>>y2;
        point a, b;
        a.x = x1;
        a.y = y1;
        b.x = x2;
        b.y = y2;
        windows p;
        p.p1 = a;
        p.p2 = b;
        p.num = i;
        w[i] = p;
        if(i == WindowsNum) break;
        i ++;
    }
    while(ClickNum --)
    {
        int x, y;
        cin>>x>>y;
        int pos = 0;
        for(pos = WindowsNum; pos > 0; pos --)
        {
            if(x >= w[pos].p1.x && y >= w[pos].p1.y && x <= w[pos].p2.x && y <= w[pos].p2.y)
            {
                cout<<w[pos].num<<endl;
                int i = 0;
                windows temp = w[pos];
                for(i = pos; i < WindowsNum; i ++)
                {
                    w[i] = w[i + 1];
                }
                w[WindowsNum] = temp;
                break;
            }
        }
        if(pos == 0) cout<<"IGNORED"<<endl;
    }
    return 0;
}

最小生成樹(shù)的權(quán)值之和

【問(wèn)題描述】
已知含有n個(gè)頂點(diǎn)的帶權(quán)連通無(wú)向圖，采用鄰接矩陣存儲(chǔ)，鄰接矩陣以三元組的形式給出，只給出不包括主對(duì)角線元素在內(nèi)的下三角形部分的元素，且不包括不相鄰的頂點(diǎn)對(duì)。請(qǐng)采用Prim算法，求該連通圖從1號(hào)頂點(diǎn)出發(fā)的最小生成樹(shù)的權(quán)值之和。
【輸入形式】
第一行給出結(jié)點(diǎn)個(gè)數(shù)n和三元組的個(gè)數(shù)count，以下每行給出一個(gè)三元組，數(shù)之間用空格隔開(kāi)。（注意這里頂點(diǎn)的序號(hào)是從1到n，而不是0到n-1，程序里要小心?。?br> 【輸出形式】
求解的最小生成樹(shù)的各條邊、邊的權(quán)值之和
【樣例輸入】
5 8
2 1 7
3 1 6
3 2 8
4 1 9
4 2 4
4 3 6
5 2 4
5 4 2
【樣例輸出】

1-3:6
3-4:6
4-5:2
4-2:4
18

【樣例說(shuō)明】
權(quán)值是正整數(shù)，可能很大，但不需要考慮整型溢出問(wèn)題

#include<iostream>
#define N 50
#define Max 999999
using namespace std;

int R[N][N];
typedef struct
{
    int adjvex;
    int loweight;
    int flag;
}Closedge;

int Min(Closedge * MTree, int limit)
{
    int min = 99999;
    int i = 0;
    int res = 0;
    for(i = 1; i <= limit; i ++)
    {
        if(MTree[i].loweight < min && MTree[i].flag == 1)
        {
            min = MTree[i].loweight;
            res = i;
        }
    }
    return res;
}

void Prim(int limit)
{
    int sum = 0;
    Closedge MTree[limit + 1];
    int i = 0;
    for(i = 1; i <= limit; i ++) //初始化
    {
        if(i != 1)
            MTree[i].adjvex = 1;
        MTree[i].flag = 1;
        MTree[i].loweight = R[1][i];
    }
    for(i = 2; i <= limit; i ++)
    {
        int MinId = Min(MTree, limit);
        cout<<MTree[MinId].adjvex<<'-'<<MinId<<':'<<MTree[MinId].loweight<<endl;
        sum += MTree[MinId].loweight;
        MTree[MinId].flag = 0;
        int j = 0;
        for(j = 2; j <= limit; j ++)
        {
            if(R[MinId][j] < MTree[j].loweight)
            {
                MTree[j].loweight = R[MinId][j];
                MTree[j].adjvex = MinId;
            }
        }
    }
    cout<<sum;
}

int main()
{
    int NodeNum;
    int RelationNum;
    cin>>NodeNum>>RelationNum;
    int i = 0;
    int j = 0;
    for(i = 1; i <= NodeNum; i++)
    {
        for(j = 1; j <= NodeNum; j ++)
        {
            R[i][j] = Max;
        }
    }
    while(RelationNum --)
    {
        int i, j, k;
        cin>>i>>j>>k;
        R[i][j] = k;
        R[j][i] = k;
    }
    Prim(NodeNum);
    return 0;
}

Jungle Roads

請(qǐng)用kruskal算法編程實(shí)現(xiàn)下面的問(wèn)題。
The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above. The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems.

Input

The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the alphabet, capitalized. Each data set is completed with n-1 lines that start with village labels in alphabetical order. There is no line for the last village. Each line for a village starts with the village label followed by a number, k, of roads from this village to villages with labels later in the alphabet. If k is greater than 0, the line continues with data for each of the k roads. The data for each road is the village label for the other end of the road followed by the monthly maintenance cost in aacms for the road. Maintenance costs will be positive integers less than 100. All data fields in the row are separated by single blanks. The road network will always allow travel between all the villages. The network will never have more than 75 roads. No village will have more than 15 roads going to other villages (before or after in the alphabet). In the sample input below, the first data set goes with the map above.

Output

The output is one integer per line for each data set: the minimum cost in aacms per month to maintain a road system that connect all the villages. Caution: A brute force solution that examines every possible set of roads will not finish within the one minute time limit.文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-461330.html

#include<iostream>
#define N 100
using namespace std;

typedef struct
{
    char node1;
    char node2;
    int weight;
}MTree;

int parent[N];

void Init(int limit)
{
    int i;
    for(i = 0; i <= limit; i ++)
    {
        parent[i] = i;
    }
}

int find(char a)
{
    int m = int(a) - 65;
    int root = int(a) - 65;
    while(root != parent[root]) root = parent[root];
    while(m != root)
    {
        int t = parent[m];
        parent[m] = root;
        m = t;
    }
    return root;
}

void unite(char a, char b)
{
    int m = find(a);
    int n = find(b);
    parent[n] = m;

}

void Sort(MTree tree[N], int limit)
{
    int i, j;
    for(i = 0; i <= limit; i ++)
    {
        int min = tree[i].weight;
        int minid = i;
        for(j = i + 1; j <= limit; j ++)
        {
            if(tree[j].weight < min)
            {
                min = tree[j].weight;
                minid = j;
            }
        }
        if(minid != i)
        {
            MTree temp = tree[i];
            tree[i] = tree[minid];
            tree[minid] = temp;
        }
    }
}

void Kruskal(MTree tree[N], int limit)
{
    int res = 0;
    int i = 0;
    for(i = 0; i <= limit; i ++)
    {
        if(find(tree[i].node1) != find(tree[i].node2))
        {
            unite(tree[i].node1, tree[i].node2);
            res += tree[i].weight;
            //cout<<tree[i].weight<<endl;
        }
    }
    cout<<res<<endl;
}

int main()
{
    MTree tree[N];
    int NodeNum;
    cin>>NodeNum;
    int i = 1;
    int count = -1;
    while(1)
    {
        char a1;
        cin>>a1;
        int RelationNum;
        cin>>RelationNum;
        while(RelationNum --)
        {
            count ++;
            char a2;
            cin>>a2;
            int r;
            cin>>r;
            tree[count].node1 = a1;
            tree[count].node2 = a2;
            tree[count].weight = r;
        }
        if(i == NodeNum - 1) break;
        i ++;
    }
    Init(count);
    Sort(tree, count);
    /*for(i = 0; i <= count; i ++)
    {
        cout<<tree[i].node1<<" "<<tree[i].node2<<" "<<tree[i].weight<<endl;
    }
    cout<<endl;*/
    Kruskal(tree, count);
    return 0;
}

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)第11周 ：（圖的遍歷及連通性 + 犯罪團(tuán)伙 + 圖形窗口問(wèn)題 + 最小生成樹(shù)的權(quán)值之和 + Jungle Roads ）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！