圖的存儲結(jié)構(gòu)——鄰接矩陣與鄰接表

1 概述#

簡單的說，圖由表示數(shù)據(jù)元素的集合V和表示數(shù)據(jù)之間關(guān)系的集合E組成，記為G=<V,E>。圖又分為有向圖與無向圖。下面是圖的一些基本元素：

  • 邊(edge)：頂點(diǎn)的序偶。
  • 頂點(diǎn)(vertex)：數(shù)據(jù)元素。
  • 權(quán)重(weight)：用來表示一個頂點(diǎn)到另一個頂點(diǎn)的距離、代價、耗費(fèi)等。
  • 度(degree)：與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目，入度、出度等等。
無向圖G1與有向圖G2

圖的基本類型常使用的有相鄰矩陣與鄰接表。下面將從兩方面介紹圖的儲存結(jié)構(gòu)與基本操作。

2 圖的相鄰矩陣儲存類型#

圖的相鄰矩陣或鄰接矩陣表示定點(diǎn)之間的鄰接關(guān)系，即表示頂點(diǎn)之間有邊或沒有邊的情況。如下圖則是無向圖G1和有向圖G2的鄰接矩陣。


(a)無向圖G1的鄰接矩陣 (b)有向圖G2的鄰接矩陣
  • 相鄰矩陣類型定義

對于有向圖，相鄰矩陣不一定對稱。因為如果相鄰矩陣第i行第j列的元素為1，則表示有一條從頂點(diǎn)vi到頂點(diǎn)vj的弧，而此時不一定存在由頂點(diǎn)vj到頂點(diǎn)vi的弧。

 /*圖的相鄰矩陣儲存類型定義*/
#define MaxVertexNum 100 /*最大頂點(diǎn)數(shù)設(shè)為100*/
typedef enum{FALSE,TRUE} Boolean;
Boolean mark[MaxVertexNum];

typedef char VertexType; /*頂點(diǎn)類型設(shè)為字符型*/
typedef int EdgeType; /*邊的權(quán)值設(shè)為整型*/

typedef struct {
    VertexType vexs[MaxVertexNum]; /*頂點(diǎn)表*/
    EdgeType edges[MaxVertexNum][MaxVertexNum]; /*鄰接矩陣，即邊表*/
    int numVertex,numEdge; /*頂點(diǎn)數(shù)和邊數(shù)*/
}Mgragh,*MGragh; /*Maragh 是以鄰接矩陣存儲的圖類型*/
  • 圖創(chuàng)建

首先定義相鄰矩陣的尺寸，即定點(diǎn)數(shù)和邊數(shù)。
輸入每條邊信息，vi為初始點(diǎn)，vj為終止點(diǎn)。將鄰接表中的edges[i][j]設(shè)置為1，代表起點(diǎn)為i，終點(diǎn)為j，存在一條邊。


void CreateMGraph(MGragh G){/*建立有向圖G 的鄰接矩陣存儲*/
int i,j,k,w;
char ch;
cout<<"請輸入頂點(diǎn)數(shù)和邊數(shù)";
cin>>i>>j;
G->numVertex=i;
G->numEdge=j;

cout<<"請輸入頂點(diǎn)信息:"<<endl;

for (i=0;i<G->numVertex;i++) {cout<<"第"<<i<<"個點(diǎn):";cin>>G->vexs[i];} /*輸入頂點(diǎn)信息，建立頂點(diǎn)表*/
for (i=0;i<G->numVertex;i++)
    for (j=0;j<G->numVertex;j++) 
        G->edges[i][j]=0; /*初始化鄰接矩陣*/

cout<<"請輸入每條邊對應(yīng)的兩個頂點(diǎn)的序號:\n";

for (k=0;k<G->numEdge;k++){
    cout<<"v<i,j>:";
    cin>>i>>j; /*輸入e 條邊，建立鄰接矩陣*/
        G->edges[i][j]=1;
            }
}
  • 判斷邊類

FirstEdge即返回以v為頂點(diǎn)的第一條邊。它的想法是：返回以頂點(diǎn)v的編號的相鄰矩陣行，從j=0開始遍歷，直到搜索到矩陣元素為1時，表示i到j(luò)有一條邊，于是返回此條邊。

NextEdge即返回以v為頂點(diǎn)的下一條邊。當(dāng)輸入邊edge時，將返回以edge.from的編號相同的矩陣行，從j=edge.to+1開始遍歷，直到搜索到矩陣元素為1時，表示i到j(luò)有一條邊，返回此邊。


Edge FirstEdge(MGragh G,int oneVertex){
   Edge myEdge;
   myEdge.from=oneVertex;
   for(int i=0;i<G->numVertex;i++){
       if(G->edges[oneVertex][i]!=0){
           myEdge.to=i;
           myEdge.weight=G->edges[oneVertex][i];
           break;
       }
   }
   return myEdge;
}

Edge NextEdge(MGragh G,Edge preEdge){
   Edge myEdge;
   myEdge.from =preEdge.from ;
   if(preEdge.to <G->numVertex){
       for(int i=preEdge.to+1;i<G->numVertex;i++){
           if(G->edges[preEdge.from][i]!=0){
               myEdge.to =i;
               myEdge.weight =G->edges[preEdge.from ][i];
               break;
           }
       }
   }
   return myEdge;
}

bool isEdge(MGragh G, Edge myEdge){
   int test=0;
   for(int i=0;i<G->numVertex;i++){
       if(myEdge.to>=0&&G->edges[myEdge.from][myEdge.to]==1)return true;
   }
   return false;
}
  • 兩種周游算法

以有向圖G2為例：

深度優(yōu)先搜索的周游算法如下：假設(shè)從v0點(diǎn)出發(fā)，首先將v0的標(biāo)志位設(shè)置為TRUE，然后從v0的第一條邊出發(fā)，尋找第一條邊的終點(diǎn)v2。因為v2為被訪問過，因此將v2標(biāo)志位設(shè)置為TRUE。從v2出發(fā)，尋找v2的第一條邊終點(diǎn)為v3。因為v3為被訪問過，因此設(shè)v3的標(biāo)志位為TRUE。從v3出發(fā)，尋找v3的第一條邊終點(diǎn)為v0，標(biāo)志位為TRUE說明已被訪問過。返回上一個頂點(diǎn)v2，尋找v2的nextEdge，無。返回v0，尋找v0的nextEdge，為v1，標(biāo)識v1為TRUE。遍歷完畢。

廣度優(yōu)先算法的周游如下：假設(shè)從v0出發(fā)。首先將v0的標(biāo)志位設(shè)置為TRUE，將v0入隊。因為隊列不為空，所以取出front，設(shè)置為u，同時pop掉front。尋找v0的第一條邊的終點(diǎn)v2。輸出v2，并將其push入隊列；尋找v0的第二條邊的終點(diǎn)v1,，輸出v1，并將其push入隊列；尋找v0的第三條邊的終點(diǎn)，無。返回取出front，將v2設(shè)置為u，pop掉它。尋找v2的第一條邊v3，輸出v3并將其push如隊列；尋找v2的第二條邊，無。返回取出front，將v1設(shè)置為u，pop掉它。尋找v1的第一條邊，無。返回取出front，將v3設(shè)置為u，pop掉它，尋找v3的第一條邊v0，因為以被訪問，因此跳過；尋找v3的第二條邊，無。算法結(jié)束。

//深度優(yōu)先周游    
void DFS(MGragh G, int v){
    mark[v]=TRUE;
    cout<<G->vexs[v];
    for(Edge e=FirstEdge(G,v);isEdge(G,e);e=NextEdge(G,e)){
        if(mark[e.to]==FALSE) DFS(G,e.to);
    }
}

void DFSM(MGragh G,int v){
    for(int i=0;i<G->numVertex;i++){
        mark[i]=FALSE;
    }
    DFS(G,0);
}

//廣度優(yōu)先周游
void BFS(MGragh G, int v){
    for(int i=0;i<G->numVertex;i++){
        mark[i]=FALSE;
    }
    using std::queue;
    queue<int>Q;
    cout<<G->vexs[v];
    mark[v]=TRUE;
    Q.push(v);
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(Edge e=FirstEdge(G,u);isEdge(G,e);e=NextEdge(G,e))
            if(mark[e.to]==FALSE){
                cout<<G->vexs[e.to];
                mark[e.to]=TRUE;
                Q.push(e.to);
            }
    }
}

3 圖的鄰接表儲存類型#

當(dāng)圖中的邊數(shù)較少時，相鄰矩陣就會出現(xiàn)大量的0元素，儲存這些0元素將消耗大量的儲存空間。
鄰接表表示法是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，由一個順序儲存的頂點(diǎn)表和n個鏈表儲存的邊表組成。頂點(diǎn)表目有兩個域：頂點(diǎn)數(shù)據(jù)域和指向此頂點(diǎn)邊表指針域。邊表把依附于同一個頂點(diǎn)vi的邊（即相鄰矩陣中同一行的非0元素）組織成一個單鏈表。邊表中的每一個表目都代表一條邊，由兩個主要的域組成：與頂點(diǎn)vi鄰接的另一個頂點(diǎn)的序號、指向邊表中下一個邊表的目的指針。
頂點(diǎn)結(jié)點(diǎn)和邊結(jié)點(diǎn)的結(jié)構(gòu)如下：

Paste_Image.png

與鄰接矩陣儲存類型相似，鄰接表的基本函數(shù)依然包括FirstEdge，NextEdge和isEdge。這里不再重復(fù)，下面只給出廣度周游和深度周游算法。

  • 鄰接表類型定義
using namespace std;
#define MAX_VERTEXT_NUM 20
typedef enum{FALSE,TRUE} Boolean;
Boolean mark[MAX_VERTEXT_NUM];

typedef struct edge{     /*邊定義*/
    int from,to,weight;
}Edge,*Edged;

typedef struct ArcNode{     /*邊結(jié)點(diǎn)定義*/
    int adjvex;
    struct ArcNode *nextArc;
    int weight;
}ArcNode;

typedef struct VNode{     /*頂點(diǎn)定義*/
    char data;
    ArcNode *firstArc;
}VNode, AdjList[MAX_VERTEXT_NUM];

typedef struct Indegree{     /*每個點(diǎn)的入度*/
    int indegree;
}Indegree,indegree[MAX_VERTEXT_NUM];

typedef struct{     /*圖定義*/
    AdjList verTices;
    int vexNum;
    int arcNum;
    int kind;
    indegree Indegree;
}ALGraph;
  • 圖的鄰接表儲存類型建立

首先輸入頂點(diǎn)和邊的個數(shù)，同時申請頂點(diǎn)個數(shù)的結(jié)點(diǎn)空間。
每次輸入邊的鄰接關(guān)系時i-j時，首先申請一個邊結(jié)點(diǎn)空間給，結(jié)點(diǎn)的adjvex為j，nextarc為頭結(jié)點(diǎn)firstarc的nextarc，頭結(jié)點(diǎn)的firstarc變?yōu)榇薺結(jié)點(diǎn)arcnode。

鄰接表插入頂點(diǎn)
void CreateGraph(ALGraph *G)
{
    int i,j,k,weight;
    ArcNode *arcNode;
    printf_s("請輸入頂點(diǎn)數(shù)和邊數(shù)：");
    cin>>G->vexNum;
    cin>>G->arcNum;
    //建立頂點(diǎn)表
    printf_s("建立頂點(diǎn)表\n");
    for (i = 0; i < G->vexNum; i++)
    {
        printf_s("請輸入第%d個頂點(diǎn):", i);
        cin>>G->verTices[i].data;
        arcNode = (ArcNode *)malloc(sizeof(ArcNode));
        arcNode->adjvex=i;
        arcNode->nextArc=NULL;
        G->verTices[i].firstArc=arcNode;
        G->Indegree[i].indegree=0;
    }
    //建立邊表
    printf_s("建立邊表\n");
    for (k = 0; k < G->arcNum; k++)
    {
        printf_s("請輸入（vi-vj）的頂點(diǎn)對序號");
        cin>>i;
        cin>>j;
        arcNode = (ArcNode *)malloc(sizeof(ArcNode));
        arcNode->adjvex = j;
        arcNode->nextArc = G->verTices[i].firstArc->nextArc;//插入表頭
        G->verTices[i].firstArc ->nextArc= arcNode;
        G->Indegree[j].indegree++;
    }
}
  • 兩種周游算法

深度優(yōu)先周游：對于鄰接表存儲類型，它采用遞歸算法，從起始點(diǎn)v0沿著鄰接表一次訪問，直到next指針為NULL，則返回上一層，進(jìn)入上一層頂點(diǎn)v1所在的鏈表繼續(xù)逐個訪問。

廣度周游與相鄰矩陣法類似，這里不做闡述。算法如下：

//深度優(yōu)先周游
void DFSM(ALGraph *G,int i){
    ArcNode *p;
    cout<<G->verTices[i].data;
    mark[i]=TRUE;
    p=G->verTices[i].firstArc;
    while(p){
        if(mark[p->adjvex]==FALSE)
            DFSM(G,p->adjvex);
        p=p->nextArc;       
    }
}

void DFS(ALGraph *G){
    for ( int i=0; i<G->vexNum;i++)
        mark[i]=FALSE;
    for( int i=0; i<G->vexNum;i++)
        if(!mark[i])
            DFSM(G,i);
}

//廣度優(yōu)先周游
void BFS(ALGraph *G,int x){
    ArcNode *p;
    int w;
    using std::queue;
    queue<int> Q;
    for ( int i=0; i<G->vexNum;i++) {mark[i]=FALSE;}
    cout<<G->verTices[x].data;
    mark[x]=TRUE;
    Q.push(x);
    while(!Q.empty()){
        int v=Q.front();
        Q.pop();
        p=G->verTices[v].firstArc;
        while(p){
            int w=p->adjvex;
            if(mark[w]==FALSE){
                mark[w]=TRUE;
                cout<<G->verTices[w].data;
                Q.push(w);}
            p=p->nextArc;
            }
        }
}
  • 拓?fù)渑判?/strong>

有向圖的邊可以看做定點(diǎn)之間制約關(guān)系的描述。在工程實(shí)踐中，有些工程的進(jìn)行經(jīng)常受到一定條件的約束，例如一個工程項目通常由若干子工程組成，某些子工程完成之后另一些子工程才能開始。

一個無環(huán)的有向圖稱為有向無環(huán)圖，有向無環(huán)圖常用來描述一個過程或一個系統(tǒng)的進(jìn)行過程。對于有向無環(huán)圖G=<V,E>，如果頂點(diǎn)序列滿足：存在頂點(diǎn)vi到vj的一條路徑，那么在序列中頂點(diǎn)vi必在頂點(diǎn)vj之前，頂點(diǎn)集合V的這種線型序列稱作一個拓?fù)湫蛄小?/p>

進(jìn)行有向圖的拓?fù)湫蛄蟹椒ㄈ缦拢?/p>

  1. 從有向圖中選出一個沒有前驅(qū)（入度為0）的頂點(diǎn)并輸出。
  2. 刪除圖中該頂點(diǎn)和所有以它為起點(diǎn)的弧。

不斷重復(fù)上述兩個步驟，會出現(xiàn)兩種情形：要么有向圖中頂點(diǎn)全部被輸出，要么當(dāng)前圖中不存在沒有前驅(qū)的頂點(diǎn)。當(dāng)圖中的頂點(diǎn)全部輸出時，就完成了有向無環(huán)圖的拓?fù)渑判?；?dāng)圖中還有頂點(diǎn)沒有輸出時，說明有向圖中含有環(huán)。

它的工作思想如下：

拓?fù)渑判?/div> 

//拓?fù)渑判?void TopsortbyQueue(ALGraph*G){
    for(int i=0; i< G->vexNum;i++)
        mark[i]=FALSE;
    using std::queue;
    queue<int> Q;
    cout<<"拓?fù)湫蛄袨?"<<endl;
    for(int i=0; i< G->vexNum;i++){
        if(G->Indegree[i].indegree==0)
            Q.push(i);}
        while(!Q.empty()){
            int v=Q.front();
            Q.pop();
            cout<<v;
            mark[v]=TRUE;
            for(Edge e=FirstEdge(G,v);isEdge(G,e);e=NextEdge(G,e)){
                G->Indegree[e.to].indegree--;
                if(G->Indegree[e.to].indegree ==0)
                    Q.push(e.to);
            }
        }
        for(int i=0;i< G->vexNum;i++)
            if(mark[i]==FALSE){
                cout<<endl;
                cout<<"還有頂點(diǎn)未訪問，此圖有環(huán)。"<<endl;
                break;
            }
}

4 總結(jié)#

明顯感覺到寫得多了對于語言的運(yùn)用更熟練了，也更有了設(shè)計算法需要的邏輯思想。這個寫的還算比較順隨著思維和語言能力提升，希望能在acm校選賽比賽上有好的發(fā)揮過兩天來更新結(jié)果！

5 附錄#

鄰接矩陣：

鄰接矩陣測試結(jié)果
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<queue> 
using namespace std;

#define MaxVertexNum 100 /*最大頂點(diǎn)數(shù)設(shè)為100*/
typedef enum{FALSE,TRUE} Boolean;
Boolean mark[MaxVertexNum];

typedef char VertexType; /*頂點(diǎn)類型設(shè)為字符型*/
typedef int EdgeType; /*邊的權(quán)值設(shè)為整型*/

typedef struct {
    VertexType vexs[MaxVertexNum]; /*頂點(diǎn)表*/
    EdgeType edges[MaxVertexNum][MaxVertexNum]; /*鄰接矩陣，即邊表*/
    int numVertex,numEdge; /*頂點(diǎn)數(shù)和邊數(shù)*/
}Mgragh,*MGragh; /*Maragh 是以鄰接矩陣存儲的圖類型*/


typedef struct edge{
    int from,to,weight;
}Edge,*Edged;

void CreateMGraph(MGragh G){/*建立有向圖G 的鄰接矩陣存儲*/
int i,j,k,w;
char ch;
cout<<"請輸入頂點(diǎn)數(shù)和邊數(shù)";
cin>>i>>j;
G->numVertex=i;
G->numEdge=j;

cout<<"請輸入頂點(diǎn)信息:"<<endl;

for (i=0;i<G->numVertex;i++) {cout<<"第"<<i<<"個點(diǎn):";cin>>G->vexs[i];} /*輸入頂點(diǎn)信息，建立頂點(diǎn)表*/
for (i=0;i<G->numVertex;i++)
    for (j=0;j<G->numVertex;j++) 
        G->edges[i][j]=0; /*初始化鄰接矩陣*/

cout<<"請輸入每條邊對應(yīng)的兩個頂點(diǎn)的序號:\n";

for (k=0;k<G->numEdge;k++){
    cout<<"v<i,j>:";
    cin>>i>>j; /*輸入e 條邊，建立鄰接矩陣*/
        G->edges[i][j]=1;
            }
}

void displaygraph(MGragh G){
int i,j;

for(i=0;i<G->numVertex;i++){
    for(j=0;j<G->numVertex;j++){
        cout<<G->edges[i][j]<<" ";}
    cout<<endl;
}
}

Edge FirstEdge(MGragh G,int oneVertex){
    Edge myEdge;
    myEdge.from=oneVertex;
    for(int i=0;i<G->numVertex;i++){
        if(G->edges[oneVertex][i]!=0){
            myEdge.to=i;
            myEdge.weight=G->edges[oneVertex][i];
            break;
        }
    }
    return myEdge;
}

Edge NextEdge(MGragh G,Edge preEdge){
    Edge myEdge;
    myEdge.from =preEdge.from ;
    if(preEdge.to <G->numVertex){
        for(int i=preEdge.to+1;i<G->numVertex;i++){
            if(G->edges[preEdge.from][i]!=0){
                myEdge.to =i;
                myEdge.weight =G->edges[preEdge.from ][i];
                break;
            }
        }
    }
    return myEdge;
}

bool isEdge(MGragh G, Edge myEdge){
    int test=0;
    for(int i=0;i<G->numVertex;i++){
        if(myEdge.to>=0&&G->edges[myEdge.from][myEdge.to]==1)return true;
    }
    return false;
}

//深度優(yōu)先周游    
void DFS(MGragh G, int v){
    mark[v]=TRUE;
    cout<<G->vexs[v];
    for(Edge e=FirstEdge(G,v);isEdge(G,e);e=NextEdge(G,e)){
        if(mark[e.to]==FALSE) DFS(G,e.to);
    }
}

void DFSM(MGragh G,int v){
    for(int i=0;i<G->numVertex;i++){
        mark[i]=FALSE;
    }
    DFS(G,0);
}

//廣度優(yōu)先周游
void BFS(MGragh G, int v){
    for(int i=0;i<G->numVertex;i++){
        mark[i]=FALSE;
    }
    using std::queue;
    queue<int>Q;
    cout<<G->vexs[v];
    mark[v]=TRUE;
    Q.push(v);
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(Edge e=FirstEdge(G,u);isEdge(G,e);e=NextEdge(G,e))
            if(mark[e.to]==FALSE){
                cout<<G->vexs[e.to];
                mark[e.to]=TRUE;
                Q.push(e.to);
            }
    }
}

int main(){
    Mgragh *Graph = (Mgragh *)malloc(sizeof(Mgragh));
    CreateMGraph(Graph);
    displaygraph(Graph);
    cout<<endl;
    BFS(Graph,0);
    cout<<endl;
    DFSM(Graph,0);
    system("pause");
    return 0;
}

鄰接表

鄰接表
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<queue> 
using namespace std;
#define MAX_VERTEXT_NUM 20
typedef enum{FALSE,TRUE} Boolean;
Boolean mark[MAX_VERTEXT_NUM];

typedef struct edge{
    int from,to,weight;
}Edge,*Edged;

typedef struct ArcNode{
    int adjvex;
    struct ArcNode *nextArc;
    int weight;
}ArcNode;

typedef struct VNode{
    char data;
    ArcNode *firstArc;
}VNode, AdjList[MAX_VERTEXT_NUM];

typedef struct Indegree{
    int indegree;
}Indegree,indegree[MAX_VERTEXT_NUM];

typedef struct{
    AdjList verTices;
    int vexNum;
    int arcNum;
    int kind;
    indegree Indegree;
}ALGraph;

typedef struct Dist{
    int index;
    int length;
    int pre;
}Dist,*Dijk;

edge FirstEdge(ALGraph *G,int oneVertex){
    Edge myEdge;
    myEdge.from=oneVertex;
    ArcNode *temp=G->verTices[oneVertex].firstArc;
    if(temp->nextArc!=NULL){
        myEdge.to=temp->nextArc->adjvex;
        myEdge.weight=temp->nextArc->weight;
    }
    return myEdge;
}

edge NextEdge(ALGraph *G,Edge preEdge){
    Edge myEdge;
    myEdge.from =preEdge.from;
    ArcNode *temp=G->verTices[preEdge.from].firstArc;
    while(temp->nextArc!=NULL&&temp->adjvex<=preEdge.to)
        temp=temp->nextArc;
    if(temp->nextArc!=NULL){
        myEdge.to=temp->nextArc->adjvex;
        myEdge.weight=temp->nextArc->weight;
    }
    return myEdge;
}

bool isEdge(ALGraph *G, Edge myEdge){
    int n=0;
    ArcNode *p;
    p=G->verTices[myEdge.from].firstArc;
    while(p){
        if(p->adjvex==myEdge.to){
            n=0;
        }else{
            n=1;
        }
        p=p->nextArc;
    }
    if(n==0){return true;}
    else{
        return false;
    }
}

void CreateGraph(ALGraph *G)
{
    int i,j,k,weight;
    ArcNode *arcNode;
    printf_s("請輸入頂點(diǎn)數(shù)和邊數(shù)：");
    cin>>G->vexNum;
    cin>>G->arcNum;
    //建立頂點(diǎn)表
    printf_s("建立頂點(diǎn)表\n");
    for (i = 0; i < G->vexNum; i++)
    {
        printf_s("請輸入第%d個頂點(diǎn):", i);
        cin>>G->verTices[i].data;
        arcNode = (ArcNode *)malloc(sizeof(ArcNode));
        arcNode->adjvex=i;
        arcNode->nextArc=NULL;
        G->verTices[i].firstArc=arcNode;
        G->Indegree[i].indegree=0;
    }
    //建立邊表
    printf_s("建立邊表\n");
    for (k = 0; k < G->arcNum; k++)
    {
        printf_s("請輸入（vi-vj）的頂點(diǎn)對序號");
        cin>>i;
        cin>>j;
        arcNode = (ArcNode *)malloc(sizeof(ArcNode));
        arcNode->adjvex = j;
        arcNode->nextArc = G->verTices[i].firstArc->nextArc;//插入表頭
        G->verTices[i].firstArc ->nextArc= arcNode;
        G->Indegree[j].indegree++;
    }
}

//顯示圖的鄰接表
void DisplayGraph(ALGraph *G)
{
    int i;
    for (i = 0; i < G->vexNum; i++)
    {
            cout<<G->Indegree[i].indegree;
            ArcNode *P= G->verTices[i].firstArc;
            printf_s("%d->", i);
        while (P != NULL)
        {
            printf_s("%d->", P->adjvex);
            P = P->nextArc;
        }
        printf_s("\n");
    }
}

//深度優(yōu)先周游
void DFSM(ALGraph *G,int i){
    ArcNode *p;
    cout<<G->verTices[i].data;
    mark[i]=TRUE;
    p=G->verTices[i].firstArc;
    while(p){
        if(mark[p->adjvex]==FALSE)
            DFSM(G,p->adjvex);
        p=p->nextArc;       
    }
}

void DFS(ALGraph *G){
    for ( int i=0; i<G->vexNum;i++)
        mark[i]=FALSE;
    for( int i=0; i<G->vexNum;i++)
        if(!mark[i])
            DFSM(G,i);
}

//廣度優(yōu)先周游
void BFS(ALGraph *G,int x){
    ArcNode *p;
    int w;
    using std::queue;
    queue<int> Q;
    for ( int i=0; i<G->vexNum;i++) {mark[i]=FALSE;}
    cout<<G->verTices[x].data;
    mark[x]=TRUE;
    Q.push(x);
    while(!Q.empty()){
        int v=Q.front();
        Q.pop();
        p=G->verTices[v].firstArc;
        while(p){
            int w=p->adjvex;
            if(mark[w]==FALSE){
                mark[w]=TRUE;
                cout<<G->verTices[w].data;
                Q.push(w);}
            p=p->nextArc;
            }
        }
}

//拓?fù)渑判?void TopsortbyQueue(ALGraph*G){
    for(int i=0; i< G->vexNum;i++)
        mark[i]=FALSE;
    using std::queue;
    queue<int> Q;
    cout<<"拓?fù)湫蛄袨?"<<endl;
    for(int i=0; i< G->vexNum;i++){
        if(G->Indegree[i].indegree==0)
            Q.push(i);}
        while(!Q.empty()){
            int v=Q.front();
            Q.pop();
            cout<<v;
            mark[v]=TRUE;
            for(Edge e=FirstEdge(G,v);isEdge(G,e);e=NextEdge(G,e)){
                G->Indegree[e.to].indegree--;
                if(G->Indegree[e.to].indegree ==0)
                    Q.push(e.to);
            }
        }
        for(int i=0;i< G->vexNum;i++)
            if(mark[i]==FALSE){
                cout<<endl;
                cout<<"還有頂點(diǎn)未訪問，此圖有環(huán)。"<<endl;
                break;
            }
}

int main(){
    int x;
    int num;
    string edge;

    ALGraph *Graph = (ALGraph *)malloc(sizeof(ALGraph));
    CreateGraph(Graph);
    DisplayGraph(Graph);
    DFS(Graph);
    BFS(Graph,0);

    TopsortbyQueue(Graph);
    system("pause");
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容