|
// Graph.cpp : Defines the entry point for the console application. //鄰接矩陣 #include "stdafx.h" // test.cpp : Defines the entry point for the console application. #include "stdafx.h" #include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <iostream> #include <queue> using namespace std; //圖的數(shù)組（鄰接矩陣）存儲(chǔ) #define MAX_VERTEX_NUM 20 //最大頂點(diǎn)個(gè)數(shù) //頂點(diǎn)關(guān)系，對(duì)無(wú)權(quán)圖，用1(是)或0(否)表示相鄰否 bool visited[20]; typedef struct { char* vexs[MAX_VERTEX_NUM];//頂點(diǎn)向量,指針數(shù)組，用于存儲(chǔ)頂點(diǎn) int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];////鄰接矩陣 .頂點(diǎn)關(guān)系，對(duì)無(wú)權(quán)圖，用1(是)或0(否)表示相鄰否 int vexnum,arcnum; }MGraph; int LocateVex(MGraph G, char* u) {//操作結(jié)果:若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1 int i ; for(i = 0; i < G.vexnum; ++i) if(strcmp(G.vexs[i],u) == 0) //strcmp的參數(shù)必須是const char* return i; return -1; } void CreateFAG(MGraph *G) {//采用數(shù)組(鄰接矩陣)表示法,由文件構(gòu)造沒(méi)有相關(guān)信息的無(wú)向圖G int i, j ,k ; int N = 3; //N表示頂點(diǎn)字符數(shù) 在開辟空間時(shí)用到 char filename[30]; char va[5]; char vb[5]; FILE* pFile; printf("請(qǐng)輸入數(shù)據(jù)文件名:"); scanf("%s",filename); //請(qǐng)輸入數(shù)據(jù)文件名 //D:\\Graph\\1.txt or D:/Graph/1.txt pFile = fopen(filename, "r"); //pFile = fopen("1.txt","r"); if(pFile == NULL) { printf("fail to read"); getchar(); getchar(); exit(1); } fscanf(pFile, "%d", &(*G).vexnum); fscanf(pFile, "%d", &(*G).arcnum); for(i = 0; i < G->vexnum; i++){ G->vexs[i] = (char*)malloc(N*sizeof(char));//分配頂點(diǎn)數(shù)目 } for(i = 0; i < G->vexnum; i++){ fscanf(pFile, "%s", G->vexs[i]); }//存儲(chǔ)節(jié)點(diǎn) for(i = 0 ; i < (*G).vexnum; ++i) //初始化鄰接矩陣 for(j = 0; j <(*G).vexnum; ++j) { (*G).arcs[i][j] = 0; } for(k = 0; k < (*G).arcnum; ++k) { fscanf(pFile, "%s %s",va,vb); i = LocateVex(*G, va); j = LocateVex(*G, vb); (*G).arcs[i][j] = (*G).arcs[j][i] = 1;//無(wú)向圖 } fclose(pFile); return; } //圖G中頂點(diǎn)k的第一個(gè)鄰接頂點(diǎn) int FirstVex(MGraph G, int k){ if(k >= 0 && k < G.vexnum){// k合理 for(int i = 0; i < G.vexnum; i++) if(G.arcs[k][i] != 0) return i ;//頂點(diǎn)相連，則返回頂點(diǎn)位置 } return -1; } //圖G中頂點(diǎn)i的第j個(gè)鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn) int NextVex(MGraph G, int i, int j){ if( i >= 0 && i <G.vexnum && j >=0 && j < G.vexnum){//i,j合理 for(int k = j+1; k < G.vexnum; k++) if(G.arcs[i][k] != 0) return k; } return -1; } //深度優(yōu)先遍歷 test.exe!mainCRTStartup() Line 371 C void DFS(MGraph G, int k){ int i ; visited[k] = true; printf("%s ", G.vexs[k]);////訪問(wèn)第K個(gè)節(jié)點(diǎn) for( i = FirstVex(G,k); i >= 0; i = NextVex(G, k, i)) if(!visited[i]) DFS(G, i);//對(duì)K的尚未訪問(wèn)的鄰接頂點(diǎn)i遞歸調(diào)用DFS } void DFStrieval(MGraph G) { int i; for( i = 0; i< G.vexnum;i++) { if(visited[i] != true) DFS(G, i); } } //---------廣度遍歷------------- void BFS(MGraph G) { for(int n = 0; n < G.vexnum; n++) { int k ; queue<int> SQ; //輔助隊(duì)列SQ ,存儲(chǔ)頂點(diǎn)的位置 if(!visited[n]){//i未訪問(wèn) visited[n] = true; printf("%s ", G.vexs[n]); SQ.push(n); while(!SQ.empty()){ k = SQ.front(); SQ.pop(); for(int w = FirstVex(G, k); w >= 0; w = NextVex(G, k ,w)) if(!visited[w]){ //w為k的尚未訪問(wèn)的鄰接頂點(diǎn) visited[w] = true; printf("%s ", G.vexs[w]); SQ.push(w); } }//while } } } int main(){ MGraph *G; G = (MGraph*)malloc(sizeof(MGraph)); CreateFAG(G); memset(visited, 0, sizeof(visited)); printf("深度遍歷：\n"); //DFS(*G, 1);//從第二個(gè)節(jié)點(diǎn)開始 DFStrieval(*G); memset(visited, 0, sizeof(visited)); printf("\n"); printf("廣度遍歷：\n"); BFS(*G); //從第一個(gè)節(jié)點(diǎn)開始 getchar(); getchar(); return 0; } 1.txt 8 9 V0 V1 V2 V3 V4 V5 V6 V7 V0 V1 V0 V3 V0 V4 V1 V2 V1 V4 V2 V5 V3 V6 V4 V6 V6 V7 |
|
|
