重み付け図への隣接テーブル実装
3133 ワード
疎図はこのようにして空間を節約することができますが、隣接表写アルゴリズムの卵が痛くて、私はやはり行列を使うのが好きです.の
テスト:
// cunzai direction and value de listGraph
#ifndef listGRAPH_H_
#define listGRAPH_H_
#define MAXSIZE 100
#include
#include
#include
#include
using namespace std;
struct edgeNode
{
char info;
int cost;
edgeNode *next;
};
struct headNode
{
char info;
int index;
edgeNode *firstEdge;
};
class listGraph
{
public:
listGraph();
~listGraph();
void creatGraph();
void dfs();
void bfs();
private:
int headNum;
int edgeNum;
headNode *list;
};
listGraph::listGraph()
{
cout<>headNum>>edgeNum;
list = new headNode[headNum];
cout<>list[i].info;
list[i].index=i;
list[i].firstEdge=NULL;
}
}
void listGraph::creatGraph()
{
int i,j;
char head;
cout<>head>>edge->info>>edge->cost;
edge->next=NULL;
for(j=0; jnext=list[j].firstEdge;
list[j].firstEdge=edge;
}
}
}
}
listGraph::~listGraph()
{
int i;
edgeNode *temp;
for(i=0; inext;
delete temp;
}
}
}
void listGraph::dfs()
{
bool visited[headNum];
memset(visited,0,sizeof(visited));
cout<S;
S.push(0);
while(!S.empty())
{
int temp=S.top();
edgeNode*cur=list[temp].firstEdge;
while(cur)
{
int curIndex;//find and stroe the index of current element.
for(int i=0; iinfo==list[i].info)
{
curIndex=list[i].index;
break;
}
}
if(!visited[curIndex])
{
cout<info<next;
}
if(!cur)S.pop();
}
}
void listGraph::bfs()
{
bool visited[headNum];
int printCount=0;
memset(visited,0,sizeof(visited));
queueQ;
Q.push(0);
while(!Q.empty())
{
int temp=Q.front();
Q.pop();
if(!visited[temp])
{
cout<info==list[i].info)
{
curIndex=list[i].index;
break;
}
}
Q.push(curIndex);
cur=cur->next;
}
//use printCount to deal with the situation if there is a loop in the graph.
if(printCount==headNum)break;
}
}
#endif
テスト:
#include
#include "listGraph.h"
#include
using namespace std;
int main()
{
//freopen("in.txt","r",stdin);
//for input test
/*
6 5
A B C D E F
A B 0
A C 0
A D 0
B E 0
B F 0
*/
listGraph test;
test.creatGraph();
cout<