图的存储和遍历

0.图 = 点 + 边

1.邻接矩阵表示

 #define maxn 100
typedef struct {
	int no;         //顶点编号
	char data[maxn];//顶点的其他信息
}VertexType;
typedef struct{	
	int edges[maxn][maxn];		//存放边的数组
	int n, e;					//顶点数，边数
	VertexType vex[maxn][maxn];	//存放顶点数组
}MGraph;

2.邻接表表示

typedef struct EdgeNode{  //边表结点
	int adjvex;           //该边的终点编号( 如u->v ，这里指的就是v的编号 )
	int weight;           //边的权值
	struct EdgeNode *next; //指向下一条边的指针
}EdgeNode;
typedef struct VextexNode{
	char data;			  //顶点域，存储顶点信息
	EdgeNode *firstedge;  //边表头指针，指向连接的第一条边
}VextexNode, AdjList[maxn];  //AdjList是邻接表类型
typedef struct{
	AdjList adjList;	 //邻接表
	int n, e;              //图中顶点数和边数
}GraphAdjList;

附：用邻接表表示创建无向图(这里用的是头插法)：

void CreateALGraph(GraphAdjList *Gp)
{
    int i, j, k;
    EdgeNode *pe;
    cout << "输入顶点数和边数(空格分隔）:" << endl;
    cin >> Gp->numNodes >> Gp->numEdges;
    for (i = 0 ; i < Gp->numNodes; i++)
    {
        cout << "输入顶点信息：" << endl;
        cin >> Gp->adjList[i].data;
        Gp->adjList[i].firstedge = NULL;/* 将边表置为空表 */
    }
    for (k = 0; k <  Gp->numEdges; k++)/* 建立边表 */
    {
        cout << "输入边(u,v)的顶点序号i,j"<< endl;
        cin >> i >> j;
        pe = (EdgeNode *)malloc(sizeof(EdgeNode));
        pe->adjvex = j;     //边的终点编号为j 
        // 将pe的指针指向当前顶点上指向的结点 
        pe->next = Gp->adjList[i].firstedge;
        Gp->adjList[i].firstedge = pe;/* 将当前顶点的指针指向pe */
        //因为是无向图，所以下面还要以i作为边的终点
        pe = (EdgeNode *)malloc(sizeof(EdgeNode));
        pe->adjvex = i;
        pe->next = Gp->adjList[j].firstedge;
        Gp->adjList[j].firstedge = pe;
    }
}

3.深度优先遍历

注：INF是无穷，visited[] 是全局数组，用来标记点是否被访问，初始置为0

1.邻接矩阵：

void DFS(MGraph g, int v){
	int w;
	cout << v;			//输出当前访问的结点
	visited[v] = 1;     //将已访问的置为1
	for (w = 0; w < g.n; w++){		//找当前顶点v的所有邻接顶点
		if (g.edges[v][w] != 0 && g.edges[v][w] != INF&&visited[w] == 0){  //找顶点v未访问过的邻接点w
			DFS(g, w);				
		}
	}
}

2.邻接表：

void DFS(GraphAdjList *g, int v){
	EdgeNode *p;
	cout << v;						//输出当前访问的点
	visited[v] = 1;					//已访问的置为1
	p = g->adjList[v].firstedge;    //p指向顶点v的第一个边邻接点
	while (p != NULL){
		if (visited[p->adjvex] == 0){
			DFS(g, p->adjvex);   //若p->adjvex顶点未访问，递归访问它
		}
		p = p->next;   //p指向顶点v的下一个邻接点
	}
}

4.广度优先遍历(层次)

1.邻接矩阵：

void BFS(MGraph g, int v){
	queue<int> qu; //定义一个队列 qu
	int visited[maxn];  //定义一个存放结点打的访问标志的数组
	int w, i;
	memset(visited, 0, sizeof(visited)); //初始化访问标志数组
	cout << v;        //输出当前访问的顶点编号
	visited[v] = 1;   //已访问的置为1
	qu.push(v);       //v进队
	while (!qu.empty()){    //队列不空时循环
		w = qu.front();		
		qu.pop();			//出队队首顶点
		for (int i = 0; i < g.n; i++){
			//若当前相邻顶点i未被访问
			if (g.edges[v][i] != 0 && g.edges[v][i] != INF&&visited[i] == 0){
				cout << i;    //访问相邻顶点
				visited[i]=1;	  //已访问的置为1
				qu.push(i);   //该顶点进队
			}
		}
	}
	cout << endl;
}

2.邻接表：

void BFS(GraphAdjList* g, int v){
	EdgeNode *p;
	queue<int> qu; //定义一个队列 qu
	int visited[maxn];  //定义一个存放结点打的访问标志的数组
	int w, i;
	memset(visited, 0, sizeof(visited)); //初始化访问标志数组
	cout << v;        //输出当前访问的顶点编号
	visited[v] = 1;   //已访问的置为1
	qu.push(v);       //v进队
	while (!qu.empty()){    //队列不空时循环
		w = qu.front();		
		qu.pop();			//出队队首顶点w
		p = g->adjList[w].firstedge; //找顶点w的第一个邻接点
		while (p != NULL){
			//若当前相邻的顶点未被访问
			if (visited[p->adjvex] == 0){
				cout << p->adjvex;  //访问相邻顶点
				visited[p->adjvex] = 1; //已访问的置为1
				qu.push(p->adjvex);		//该顶点进队
			}
			p = p->next;   //找顶点w的下一个邻接点
		}
	}
	cout << endl;
}