程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 圖的深度優先遍歷的實現 c/c++ DFS,深度dfs

圖的深度優先遍歷的實現 c/c++ DFS,深度dfs

編輯:C++入門知識

圖的深度優先遍歷的實現 c/c++ DFS,深度dfs


#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

using namespace std;

 

#define MAX 100

#define LENGTH(a) (sizeof(a) / sizeof(a[0]))

 

int visited[MAX];

 

typedef struct _graph{

    char vexs[MAX];

    int vexnum;

    int edgnum;

    int matrix[MAX][MAX];

}Graph,*PGgraph;

 

static int get_position(Graph g, char ch){

    for(int i = 0;i<g.vexnum;i++){

        if(ch == g.vexs[i])

            return i;

    }

    return -1;

}

 

static char read_char(){

    char ch;

    while(!((((ch)>='a') && ((ch)<='z')) || (((ch)>='A') && ((ch)<='Z'))))

        ch = getchar();

    return ch;

}

 

Graph creat_graph(){

    char c1,c2;

    int v,e;

    int p1,p2;

    Graph pG;

    

    cout<<"input number of vex > ";

    cin>>v;

    

    cout<<"input number of edge > ";

    cin>>e;

    

    //memset(pG,0,sizeof(Graph));

    pG.vexnum = v;

    pG.edgnum = e;

    

    //Initialize vexs

    for(int i=0; i<pG.vexnum;i++){

        //pG.vexs[i] = read_char();

        cin>>pG.vexs[i] ;

    }

    

    //Initialize edges

    for(int i = 0;i < pG.edgnum; i++){

        //c1 = read_char();

        //c2 = read_char();

        cin>>c1>>c2;

        cout<<c1<<c2<<endl;

        p1 = get_position(pG, c1);

        p2 = get_position(pG, c2);

        pG.matrix[p1][p2] = 1;

        pG.matrix[p2][p1] = 1;

    }

    return pG;

}

 

static int next_vertex(Graph g, int v,int w){

    

    if(v<0 || v>g.vexnum-1|| w<0 || w>(g.vexnum-1))   return -1;

    

    for(int i=w+1; i < g.vexnum; i++){

        if(g.matrix[v][i] == 1)  return i;

    }

    

    return -1;

}

 

 

static int first_vertex(Graph g, int v){

    

    if(v<0 || v>g.vexnum-1)   return -1;

    

    for(int i=0; i < g.vexnum; i++){

        if(g.matrix[v][i] == 1)  return i;

    }

    

    return -1;

}

 

void DFS(Graph g, int i){

    

    if(visited[i] == 0){

        visited[i] = 1;

        cout<<g.vexs[i]<<" ";

    }

    int w = first_vertex(g,i);

    for(;w>=0; w = next_vertex(g,i,w)){

        if(!visited[w]) DFS(g,w);

        

    }

}

 

 

 

int main(int argc, const char * argv[]) {

    for(int i = 0; i < MAX; i++){

        visited[i] = 0;

    }

    Graph g;

    g= creat_graph();

    

    for(int i = 0; i< g.vexnum; i++){

        if(!visited[i])         DFS(g,i);

    }

    return 0;

}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved