邻接表+DFS

#include<iostream>
using namespace std;int Visited[100]={0};typedef struct ENode
{int V1,V2;int Weight;
} Edge;//邻接点的定义 
typedef struct AdjVNode
{int AdjV; //邻接点下标 int Weight;struct AdjVNode* Next;
} PtrAdjV;//顶点表头结点的定义 
typedef struct VNode
{PtrAdjV* FirstEdge; //边表头指针 int Data; //存顶点数据 
} AdjList[100]; //AdjList是邻接表类型 //图结点的定义 
typedef struct GNode
{int Nv;int Ne;AdjList G; //邻接表 
} LGraph;LGraph* CreateGraph(int VertexNum)
{int V;LGraph* Graph;Graph=new LGraph;Graph->Nv=VertexNum;Graph->Ne=0;for (V=0;V<Graph->Nv;V++){Graph->G[V].FirstEdge=NULL;}return Graph;
}void InsertEdge(LGraph* Graph,Edge* E)
{PtrAdjV* NewNode;NewNode=new PtrAdjV;NewNode->AdjV=E->V2;NewNode->Weight=E->Weight;NewNode->Next=Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge=NewNode;NewNode=new PtrAdjV;NewNode->AdjV=E->V1;NewNode->Weight=E->Weight;NewNode->Next=Graph->G[E->V2].FirstEdge;Graph->G[E->V2].FirstEdge=NewNode;
}LGraph* BuildGraph(LGraph* Graph)
{Edge* E;int V;int Nv,Ne,i;cin>>Nv>>Ne;Graph=CreateGraph(Nv);Graph->Ne=Ne;for (V=0;V<Graph->Nv;V++){cin>>Graph->G[V].Data;}if (Graph->Ne!=0){E=new Edge;for (i=0;i<Graph->Ne;i++){cin>>E->V1>>E->V2>>E->Weight;InsertEdge(Graph,E); }}return Graph;
}void Visit(int V)
{cout<<V<<" ";
}//void DFS(LGraph* Graph,int V,void(* Visit)(int))
void DFS(LGraph* Graph,int V)
{PtrAdjV* W;Visit(V);Visited[V]=1;for (W=Graph->G[V].FirstEdge;W;W=W->Next){if (Visited[W->AdjV]==0){
//			DFS(Graph,W->AdjV,Visit);DFS(Graph,W->AdjV);}}
}int main()
{LGraph* Graph;int V=0;Graph=BuildGraph(Graph);DFS(Graph,V);return 0;
}

邻接矩阵+BFS

#include<iostream>
using namespace std;
#define Infinity 65535
#define ERROR -1
#define MaxSize 100int Visited[100]={0};typedef struct GNode
{int Nv;int Ne;int G[100][100];int Data[100];
} MGraph;typedef struct ENode
{int V1,V2;int Weight;
} Edge;typedef struct QNode
{int* data;int front,rear;int Maxsize;
} Queue;Queue* CreateQueue(int Maxsize)
{Queue* Q=new Queue;Q->data=new int;Q->front=Q->rear=0;Q->Maxsize=Maxsize;return Q; 
}bool IsFull(Queue* Q)
{return ((Q->rear+1)%Q->Maxsize==Q->front);
}bool AddQ(Queue* Q,int X)
{if (IsFull(Q)){return false; }else{Q->rear=(Q->rear+1)%Q->Maxsize;Q->data[Q->rear]=X;return true;}
}bool IsEmpty(Queue* Q)
{return (Q->front==Q->rear);
}int DeleteQ(Queue* Q)
{if (IsEmpty(Q)){return ERROR;}else{Q->front=(Q->front+1)%Q->Maxsize;return Q->data[Q->front];}
}MGraph* CreateGraph(int VertexNum)
{int V,W;MGraph* Graph;Graph=new MGraph;Graph->Nv=VertexNum;Graph->Ne=0;for (V=0;V<Graph->Nv;V++){for (W=0;W<Graph->Nv;W++){Graph->G[V][W]=Infinity;}}return Graph;
}void InsertEdge(MGraph* Graph,Edge* E)
{Graph->G[E->V1-Graph->Data[0]][E->V2-Graph->Data[0]]=E->Weight;Graph->G[E->V2-Graph->Data[0]][E->V1-Graph->Data[0]]=E->Weight; 
}MGraph* BuildGraph(MGraph* Graph)
{Edge* E;int V;int Nv,Ne,i;cin>>Nv>>Ne;Graph=CreateGraph(Nv);Graph->Ne=Ne;for (V=0;V<Nv;V++){cin>>Graph->Data[V];}if (Graph->Ne!=0){E=new Edge;for (i=0;i<Graph->Ne;i++){cin>>E->V1>>E->V2>>E->Weight;InsertEdge(Graph,E);}}return Graph;
}bool IsEdge(MGraph* Graph,int V,int W)
{return Graph->G[V][W]<Infinity?true:false;
}void Visit(int V)
{cout<<V<<" ";
}void BFS(MGraph* Graph,int S)
{Queue* Q;int V,W;Q=CreateQueue(MaxSize);Visit(S);Visited[S]=1;AddQ(Q,S);while(!IsEmpty(Q)){V=DeleteQ(Q);for (W=0;W<Graph->Nv;W++){if (Visited[W]==0&&IsEdge(Graph,V,W)){Visit(W);Visited[W]=1;AddQ(Q,W);}}}
}int main()
{MGraph* Graph;int S=0;Graph=BuildGraph(Graph);BFS(Graph,S);
}