日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網(wǎng)站首頁 編程語言 正文

C++實現(xiàn)圖的遍歷算法(DFS,BFS)的示例代碼_C 語言

作者：小張﹉ ? 更新時間： 2022-09-17 編程語言

圖的定義

圖由頂點集V(G)和邊集E(G)組成，記為G=(V,E)。其中E(G)是邊的有限集合，邊是頂點的無序?qū)Γo向圖）或有序?qū)Γㄓ邢驁D）。對于有向圖來說，E(G)是有向邊（也稱弧(Arc)）的有限集合，弧是頂點的有序?qū)Γ洖?lt;v,w>，v、w是頂點，v為弧尾（箭頭根部），w為弧頭（箭頭處）。對于無向圖來說，E(G)是邊的有限集合，邊是頂點的無序?qū)Γ洖?v, w)或者(w, v)，并且(v, w)=(w,v)。

圖的相關術(shù)語

①頂點(Vertex)：圖中的數(shù)據(jù)元素。

②頂點v的度：與v相關聯(lián)的邊的數(shù)目；

③頂點v的出度：以v為起點有向邊數(shù)；

④頂點v的入度：以v為終點有向邊數(shù)。

⑤邊：頂點之間的邏輯關系用邊來表示，邊集可以是空的。

⑥無向邊(Edge)：若頂點V1到V2之間的邊沒有方向，則稱這條邊為無向邊。

⑦無向圖(Undirected graphs)：圖中任意兩個頂點之間的邊都是無向邊。（A,D）=（D,A）

⑧有向邊：若從頂點V1到V2的邊有方向，則稱這條邊為有向邊，也稱弧(Arc)。用<V1,V2>表示，V1為狐尾(Tail)，V2為弧頭(Head)。（V1，V2）≠（V2，V1）。

⑨有向圖(Directed graphs)：圖中任意兩個頂點之間的邊都是有向邊。

注意：無向邊用“（）”，而有向邊用“< >”表示。

⑩簡單圖：圖中不存在頂點到其自身的邊，且同一條邊不重復出現(xiàn)。

?無向完全圖：無向圖中，任意兩個頂點之間都存在邊。

?有向完全圖：有向圖中，任意兩個頂點之間都存在方向互為相反的兩條弧。

?稀疏圖：有很少條邊。

?稠密圖：有很多條邊。

?權(quán)（Weight）：與圖的邊或弧相關的數(shù)。

?網(wǎng)（Network）：帶權(quán)的圖。

?連通圖：圖中任意兩個頂點都是連通的。

?極大連通子圖：該子圖是G連通子圖，將G的任何不在該子圖的頂點加入，子圖將不再連通。

?極小連通子圖：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖都將不再連通。

圖的創(chuàng)建(鄰接矩陣)---結(jié)構(gòu)體

typedef struct
{
    //用來存放頂點
    int vexs[MAX];
    //二維數(shù)組：用來存放兩點之間的關系
    int arcs[MAX][MAX];
    //圖的頂點數(shù)和邊數(shù)
    int vexsum, arcsnum;
}AMGraph,*StrAMGraph;

圖的創(chuàng)建(鄰接矩陣)---鄰接矩陣的創(chuàng)建

int locate(AMGraph&G, int n)
{
    for (int i = 0; i < G.vexsum; i++)
    {
        if (G.vexs[i] == n)
        {
            return i;
        }
    }
}
 
//創(chuàng)建鄰接矩陣
void Creat(AMGraph&G)
{
    int v1 = 0, v2 = 0, w = 0;
    cin >> G.vexsum >> G.arcsnum;
    for (int i = 0; i < G.vexsum; i++)
    {
        cin >> G.vexs[i];
    }
    for (int i = 0; i < G.vexsum; i++)
    {
        for (int j = 0; j < G.vexsum; j++)
        {
            G.arcs[i][j] = 0;
        }
    }
    for (int k = 0; k < G.arcsnum; k++)
    {
        cin >> v1 >> v2 >> w;
        int i = locate(G, v1);
        int j = locate(G, v2);
        G.arcs[i][j] = w;
    }
}

圖的創(chuàng)建(鄰接表)---結(jié)構(gòu)體

typedef struct ArcNode
{
    int Adjust;
    struct ArcNode *next;
}AcrNode,*StrAcrNode;
 
 
typedef struct
{
    int data;
    StrAcrNode next;
}HeadNode, *StrHeadNode;
 
 
typedef struct 
{
    HeadNode arr[MAX];
    int acsrnum, vexsnum;
}ALGraph, *StrALGraph;

圖的創(chuàng)建(鄰接表)---鄰接表的創(chuàng)建

int locate1(ALGraph&G, int n)
{
    for (int i = 0; i < G.vexsnum; i++)
    {
        if (G.arr[i].data == n)
        {
            return i;
        }
    }
}
 
void CreatALGraph(ALGraph&G)
{
    int v1 = 0, v2 = 0, w = 0;
    cin >> G.vexsnum >> G.acsrnum;
    for (int i = 0; i < G.vexsnum; i++)
    {
        cin >> G.arr[i].data;
        G.arr[i].next = NULL;
    }
    for (int k = 0; k < G.acsrnum; k++)
    {
        cin >> v1 >> v2;
        int i = locate1(G, v1);
        int j = locate1(G, v2);
        StrAcrNode p1;
        p1 = new AcrNode;
        p1->next = G.arr[i].next;
    }
}

對鄰接矩陣進行深度優(yōu)先遍歷

//對鄰接矩陣進行深度優(yōu)先遍歷
void DFS(AMGraph&G, int n)
{
    cout << G.vexs[n] << " ";
    visit[n] = 1;
    for (int i = 0; i < G.vexsum; i++)
    {
        if (G.arcs[n][i] != 1 && visit[i] != 1)
        {
            DFS(G, G.arcs[n][i]);
        }
    }
}

對鄰接矩陣進行廣度優(yōu)先遍歷

queue<int> qu;
//對鄰接矩陣進行廣度優(yōu)先遍歷
void BFS(AMGraph&G, int n)
{
    cout << G.vexs[n] << " ";
    qu.push(n);
    while (!qu.empty())
    {
        int m = qu.front();
        qu.pop();
        for (int i = 0; i < G.vexsum; i++)
        {
            if (visit[i] != 1 && G.arcs[m][i] != 1)
            {
                cout << G.vexs[i] << " ";
                visit[i] = 1;
                qu.push(i);
            }
        }
    }
}

對鄰接表進行深度優(yōu)先遍歷?

void DFS1(ALGraph&G, int n)
{
    cout << G.arr[n].data << " ";
    visit3[n] = 1;
    StrAcrNode p1;
    p1 = G.arr[n].next;
    while (p1)
    {
        int w = p1->Adjust;
        if (visit3[w] != 1)
        {
            DFS1(G, w);
        }
        p1 = p1->next;
    }
}
 
queue<int> qu1;

對鄰接表進行廣度優(yōu)先遍歷?

queue<int> qu1;
void BFS(ALGraph&G, int n)
{
    cout << G.arr[n].data << " ";
    visit4[n] = 1;
    qu1.push(n);
    StrAcrNode p1;
    p1 = G.arr[n].next;
    while (!qu1.empty())
    {
        qu1.pop();
        int w = p1->Adjust;
        while (p1)
        {
            if (visit4[w] != 1)
            {
                qu1.push(w);
                visit4[w] = 1;
            }
            p1 = p1->next;
        }
    }
}

整體代碼

#include<iostream>
#include<queue>
using namespace std;
const int MAxInt = 10;
int visit[MAxInt];
 
typedef struct
{
    int vexs[MAxInt];
    int arcs[MAxInt][MAxInt];
    int arcnum, vexsnum;
}AMGraph;
 
int locate(AMGraph&G, int n)
{
    for (int i = 0; i < G.vexsnum; i++)
    {
        if (G.vexs[i] == n)
        {
            return i;
        }
    }
}
 
void Creat(AMGraph&G)
{
    int v1 = 0, v2 = 0, w = 0;
    cin >> G.vexsnum >> G.arcnum;
    for (int i = 0; i < G.vexsnum; i++)
    {
        cin >> G.vexs[i];
    }
    for (int i = 0; i < G.vexsnum; i++)
    {
        for (int j = 0; j < G.vexsnum; j++)
        {
            G.arcs[i][j] = MAxInt;
        }
    }
    for (int k = 0; k < G.arcnum; k++)
    {
        cin >> v1 >> v2 >> w;
        int i = locate(G, v1);
        int j = locate(G, v2);
        G.arcs[i][j] = w;
        G.arcs[j][i] = w;
    }
}
 
 
 
queue<int> qu;
void BFS(AMGraph G, int v)
{
    cout << G.vexs[v];
    qu.push(v);
    visit[v] = 1;
    while (!qu.empty())
    {
        int w = qu.front();
        qu.pop();
        for (int i = 0; i < G.vexsnum; i++)
        {
            if (visit[i] != 1 && G.arcs[w][i] != MAxInt)
            {
                cout << G.vexs[i] << " ";
                visit[i] = 1;
                qu.push(i);
            }
        }
    }
}
 
int main()
{
    AMGraph G;
    Creat(G);
    cout << "對圖進行廣度優(yōu)先遍歷的結(jié)果為" << endl;
    BFS(G, 1);
    return 0;
}

注意 ：這里的代碼是創(chuàng)建一個鄰接矩陣來對圖進行廣度優(yōu)先遍歷，對圖進行深度優(yōu)先遍歷以及臨界表實現(xiàn)對圖進行廣度優(yōu)先遍歷，對圖進行深度優(yōu)先遍歷大家都可以通過上面的代碼塊進行自由組合實現(xiàn)，這里就不進行一一實現(xiàn)。

結(jié)果展示

原文鏈接：https://blog.csdn.net/weixin_64067830/article/details/125965460

欄目分類
最近更新