＜图＞邻接矩阵(有向)_有向图的邻接矩阵

图的存储结构
  1.顺序存储
    邻接矩阵adjacency_matrix表示顶点之间的关系
        缺点：迅速判断两个节点之间是否有边，方便计算各个顶点之间的度
        优点：不方便图中顶点的增加个删除，不方便访问各个邻接点
    需要两个数组来储存图。
        一维数组储存顶点信息
        二维数组储存顶点和顶点之间的邻接关系即边 notice:
          a -- b 
          |  / |    4个顶点，5条边
          d -- c
          vex[] = a b c d
                         a b c d
          Edge[i][j] = a 0 1 0 1
                       b 1 0 1 1
                       c 0 1 0 1
                       d 1 1 1 0
            1.对称阵 Edge[i][j] == Edge[j][i]
            2.第i行或第i列所有非0元素的个数 == 顶点的度
        -------------------------------------
            b
          ↗   ↖
         a  →  c  5个顶点，7条边
         ↓  ↙  ↓
         e  ←  d
         Vex[] = a b c d e 
                        a b c d e 
         Egde[i][j] = a 0 1 1 0 1
                      b 0 0 1 0 0
                      c 0 0 0 1 1
                      d 0 0 0 0 1
                      e 0 0 0 0 0 
         1.不一定是对称
         2.第i行非零元素的个数 == 第i个顶点的出度
         3.第i列非零元素的个数 == 第i个顶点的入度
 
        --------------------------------------
             5
          a  →  b  
        2 ↑     ↓ 4
          d  ←  c
             3
        Vex[] = a b c d
                        a  b  c  d
        Egde[i][j] = a -1  5 -1 -1
                     b -1 -1  4 -1
                     c -1 -1 -1  3
                     d  2 -1 -1 -1 
 
  2.链式存储
    邻接表

#include "directed_mat.h"
 
int main()
{
	struct AMG_Graph* ud_graph;
 
	ud_graph = Create_AMG_Graph();
 
    Show_AMG_Graph(ud_graph);
 
    return 0;
}

directed_mat.cpp

 
#include <iostream>
#include "directed_mat.h"
using namespace std;
 
 
struct AMG_Graph* Create_AMG_Graph(void)
{
	int i, j;
    char u, v;
	struct AMG_Graph* graph;
 
	// 申请内存空间，结构体多大申请多大，强制类型转换
	graph = (struct AMG_Graph *)malloc(sizeof(struct AMG_Graph));
 
	cout << "请输入顶点的个数： ";
	cin >> graph->vex_num;
 
	cout << "请输入边的个数： ";
	cin >> graph->edge_num;
 
 
		
	cout << "请输入顶点信息: " << endl;
	for(i = 0; i < graph->vex_num; i++)
	{
		cin >> graph->Vex[i];
 
	}
 
    for(i = 0; i < graph->vex_num; i++)
    {
        for(j = 0; j < graph->vex_num; j++)
        {
            // 初始化为0
            graph->Edge[i][j] = 0;
        }
    }
 
    while(graph->edge_num--)
    {
        cout << "请输入通过边连接起来的顶点：" << endl;
        cin >> u;
        cin >> v;
        // 到graph中找到字符u，所对应的索引
        i = search_vex(graph, u);
        j = search_vex(graph, v);
        if(i != -1 && j != -1)
            // 有向图为非对称的二维邻接矩阵
            graph->Edge[i][j]  = 1;
        else
        {
            cout << "你输入的顶点信息是错的，请再次输入" << endl;
            graph->edge_num++;
        }
    }
 
	return graph;
 
}
 
void Show_AMG_Graph(struct AMG_Graph * graph)
{
    int i,j;
    cout << "显示顶点信息："<< endl;
    for(i = 0; i < graph->vex_num; i++)
        cout << graph->Vex[i] << "\t";
    cout << endl;
 
    cout << "显示邻接矩阵：" << endl;
    for(i = 0; i < graph->vex_num; i++)
    {
        for(j = 0; j < graph->vex_num; j++)
        {
           cout <<  graph->Edge[i][j] << "\t";
        }
        cout << endl;
    }
}
 
 
int search_vex(struct AMG_Graph* graph, char c)
{
    int i;
    // o(n)
    for(i = 0; i < graph->vex_num; i++)
    {
        if(c == graph->Vex[i])
            return i;
    }
    return -1;
}

directed_mat.h

#ifndef __directed_mat_h__
#define __directed_mat_h__
 
#define MAX 100
 
// 图结构，代表一整张图
struct AMG_Graph
{
	// 顶点的个数，边的个数
	int vex_num, edge_num;
	// 储存顶点的信息的一维数组
	char Vex[MAX];
	// 储存顶点和顶点之间的邻接关系，二维矩阵
	int Edge[MAX][MAX];
 
};
 
 
 
struct AMG_Graph* Create_AMG_Graph(void);
void Show_AMG_Graph(struct AMG_Graph * graph);
int search_vex(struct AMG_Graph* graph, char c);
 
 
#endif