有向圖 無向圖和創建（數組表示法）和深度優先訪問

有向圖和無向圖差別就是一句代碼的差別 ，無向圖中代碼注釋掉即可

有向圖和有向網的差別也就是權值的差別  有向網需要賦予權值  有向圖有連線自動賦值為1

深度優先采用遞歸方法（參考前面幾篇文章，裡面有具體的深度優先和廣度優先訪問和隊列基本操作）

廣度優先采用隊列

上代碼

[cpp] #include <stdio.h>  
#include <stdlib.h>  
 
#define OK 1  
#define ERROR -1  
#define OVERFLOW 0  
#define MAXVER 20  //定義最大頂點數  
 
 
typedef enum{UDG,UDN,DG,DN} GraphKind;// 定義無向圖 無向網 有向圖 有向網  
typedef char verType;  //定義頂點類型  
typedef int status ; 
typedef struct  
{ 
    verType verx[MAXVER];  //定義頂點  
    int arcs[MAXVER][MAXVER]; //定義弧  
    int vernum,arcsnum;//定義最大頂點數 和弧  
    GraphKind kind;  //類別  
}MGraph; 
 
int visited[MAXVER]={0};  //頂點剛開始都沒被訪問過   
 
//查找頂點在數組中的下標  
int locate(MGraph G,verType ch){ 
    int i; 
    for(i=0;i<G.vernum&&ch!=G.verx[i];i++); 
    return i; 
} 
 
//創建無向圖  
status createUDN(MGraph &G,int &v) 
{ 
    int i,j,k; 
    verType ch1,ch2; 
    printf("請輸入無向圖的頂點數和弧數：格式如2 3\n"); 
    scanf("%d%d",&G.vernum,&G.arcsnum);  
    fflush(stdin); 
    printf("請輸入頂點符號：\n"); 
    for(i=0;i<G.vernum;i++){ 
        scanf("%c",&G.verx[i]); 
        fflush(stdin); 
    } 
    for(i=0;i<G.vernum;i++){ 
        for(j=0;j<G.vernum;j++) 
            G.arcs[i][j]=0;  //賦初值為0  
    } 
    printf(" 請輸入有連接的點：格式A B\\n \n"); 
    for(i=0;i<G.arcsnum;i++){ 
        printf("請輸入第%d對值\n",i+1); 
    scanf("%c %c",&ch1,&ch2);  //輸入頂點符號和權值  
    fflush(stdin);  
    k=locate(G,ch1);   //獲得頂點下標  
    j=locate(G,ch2); 
    G.arcs[k][j]=1;  //為臨界矩陣賦值  
    G.arcs[j][k]=G.arcs[k][j];  //無向圖為對稱矩陣  
    } 
    return OK; 
} 
 
//創建有向圖  
status createDN(MGraph &G,int &v) 
{ 
    int i,j,k; 
    verType ch1,ch2; 
    printf("請輸入有向圖的頂點數和弧數：格式如2 3\n"); 
    scanf("%d%d",&G.vernum,&G.arcsnum); //  頂點數和弧數輸入  
    fflush(stdin);  //清除回車  
    printf("請輸入頂點符號：\n"); 
    for(i=0;i<G.vernum;i++){ 
        scanf("%c",&G.verx[i]);   //頂點符號輸入  
        fflush(stdin); 
    } 
    for(i=0;i<G.vernum;i++){ 
        for(j=0;j<G.vernum;j++) 
            G.arcs[i][j]=0;  //賦初值為0  
    } 
    printf(" 請輸入頂點符號：格式A B 3\\n \n"); 
    for(i=0;i<G.arcsnum;i++){ 
        printf("請輸入第%d對值\n",i+1); 
    scanf("%c %c",&ch1,&ch2);  //輸入頂點符號和權值  
    fflush(stdin);  
    k=locate(G,ch1);   //獲得頂點下標  
    j=locate(G,ch2); 
    G.arcs[k][j]=1;  //為臨界矩陣賦值  
//  G.arcs[j][k]=G.arcs[k][j];  //無向圖為對稱矩陣  
    } 
    return OK; 
} 
 
//進行深度優先遍歷  
void DFS(MGraph G,int v){  //參數 1 圖 2傳遞進來下標   
    int i; 
    printf("%c ",G.verx[v]);  
    visited[v]=1; 
    for(i=0;i<G.vernum;i++) 
        if(visited[i]==0 && G.arcs[v][i]!=0){ //類型的判斷  是否被訪問過 是否是權值或邊  
            DFS(G,i); 
        } 
} 
 
 
//進行圖的遍歷  
void DFSTravers(MGraph G){  
    int i; 
    for(i=0;i<G.vernum;i++){  
      visited[i]=0; 
    } 
    for(i=0;i<G.vernum;i++){  
        if(visited[i]==0) 
            DFS(G,i); 
    } 
} 
 
int main() 
{ 
    MGraph G; 
    int v=0; 
    if(createUDN(G,v)){//創建無向圖  
        printf("遍歷結果為：\n"); 
       DFSTravers(G);  //進行無向圖的遍歷  
    } 
    if(createDN(G,v)){//創建有向圖  
        printf("遍歷結果為：\n"); 
       DFSTravers(G);  //進行有向圖的遍歷  
    } 
    return 0; 
} 

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR -1
#define OVERFLOW 0
#define MAXVER 20  //定義最大頂點數

typedef enum{UDG,UDN,DG,DN} GraphKind;// 定義無向圖 無向網 有向圖 有向網
typedef char verType;  //定義頂點類型
typedef int status ;
typedef struct
{
 verType verx[MAXVER];  //定義頂點
    int arcs[MAXVER][MAXVER]; //定義弧
 int vernum,arcsnum;//定義最大頂點數 和弧
 GraphKind kind;  //類別
}MGraph;

int visited[MAXVER]={0};  //頂點剛開始都沒被訪問過

//查找頂點在數組中的下標
int locate(MGraph G,verType ch){
 int i;
    for(i=0;i<G.vernum&&ch!=G.verx[i];i++);
 return i;
}

//創建無向圖
status createUDN(MGraph &G,int &v)
{
 int i,j,k;
 verType ch1,ch2;
 printf("請輸入無向圖的頂點數和弧數：格式如2 3\n");
 scanf("%d%d",&G.vernum,&G.arcsnum);
 fflush(stdin);
 printf("請輸入頂點符號：\n");
 for(i=0;i<G.vernum;i++){
  scanf("%c",&G.verx[i]);
  fflush(stdin);
 }
 for(i=0;i<G.vernum;i++){
  for(j=0;j<G.vernum;j++)
   G.arcs[i][j]=0;  //賦初值為0
 }
 printf(" 請輸入有連接的點：格式A B\\n \n");
 for(i=0;i<G.arcsnum;i++){
  printf("請輸入第%d對值\n",i+1);
 scanf("%c %c",&ch1,&ch2);  //輸入頂點符號和權值
 fflush(stdin);
 k=locate(G,ch1);   //獲得頂點下標
 j=locate(G,ch2);
 G.arcs[k][j]=1;  //為臨界矩陣賦值
 G.arcs[j][k]=G.arcs[k][j];  //無向圖為對稱矩陣
 }
 return OK;
}

//創建有向圖
status createDN(MGraph &G,int &v)
{
 int i,j,k;
 verType ch1,ch2;
 printf("請輸入有向圖的頂點數和弧數：格式如2 3\n");
 scanf("%d%d",&G.vernum,&G.arcsnum); //  頂點數和弧數輸入
 fflush(stdin);  //清除回車
 printf("請輸入頂點符號：\n");
 for(i=0;i<G.vernum;i++){
  scanf("%c",&G.verx[i]);   //頂點符號輸入
  fflush(stdin);
 }
 for(i=0;i<G.vernum;i++){
  for(j=0;j<G.vernum;j++)
   G.arcs[i][j]=0;  //賦初值為0
 }
 printf(" 請輸入頂點符號：格式A B 3\\n \n");
 for(i=0;i<G.arcsnum;i++){
  printf("請輸入第%d對值\n",i+1);
 scanf("%c %c",&ch1,&ch2);  //輸入頂點符號和權值
 fflush(stdin);
 k=locate(G,ch1);   //獲得頂點下標
 j=locate(G,ch2);
 G.arcs[k][j]=1;  //為臨界矩陣賦值
// G.arcs[j][k]=G.arcs[k][j];  //無向圖為對稱矩陣
 }
 return OK;
}

//進行深度優先遍歷
void DFS(MGraph G,int v){  //參數 1 圖 2傳遞進來下標
 int i;
    printf("%c ",G.verx[v]);
 visited[v]=1;
 for(i=0;i<G.vernum;i++)
  if(visited[i]==0 && G.arcs[v][i]!=0){ //類型的判斷  是否被訪問過 是否是權值或邊
      DFS(G,i);
  }
}

//進行圖的遍歷
void DFSTravers(MGraph G){
 int i;
 for(i=0;i<G.vernum;i++){
   visited[i]=0;
 }
 for(i=0;i<G.vernum;i++){
  if(visited[i]==0)
   DFS(G,i);
 }
}

int main()
{
 MGraph G;
 int v=0;
 if(createUDN(G,v)){//創建無向圖
  printf("遍歷結果為：\n");
    DFSTravers(G);  //進行無向圖的遍歷
 }
 if(createDN(G,v)){//創建有向圖
  printf("遍歷結果為：\n");
    DFSTravers(G);  //進行有向圖的遍歷
 }
 return 0;
}