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