|
#include "StdAfx.h" #include "Graphlist.h" #include <iostream> #include <stdio.h> #include <stdlib.h> #include <queue> //鄰結(jié)表的遍歷 using namespace std; #define MAXNODE 1000 //圖中頂點的最大數(shù) typedef int infotype; typedef char vertype; struct ArcNode //邊界點類型 { int adjvex; //該邊的終點編號 ArcNode *next; //指向下一條邊的指針 // infotype *info; //該邊的相關(guān)信息 }; struct VerNode//表頭節(jié)點 { vertype vertex; //頂點信息 ArcNode *firstarc; //指向第一個鄰接點的指針 }; struct AlGraph//鄰接表 { VerNode vertices[MAXNODE];//鄰接表 int vexnum,arcnum; //頂點和邊的數(shù)目 }; AlGraph CreateAdjList(AlGraph g)//建立有向圖的鄰接表存儲結(jié)構(gòu) { int n; cin>>n; for(int i = 1;i <= n; i++) { cin>>g.vertices[i].vertex;//輸入頂點信息 g.vertices[i].firstarc=NULL;//初始化每個鏈表為空 } int v1, v2; cin>>v1>>v2; //輸入一條邊依附的兩個頂點序號 int e = 0; //圖的邊數(shù) while(v1 != 0&&v2!=0) //題目要求兩頂點之一為0結(jié)束 { ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode)); //用頭插法插入節(jié)點以建立鏈表 p->adjvex = v2; p->next = g.vertices[v1].firstarc; g.vertices[v1].firstarc=p; e++; cin>>v1>>v2; } g.vexnum = n; g.arcnum = e; return g; } int visited[MAXNODE]; //訪問標志數(shù)組 void VisitFunc(AlGraph g, int v)//訪問v { cout<<g.vertices[v].vertex <<endl; } int GraphFirstAdj(AlGraph g , int v)//得到v的第一個鄰結(jié)點 { if(g.vertices[v].firstarc!=NULL) return g.vertices[v].firstarc->adjvex; else return 0; } int GraphNextAdj(AlGraph g,int v, int w)//返回v的下一個鄰結(jié)點，若w是v的最后一個鄰結(jié)點則返回0 { ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode)); p = g.vertices[v].firstarc; while(p) { if(p->adjvex == w && p->next != NULL) return p->next->adjvex; p = p->next; } return 0; } void DFS(AlGraph g, int v)//dfs { visited[v] = 1; VisitFunc(g,v);//訪問v頂點(輸出v) for(int w = GraphFirstAdj(g,v); w!= 0; w = GraphNextAdj(g,v,w)) { if(!visited[w])DFS(g,w);//對v的尚未訪問的鄰接頂點w遞歸調(diào)用 } } void DFSTraverse(AlGraph g) //圖的dfs遍歷 { for(int i = 1; i <= g.vexnum; i++) visited[i] = 0;//初始訪問數(shù)組置未訪問標志 for(int i = 1; i <= g.vexnum; i++) { if(!visited[i])DFS(g,i);//對未訪問的頂點調(diào)用DFS } } void BFSTraverse(AlGraph g)// 圖的bfs遍歷 { for(int i = 1; i <= g.vexnum;i++) visited[i] = 0;//初始訪問數(shù)組 queue<int> q; for(int i = 1;i <= g.vexnum;i++) { if(!visited[i]) { q.push(i); visited[i] = 1; VisitFunc(g,i); while(!q.empty()) { int v = q.front();//對頭元素出隊列并置為v q.pop(); for(int w = GraphFirstAdj(g,v); w!=0; w = GraphNextAdj(g,v,w))//遍歷v的鄰結(jié)點 { if(!visited[w]) { q.push(w);//v的尚未訪問的鄰結(jié)頂點w入隊列Q visited[w] = 1; VisitFunc(g,w); } } } } } } |
|
|
