图的基本实现

开始学习图的基本算法，《大话数据结构》一书写的很不错，推荐之。算法导论上的图例子举得不好，感觉把简单的给弄复杂了。

#include <iostream>
#include <stdio.h>
#include <queue>
#define MAXVER 1024
#define INF 65535
bool visited[MAXVER];
#define TRUE 1
#define FALSE 0;
using namespace std;

typedef struct{
	int numVertex;//顶点数
	int numEdges;//边数
	int vertex[MAXVER];//顶点
	int edges[MAXVER][MAXVER];//每条边的权值
}Graph;

void CreateGraph(Graph* g, int v, int e){
	g->numVertex = v;
	g->numEdges = e;

	//邻接矩阵初始化
	for (int i = 0; i < g->numVertex; i++)
	{
		for (int j = 0; j < g->numVertex; j++){
			g->edges[i][j] = INF;
		}
	}
}

void SetEdgeVal(Graph* g, int i, int j, int val)
{
	g->edges[i][j] = val;
}

int locate(Graph *g, int s)//定位
{
	for (int i = 0; i < g->numVertex; i++)
	{
		if (g->vertex[i] == s)
		{
			return i;
		}
	}
	return -1;
}
void PrintGraph(Graph* g)
{
	for (int i = 0; i < g->numVertex; i++)
	{
		for (int j = 0; j < g->numVertex; j++){
			cout << g->edges[i][j] << " ";
		}
		cout << endl;
	}
}
//深度优先遍历的递归实现
void DFS(Graph* g, int i)
{
	visited[i] = TRUE;
	//do sth
	cout << i << "Test DFS" << endl;
	for (int j = 0; j < g->numVertex; j++)
	{
		if (g->edges[i][j] != INF && !visited[j])
		{
			DFS(g, j);//对为访问的邻接顶点递归调用
		}
	}
}
void DFSTraverse(Graph* g)
{
	//初始化 visited 标记
	for (int i = 0; i < g->numVertex; i++){
		visited[i] = FALSE;//初始化所有顶点状态都是未访问过状态
	}
	for (int i = 0; i < g->numVertex; i++)
	{
		if (!visited[i])//对未访问的顶点调用DFS，若是连通图，只会执行一次
		{
			DFS(g, i);
		}
	}
}
//广度优先遍历的实现
void BFS(Graph* g, int s)
{
	//以  s 为起点坐标
	queue<int> q;
	//初始化 visited 标记
	for (int i = 0; i < g->numVertex; i++){
		visited[i] = FALSE;//初始化所有顶点状态都是未访问过状态
	}
	visited[s] = TRUE;
	//do sth
	cout << s << "Test BFS" << endl;
	q.push(s);//将此节点入队列
	while (!q.empty())
	{
		int m;
		m = q.front();
		q.pop();
		for (int i = 0; i < g->numVertex; i++)
		{
			if (g->edges[s][i] != INF && !visited[i])
			{
				visited[i] = TRUE;
				//do sth
				cout << i << "Test BFS" << endl;
				q.push(i);
			}
		}
	}
}
int main()
{
	Graph *g = new Graph();
	CreateGraph(g, 10, 10);
	for (int i = 0; i < 3; i++)
	{
		g->vertex[i] = i + 1;
	}
	for (int i = 0; i < 10;i++)
	for (int j = 0; j < 10; j++)
	{
		SetEdgeVal(g, i, j, i + j);
	}
	DFSTraverse(g);
	BFS(g, 0);
	PrintGraph(g);
	return 0;
}

图的基本实现,布布扣,bubuko.com

图的基本实现

原文：http://blog.csdn.net/dutsoft/article/details/23027975